Kernelized locality-sensitive hashing for scalable image search
Top Cited Papers
- 1 September 2009
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2130-2137
- https://doi.org/10.1109/iccv.2009.5459466
Abstract
Fast retrieval methods are critical for large-scale and data-driven vision applications. Recent work has explored ways to embed high-dimensional features or complex distance functions into a low-dimensional Hamming space where items can be efficiently searched. However, existing methods do not apply for high-dimensional kernelized data when the underlying feature embedding for the kernel is unknown. We show how to generalize locality-sensitive hashing to accommodate arbitrary kernel functions, making it possible to preserve the algorithm's sub-linear time similarity search guarantees for a wide class of useful similarity functions. Since a number of successful image-based kernels have unknown or incomputable embeddings, this is especially valuable for image retrieval tasks. We validate our technique on several large-scale datasets, and show that it enables accurate and fast performance for example-based object classification, feature matching, and content-based retrieval.Keywords
This publication has 28 references indexed in Scilit:
- Information-theoretic metric learningPublished by Association for Computing Machinery (ACM) ,2007
- Local Features and Kernels for Classification of Texture and Object Categories: A Comprehensive StudyInternational Journal of Computer Vision, 2006
- Photo tourismPublished by Association for Computing Machinery (ACM) ,2006
- Kernel ICA: An alternative formulation and its application to face recognitionPattern Recognition, 2005
- Sub-linear Indexing for Large Scale Object RecognitionPublished by British Machine Vision Association and Society for Pattern Recognition ,2005
- Nonlinear Component Analysis as a Kernel Eigenvalue ProblemNeural Computation, 1998
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Satisfying general proximity / similarity queries with metric treesInformation Processing Letters, 1991
- An Algorithm for Finding Best Matches in Logarithmic Expected TimeACM Transactions on Mathematical Software, 1977
- The Law of Large Numbers and the Central Limit Theorem in Banach SpacesThe Annals of Probability, 1976