The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Locality sensitive hashing: A comparison of hash function types and querying mechanisms
Abstract
It is well known that high-dimensional nearest neighbor retrieval is very expensive. Dramatic performance gains are obtained using approximate search schemes, such as the popular Locality-Sensitive Hashing (LSH). Several extensions have been proposed to address the limitations of this algorithm, in particular, by choosing more appropriate hash functions to better partition the vector space. All the proposed extensions, however, rely on a structured quantizer for hashing, poorly fitting real data sets, limiting its performance in practice. In this paper, we compare several families of space hashing functions in a real setup, namely when searching for high-dimension SIFT descriptors. The comparison of random projections, lattice quantizers, k-means and hierarchical k-means reveal that unstructured quantizer significantly improves the accuracy of LSH, as it closely fits the data in the feature space. We then compare two querying mechanisms introduced in the literature with the one originally proposed in LSH, and discuss their respective merits and limitations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Distinctive Image Features from Scale-Invariant Keypoints
Lowe, D. G. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000029664.99615.94 · Cited by 55,589
Video Google: a text retrieval approach to object matching in videos
Sivic, & Zisserman (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238663 · Cited by 6,367 · cited 2×
“From an application point of view, it corresponds for instance to the case where we want to assign a SIFT descriptor to a visual word, as done in (Sivic and Zisserman, 2003).”
Scalable Recognition with a Vocabulary Tree
Nister, D., & Stewenius, H. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.264 · Cited by 3,579
Scale & Affine Invariant Interest Point Detectors
Mikolajczyk, K., & Schmid, C. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000027790.02288.f2 · Cited by 3,436
Sphere Packings, Lattices and Groups.
Coxeter, H. S. M., Conway, J. H., & Sloane, N. J. A. (1989) · The American Mathematical Monthly · doi:10.2307/2323992 · Cited by 3,377
(1999) · Cited by 3,186
Locality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. S. (2004) · Proceedings of the twentieth annual symposium on Computational geometry · doi:10.1145/997817.997857 · Cited by 2,936
Object retrieval with large vocabularies and fast spatial matching
Philbin, J., Chum, O., Isard, M., Sivic, J., & Zisserman, A. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383172 · Cited by 2,929
Automatic Panoramic Image Stitching using Invariant Features
Brown, M., & Lowe, D. G. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-0002-3 · Cited by 2,665
FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
(2009) · Proceedings of the Fourth International Conference on Computer Vision Theory and Applications · doi:10.5220/0001787803310340 · Cited by 2,640
When Is ''Nearest Neighbor'' Meaningful?
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49257-7_15 · Cited by 2,403 · cited 2×
“Nearest neighbor search is inherently expensive due to the curse of dimensionality (Böhm et al., 2001; Beyer et al., 1999).”
Zhang, J., Marszałek, M., Lazebnik, S., & Schmid, C. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-9794-4 · Cited by 1,923
Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search
Jegou, H., Douze, M., & Schmid, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88682-2_24 · Cited by 1,901 · cited 10×
“…functions have recently been proposed to improve the performance of E2LSH, including the Leech lat-tices (Shakhnarovich et al., 2006) and E8 lattices (J´egou et al., 2008a), which o ff er strong quantization properties, and spherical hash functions (Terasawa and Tanaka, 2007) for unit-norm vectors.”
InfluentialSelf-citationGray, R. M., & Neuhoff, D. L. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720541 · Cited by 1,642
Sphere Packings, Lattices and Groups
Conway, J. H., & Sloane, N. J. A. (1988) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-1-4757-2016-7 · Cited by 1,532
Closest point search in lattices
Agrell, E., Eriksson, T., Vardy, A., & Zeger, K. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.800499 · Cited by 1,412
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Andoni, A., & Indyk, P. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.49 · Cited by 1,067
Böhm, C., Berchtold, S., & Keim, D. A. (2001) · ACM Computing Surveys · doi:10.1145/502807.502809 · Cited by 827
Multi-probe LSH: efficient indexing for high-dimensional similarity search
Lv, Q., Josephson, W. K., Wang, Z., Charikar, M., & Li, K. (2007) · Very Large Data Bases · Cited by 634
ACOUSTICS. SPEECH. AND SIGNAL PROCESSING
Assp, V. (1983) · Cited by 556
Fast quantizing and decoding and algorithms for lattice quantizers and codes
Conway, J., & Sloane, N. J. A. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056484 · Cited by 439
Nearest-neighbor methods in learning and vision : theory and practice
Shakhnarovich, G., Indyk, P., & Darrell, T. (2005) · Cited by 399
An efficient parts-based near-duplicate and sub-image retrieval system
Ke, Y., Sukthankar, R., & Huston, L. (2004) · Proceedings of the 12th annual ACM international conference on Multimedia · doi:10.1145/1027527.1027729 · Cited by 361
Efficient near-duplicate detection and sub-image retrieval
Ke, Y. (2004) · Cited by 341
Voronoi regions of lattices, second moments of polytopes, and quantization
Conway, J., & Sloane, N. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056483 · Cited by 321
A posteriori multi-probe locality sensitive hashing
Joly, A., & Buisson, O. (2008) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/1459359.1459388 · Cited by 159
Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
Terasawa, K., & Tanaka, Y. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73951-7_4 · Cited by 124
Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing)
Shakhnarovich, G., Darrell, T. J., & Indyk, P. (2006) · The MIT Press eBooks · Cited by 121
Rapid object indexing using locality sensitive hashing and joint 3D-signature space estimation
Matei, B., Shan, Y., Sawhney, H., Tan, Y., Kumar, R., Huber, D., & Hebert, M. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.148 · Cited by 117
Maximum likelihood decoding of the Leech lattice
Vardy, A., & Be'ery, Y. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.243466 · Cited by 69
Query adaptative locality sensitive hashing
Jeǵou, H., Amsaleg, L., Schmid, C., & Gros, P. (2008) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2008.4517737 · Cited by 58
Self-citationScalability of local image descriptors: a comparative study
Lejsek, H., Ásmundsson, F. H., Jónsson, B. Þ., & Amsaleg, L. (2006) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/1180639.1180760 · Cited by 54
Self-citation
Cited by
Billion-scale similarity search with GPUs
Johnson, J., Douze, M., & Jégou, H. (2017) · arXiv · doi:10.48550/arxiv.1702.08734 · Cited by 4,140
Billion-scale similarity search with GPUs
Johnson, J., Douze, M., & Jegou, H. (2021) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2019.2921572 · Cited by 4,228
Gong, Y., Lazebnik, S., Gordo, A., & Perronnin, F. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.193 · Cited by 1,834
Wang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 971
Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, P.-E., Lomeli, M., Hosseini, L., & Jégou, H. (2026) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2025.3618474 · Cited by 478
“However, we do not consider this scenario as the performance is generally inferior to that of learnt partitions [20].”
Metadata
- Authors
- Paulevé, L., Jégou, H., & Amsaleg, L.
- Venue
- Pattern Recognition Letters
- Publisher
- Elsevier BV
- Published
- 2010-08
- Volume
- 31
- Issue
- 11
- Pages
- 1348-1358
- ISSN
- 0167-8655 (ISSN-L)
- OpenAlex
- W2059139185
- Cited by
- 297
- References
- 32
- FWCI
- 22.48
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.