Systems and methods for large scale, high-dimensional searches

Abstract

Methods and systems for fast, large scale, high-dimensional searches are described. In some embodiments, a method comprises transforming components of a high-dimensional image descriptor into transformed components in a transform domain, allocating one or more bits available within a bit budget to a given transformed component within a first subset of transformed components as a function of a variance of the given transformed component, independently quantizing each transformed component within the first subset of transformed components, generating a compact representation of the high-dimensional image descriptor based, at least in part, on the independently quantized components, and evaluating a nearest neighbor search operation based, at least in part, on the compact representation of the high-dimensional image descriptor.

What is claimed is: 
     
       1. A computer-readable storage medium, excluding signals per se, comprising instructions stored thereon that, responsive to execution by a computing device, direct the computing device to perform operations comprising:
 transforming components of a image descriptor into transformed components in a transform domain; 
 quantizing the transformed components; 
 generating a compact representation of the image descriptor based, at least in part, on the quantized components; and 
 responsive to the generating, constructing, at query time, a one-dimensional look-up table that stores a partial distance between two or more of the quantized components. 
 
     
     
       2. The computer-readable storage medium of  claim 1 , wherein the image descriptor is a SIFT descriptor. 
     
     
       3. The computer-readable storage medium of  claim 1 , wherein the quantizing reduces a distortion. 
     
     
       4. The computer-readable storage medium of  claim 1 , wherein the generating comprises concatenating the two or more of the quantized components into a word such that the quantized components do not straddle a word boundary. 
     
     
       5. The computer-readable storage medium of  claim 4 , the operations further comprising:
 calculating a partial distance between the quantized components within the word. 
 
     
     
       6. The computer-readable storage medium of  claim 1 , the operations further comprising allocating one or more bits available within a bit budget to a given transformed component within a first subset of transformed components as a function of a variance of the given transformed component, wherein a second subset of the transformed components receives zero bits. 
     
     
       7. The computer-readable storage medium of  claim 1 , wherein the transforming reduces a correlation among the components. 
     
     
       8. The computer-readable storage medium of  claim 1 , the operations further comprising evaluating a nearest neighbor search operation based, at least in part, on the compact representation of the image descriptor. 
     
     
       9. The computer-readable storage medium of  claim 8 , wherein the nearest neighbor search operation is performed based, at least in part, on the one-dimensional look-up table as part of a process selected from the group consisting of: a k-nearest neighbor image search, an image retrieval process, and a spatial pyramid bag-of-words retrieval process. 
     
     
       10. A method, comprising:
 performing, by one or more computing devices:
 transforming components of an image descriptor into transformed components; 
 allocating bits to a subset of the transformed components; 
 quantizing the subset of transformed components; 
 concatenating two or more of the quantized components into a word; and 
 constructing a two-dimensional look-up table, prior to a query, that stores a partial distance determined by the concatenated components within the word. 
 
 
     
     
       11. The method of  claim 10 , wherein concatenating comprises permuting the two or more quantized components within the word such that no quantized component straddles a word boundary. 
     
     
       12. The method of  claim 10 , further comprising applying the two-dimensional look-up table in a nearest neighbor search operation. 
     
     
       13. The method of  claim 10 , further comprising applying the two-dimensional look-up table in an image feature matching process. 
     
     
       14. The method of  claim 13 , the image feature matching process including an Internet search or microarray DNA analysis. 
     
     
       15. The method of  claim 12 , wherein the nearest neighbor search operation is performed based, at least in part, on the two-dimensional look-up table as part of a local feature image matching process. 
     
     
       16. A system, comprising:
 at least one processor; and 
 memory, communicatively coupled to the at least one processor, storing instructions that responsive to execution by the at least one processor, cause the at least one processor to perform operations comprising:
 quantizing components of a plurality of image descriptors; 
 concatenating two or more of the quantized components into a word such that the quantized components do not straddle a word boundary; 
 calculating a partial distance between the concatenated components; and 
 constructing, at query time, a one-dimensional look-up table that stores the partial distance between the concatenated components of the word. 
 
 
     
     
       17. The system of  claim 16 , the operations further comprising:
 evaluating a nearest neighbor search based, at least in part, on the one-dimensional look-up table. 
 
     
     
       18. The system of  claim 16 , the operations further comprising, prior to quantizing:
 transforming components of the image descriptors to reduce a correlation among the components. 
 
     
     
       19. The system of  claim 16 , where a number of quantization levels allocated to a given component is a function of a statistic of the given component as determined from a training sample. 
     
     
       20. The system of  claim 16 , the operations further comprising performing an Internet search based on the one-dimensional look-up table.