Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Open accessAbstract
In this article, we give an overview of efficient algorithms for the approximate and exact nearest neighbor problem. The goal is to preprocess a dataset of objects (e.g., images) so that later, given a new query object, one can quickly return the dataset object that is most similar to the query. The problem is of significant interest in a wide variety of areas.
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
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Facebook reports that 'false' accounts are less prevalent in developed markets and more in developing markets.
“The other three target one developed and two developing countries, as Facebook reports that 'false' accounts are less prevalent in developed markets and more in developing markets. 1”
From Measuring, Characterizing, and Detecting Facebook Like Farms (2017) · cites this paper as [1]
The two-class SVM is the most effective in detecting like farm users compared to Decision Tree, AdaBoost, kNN, Random Forest, and Naïve Bayes.
“We later compare this classifier with other well-known supervised classifiers such as Decision Tree [7], AdaBoost [20], kNN [1], Random Forest [6], and Na¨ ıve Bayes [55] and confirm that the two-class SVM is the most effective in detecting like farms users.”
From Measuring, Characterizing, and Detecting Facebook Like Farms (2017) · cites this paper as [1]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,659 · see citing works
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 · see citing works
Self-citationGoemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · see citing works
Sphere Packings, Lattices and Groups.
Coxeter, H. S. M., Conway, J. H., & Sloane, N. J. A. (1989) · American Mathematical Monthly · doi:10.2307/2323992 · Cited by 3,373 · see citing works
(1999) · Cited by 3,186 · see citing works
Locality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. (2004) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/997817.997857 · Cited by 2,971 · see citing works
Self-citationSimilarity estimation techniques from rounding algorithms
Charikar, M. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509965 · Cited by 2,262 · see citing works
On the resemblance and containment of documents
Broder, A. (2002) · Compression and Complexity of Sequences (SEQUENCES) · doi:10.1109/sequen.1997.666900 · Cited by 1,734 · see citing works
Handbook of discrete and computational geometry
Goodman, J. E., O'Rourke, J. 1., & Tóth, C. D. (1998) · Choice Reviews Online · doi:10.5860/choice.35-5707b · Cited by 1,457 · see citing works
Foundations of Multidimensional and Metric Data Structures
Samet, H., & Gray, J. (2006) · Cited by 1,373 · see citing works
Syntactic clustering of the Web
Broder, A., Glassman, S. C., Manasse, M. S., & Zweig, G. (1997) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(97)00031-7 · Cited by 1,348 · see citing works
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 · see citing works
Self-citationThe Volume of Convex Bodies and Banach Space Geometry
Pisier, G. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662454 · Cited by 997 · see citing works
Min-Wise Independent Permutations
Broder, A., Charikar, M., FRIEZE, A. M., & Mitzenmacher, M. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1690 · Cited by 812 · see citing works
Proceedings of the International Conference on Very Large Data Bases
Kerr, D. S. (1975) · Medical Entomology and Zoology · Cited by 691 · see citing works
An optimal algorithm for approximate nearest neighbor searching
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1994) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · doi:10.5555/314464.314652 · Cited by 590 · see citing works
Finding Motifs Using Random Projections
Buhler, J. D., & Tompa, M. (2002) · Journal of Computational Biology · doi:10.1089/10665270252935430 · Cited by 535 · see citing works
The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
Ailon, N., & Chazelle, B. (2009) · SIAM Journal on Computing · doi:10.1137/060673096 · Cited by 473 · see citing works
Nearest-Neighbor Methods in Learning and Vision
(2006) · The MIT Press eBooks · doi:10.7551/mitpress/4908.001.0001 · Cited by 442 · see citing works
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Ailon, N., & Chazelle, B. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132597 · Cited by 373 · see citing works
Min-wise independent permutations (extended abstract)
Broder, A., Charikar, M., FRIEZE, A. M., & Mitzenmacher, M. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276781 · Cited by 364 · see citing works
Two algorithms for nearest-neighbor search in high dimensions
Kleinberg, J. M. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258653 · Cited by 353 · see citing works
Navigating nets: simple algorithms for proximity search
Krauthgamer, R., & Lee, J. R. (2015) · Cited by 308 · see citing works
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Z., Ostrovsky, R., & Rabani, Y. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276877 · Cited by 261 · see citing works
Efficient large-scale sequence comparison by locality-sensitive hashing
Buhler, J. D. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.5.419 · Cited by 253 · see citing works
Nearest-Neighbor Methods in Learning and Vision (Shakhnarovich, G. et al., Eds.; 2006) [Book review]
Gianfelici, F. (2008) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.917504 · Cited by 236 · see citing works
Nearest Neighbors in High-Dimensional Spaces
Indyk, P. (2004) · Discrete mathematics and its applications · doi:10.1201/9781420035315.ch39 · Cited by 210 · see citing works
Self-citationRavichandran, D., Pantel, P., & Hovy, E. H. (2005) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.3115/1219840.1219917 · Cited by 206 · see citing works
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. G. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365733 · Cited by 191 · see citing works
Leech, J. (1967) · Canadian Journal of Mathematics · doi:10.4153/cjm-1967-017-0 · Cited by 186 · see citing works
Entropy based nearest neighbor search in high dimensions
Panigrahy, R. (2006) · doi:10.5555/1109557.1109688 · Cited by 182 · see citing works
Approximating a finite metric by a small number of tree metrics
Charikar, M., Chekuri, C., Goel, A., Guha, S., & Plotkin, S. A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743488 · Cited by 175 · see citing works
Soft decoding techniques for codes and lattices, including the Golay code and the Leech lattice
Conway, J., & Sloane, N. J. A. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057135 · Cited by 165 · see citing works
Finding motifs using random projections
Buhler, J. D., & Tompa, M. (2001) · doi:10.1145/369133.369172 · Cited by 165 · see citing works
Scalable Techniques for Clustering the Web.
Haveliwala, T. H., Gionis, A., & Indyk, P. (2000) · Cited by 148 · see citing works
Self-citationA replacement for Voronoi diagrams of near linear size
Har-Peled, S. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959884 · Cited by 147 · see citing works
On the optimality of the random hyperplane rounding technique for MAX CUT
Feige, U., & Schechtman, G. (2002) · Random Structures and Algorithms · doi:10.1002/rsa.10036 · Cited by 124 · see citing works
High-dimensional computational geometry
Motwani, R., & Indyk, P. (2000) · Cited by 114 · see citing works
Self-citationFLASH: a fast look-up algorithm for string homology
Califano, A., & Rigoutsos, I. (2002) · 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.1993.341106 · Cited by 99 · see citing works
Approximate graph coloring by semidefinite programming
Karger, D. R., Motwani, R., & Sudan, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365710 · Cited by 99 · see citing works
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 · see citing works
On the Optimality of the Dimensionality Reduction Method
Andoni, A., Indyk, P., & Pǎtraşcu, M. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.56 · Cited by 95 · see citing works
Self-citationSpherical 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 86 · see citing works
Generalized minimum-distance decoding of Euclidean-space codes and lattices
Forney, G. D., & Vardy, A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556693 · Cited by 74 · see citing works
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 65 · see citing works
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching
Chakrabarti, A., & Regev, O. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.12 · Cited by 60 · see citing works
Lower bounds on locality sensitive hashing
Motwani, R., Naor, A., & Panigrahi, R. (2006) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1137856.1137881 · Cited by 55 · see citing works
Better algorithms for high-dimensional proximity problems via asymmetric embeddings
Indyk, P. (2003) · Cited by 47 · see citing works
Self-citationEfficient algorithms for substring near neighbor problem
Andoni, A., & Indyk, P. (2006) · Cited by 26 · see citing works
Self-citationScalable Partitioning and Exploration of Chemical Spaces Using Geometric Hashing
Dutta, D., Guha, R., Jurs, P. C., et al. (2005) · Journal of Chemical Information and Modeling · doi:10.1021/ci050403o · Cited by 20 · see citing works
Scalable Techniques for Clustering the Web (Extended Abstract)
Haveliwala, T. H., Gionis, A., & Indyk, P. (2000) · Cited by 19 · see citing works
Self-citationThe bit vector intersection problem
Karp, R. M., Waarts, O., & Zweig, G. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492663 · Cited by 19 · see citing works
Paturi, R., Rajasekaran, S., & Reif, J. H. (1995) · Information and Computation · doi:10.1006/inco.1995.1038 · Cited by 17 · see citing works
Amrani, O., & Be'ery, Y. (1996) · IEEE Transactions on Communications · doi:10.1109/26.494294 · Cited by 14 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduct. Algorithms. 2nd Ed. MIT Press.
- Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. 2004. Localitysensitive hashing scheme based on p-stable distributions.In Proceedings of the ACM Symposium on Computational Geometry.
Cited by
Sorted by citations
Deep hashing for compact binary codes learning
Liong, V. E., Lu, J., Wang, G., Moulin, P., & Zhou, J. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298862 · Cited by 545 · see citing works
Lane, N. D., Xu, Y., Lu, H., Hu, S., Choudhury, T., Campbell, A. T., & Zhao, F. (2011) · Proceedings of the 13th international conference on Ubiquitous computing · doi:10.1145/2030112.2030160 · Cited by 171 · see citing works
Tenney, I., Wexler, J., Bastings, J., Bolukbasi, T., Coenen, A., Gehrmann, S., Jiang, E., Pushkarna, M., Radebaugh, C., Reif, E., et al. (2020) · Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations · doi:10.18653/v1/2020.emnlp-demos.15 · Cited by 138 · see citing works
“Users can create new datapoints based on datapoints of interest either manually through edits, or with a range of automatic counterfactual generators, such as backtranslation (Bannard and Callison-Burch, 2005), nearestneighbor retrieval (Andoni and Indyk, 2006), word substitutions (“great → terrible”), or adversarial…”
BackgroundMethodFoggyCache: Cross-Device Approximate Computation Reuse
Guo, P., Hu, B., Li, R., & Hu, W. (2018) · Proceedings of the 24th Annual International Conference on Mobile Computing and Networking · doi:10.1145/3241539.3241557 · Cited by 91 · see citing works
DNA Data Storage and Hybrid Molecular–Electronic Computing
Carmean, D., Ceze, L., Seelig, G., Stewart, K., Strauss, K., & Willsey, M. (2019) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2875386 · Cited by 69 · see citing works
Measuring, Characterizing, and Detecting Facebook Like Farms
Ikram, M., Onwuzurike, L., Farooqi, S., Cristofaro, E. D., Friedman, A., Jourjon, G., Kaafar, M. A., & Shafiq, M. Z. (2017) · ACM Transactions on Privacy and Security · doi:10.1145/3121134 · Cited by 27 · see citing works
“Finally, we generalize our approach using other classification algorithms, namely, decision tree [7], AdaBoost [20], kNN [1], random forest [6], and naı̈ve Bayes [55], and empirically confirm that the SVM classifier achieves higher accuracy across the board.”
MethodZhao, Z., Gao, M., Luo, F., Zhang, Y., & Xiong, Q. (2020) · 2020 International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn48605.2020.9207640 · Cited by 13 · see citing works
- Authors
- Andoni, A., & Indyk, P.
- Affiliations
- Massachusetts Institute of Technology (US)
- Venue
- Communications of the ACM
- Published
- 2008-01
- Volume
- 51
- Issue
- 1
- Pages
- 117-122
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2038276547
- Cited by
- 1,437
- References
- 54
- Citations by year
- 2026: 21 · 2025: 41 · 2024: 35 · 2023: 42 · 2022: 43 · 2021: 48 · 2020: 81 · 2019: 98 · 2018: 99 · 2017: 107 · 2016: 131 · 2015: 127 · 2014: 123 · 2013: 111 · 2012: 96
- FWCI
- 110.95
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Communications of the ACM (publishedVersion)
- Funders
- National Science Foundation (CCR-0133849)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Image and Video Retrieval Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- approximate nearest neighbor search, hash algorithms, high-dimensional data, nearest neighbor search, similarity search, data preprocessing, image retrieval
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
