The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Fast search in Hamming space with multi-index hashing
Abstract
There has been growing interest in mapping image data onto compact binary codes for fast near neighbor search in vision applications. Although binary codes are motivated by their use as direct indices (addresses) into a hash table, codes longer than 32 bits are not being used in this way, as it was thought to be ineffective. We introduce a rigorous way to build multiple hash tables on binary code substrings that enables exact K-nearest neighbor search in Hamming space. The algorithm is straightforward to implement, storage efficient, and it has sub-linear run-time behavior for uniformly distributed codes. Empirical results show dramatic speed-ups over a linear scan baseline and for datasets with up to one billion items, 64- or 128-bit codes, and search radii up to 25 bits.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope
Oliva, A., & Torralba, A. (2001) · International Journal of Computer Vision · doi:10.1023/a:1011139631724 · Cited by 6,319
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Product Quantization for Nearest Neighbor Search
Jégou, H., Douze, M., & Schmid, C. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.57 · Cited by 2,956 · cited 1×
“, [1, 10, 15]), we restrict our attention in this paper to the use of compact binary codes.”
BackgroundFAST 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
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,389
Similarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition
Torralba, A., Fergus, R., & Freeman, W. T. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.128 · Cited by 1,921
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 1×
“Nearest neighbor (NN) search on binary codes has been used for image search [18, 23, 24], matching local features [9, 21], and parameter estimation [20].”
MethodParameterized Complexity Theory
(2006) · Texts in Theoretical Computer Science. An EATCS Series · doi:10.1007/3-540-29953-x · Cited by 1,869
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Andoni, A., & Indyk, P. (2008) · Communications of the ACM · doi:10.1145/1327452.1327494 · Cited by 1,437
Salakhutdinov, R., & Hinton, G. (2009) · International Journal of Approximate Reasoning · doi:10.1016/j.ijar.2008.11.006 · Cited by 1,246
Iterative quantization: A procrustean approach to learning binary codes
Gong, Y., & Lazebnik, S. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995432 · Cited by 1,038
Learning to Hash with Binary Reconstructive Embeddings
Kulis, B., & Darrell, T. (2009) · Cited by 806
Fast pose estimation with parameter-sensitive hashing
Shakhnarovich, Viola, & Darrell (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238424 · Cited by 758
Small codes and large image databases for recognition
Torralba, A., Fergus, R., & Weiss, Y. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587633 · Cited by 727
Minimal Loss Hashing for Compact Binary Codes
Norouzi, M., & Blei, D. M. (2011) · Cited by 694
Self-citationSimilarity estimation techniques from rounding algorithms
Charikar, M. (2002) · doi:10.1145/509961.509965 · Cited by 659
LDAHash: Improved Matching with Smaller Descriptors
Strecha, C., Bronstein, A. M., Bronstein, M. M., & Fua, P. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.103 · Cited by 605
Locality-sensitive binary codes from shift-invariant kernels
Raginsky, M., & Lazebnik, S. (2009) · Cited by 600
Searching in one billion vectors: Re-rank with source coding
Jegou, H., Tavenard, R., Douze, M., & Amsaleg, L. (2011) · 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2011.5946540 · Cited by 313
Compact hashing with joint optimization of search accuracy and time
He, J., Chang, S., Radhakrishnan, R., & Bauer, C. (2011) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2011.5995518 · Cited by 108
Multi-index hashing for information retrieval
Greene, D., Parnas, M., & Yao, F. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365720 · Cited by 97
Distributed Kd-Trees for Retrieval from Very Large Image Collections
Aly, M., Munich, M. E., & Perona, P. (2011) · Cited by 56
Distributed Kd-Trees for Ultra Large Scale Object Recognition
Aly, M., Munich, M. E., & Perona, P. (2011) · British Machine Vision Conference (BMVC) · doi:10.5244/c.25.40 · Cited by 4
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
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
HashNet: Deep Learning to Hash by Continuation
Cao, Z., Long, M., Wang, J., & Yu, P. S. (2017) · 2017 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.598 · Cited by 777
Deep Hashing Network for Efficient Similarity Retrieval
Zhu, H., Long, M., Wang, J., & Cao, Y. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10235 · Cited by 664
Metadata
- Authors
- Norouzi, M., Punjani, A., & Fleet, D. J.
- Venue
- 2012 IEEE Conference on Computer Vision and Pattern Recognition
- Publisher
- IEEE
- Published
- 2012-06
- Pages
- 3108-3115
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2122196799
- Cited by
- 263
- References
- 25
- FWCI
- 18.23
- Type
- conference paper
- 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.