Article

Free access

Approximate nearest neighbors: towards removing the curse of dimensionality

Authors:

Piotr Indyk,

Rajeev MotwaniAuthors Info & Claims

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

Pages 604 - 613

https://doi.org/10.1145/276698.276876

Published: 23 May 1998 Publication History

PDF eReader

References

[1]

P,K, Agarwal and J. Matou~ek. Ray shooting and parametric search. In: Proceedings o/the Twenty- Fourth Annual A CM Symposium on Theory of Computing, 1992, pp. 517-526.

Digital Library

Google Scholar

[2]

$, Arya and D. Mount. Approximate nearest neighbor searching. In: Proceedings of the Fourth Annual A GM. SIAM Symposium on Discrete Algorithms, 1993, pp. 271-280,

Digital Library

Google Scholar

[3]

13, Arya, D,M, Mount, and O. Narayan, Accounting for boundary effects in nearest-neighbor searching. Discrete and Computational Geometry, 16(1996):155-176.

Digital Library

Google Scholar

[4]

S, Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. In: Proceedings of the Fi/th Annual A GM. SIAM Symposium on Discrete Al. gorithms, 1994, pp. 573-582.

Digital Library

Google Scholar

[5]

A, Andersson, P. B. Miltersen, $. Riis, M. Thorup, Static dictionaries on AC~ RAMs: Query time O( iogn! loglog n) is necessary and sufficient. In: Proceedings of the 37th Annual IEEE Symposium on Foundations o/Computer Science, 1996, pp. 441-450.

Digital Library

Google Scholar

[6]

J.L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the A CM, 18(m75):509-517.

Digital Library

Google Scholar

[7]

M. Bern. Approximate closest-point queries in high dimensions. Information Processing Letters, 45(1993):95- 99.

Digital Library

Google Scholar

[8]

M.W. Berry, S.T. Dumais, and A.T. Shippy. A case study of latent semantic indexing. U.T. Knoxville Technical Report; CS-95-271, January 1995.

Digital Library

Google Scholar

[9]

A. Broder, S. Glassman, M. Manasse, and G. Zweig. Syntactic clustering of the Web. In: Proceedings of the Sixth International F~rld F'fde l~b Conference, pp. 391-404, 1997.

Digital Library

Google Scholar

[10]

C. Buddey, A. Singhal, M. Mitra, and G. Salton. New Retrieval Approaches Using SMART: TREC 4. In: Pro. ceedings of the Fourth Text Retrieval Conference, National Institute of Standards and Technology, 1995.

Google Scholar

[11]

W.A. Burkhard and R.M. Keller. Some approaches to Best-Match File Searching. Communications of the ACM, 16(1973):230-236.

Digital Library

Google Scholar

[12]

T. Bozkaya and M. Ozsoyoglu. Distance-Based Indexing for High-Dimensional Metric Spaces, In: Proceedings of the A CM SIGMOD International Conference on Management of Data (SIGMOD), 1997.

Digital Library

Google Scholar

[13]

F. Cazals. Effective Nearest Neighbours 13earchJng on the Hyper-Cube, with Applications to Molecular Clustering. In Proceedings of the l~th Annual A CM Symposium on Computational Geometry, 1998.

Digital Library

Google Scholar

[14]

T.M. Chan. Approximate Nearest Neighbor Queries Revisited. In: Proceedings of the 18th Annual A CM Symposium on Computational Geometry, 1997, pp. 352-358.

Digital Library

Google Scholar

[15]

K. Clarkson. A randomized algorithm for closest-point queries. SlAM Journal on Computing, 17(1988):830- 847.

Digital Library

Google Scholar

[16]

K. Clarkson. An algorithm for approximate closestpoint queries. In: Proceedings of the Tenth Annual ACM Symposium on Computational Geometry, 1994, pp. 160-164.

Digital Library

Google Scholar

[17]

K. Clarkson. Nearest Neighbor Queries in Metric Spaces. in: Proceedings of the Twenty. Ninth Annual ACM Symposium on Theory of Computing, 1997, pp. 609-617.

Digital Library

Google Scholar

[18]

$. Cost and S. Salzberg. A weighted nearest neighbor algorithm for learning with symbolic features. Machine Learning, 10(1993):57-67.

Digital Library

Google Scholar

[19]

T.M. Cover and P.E. Hart, Nearest neighbor pattern classification. {EEE Transactions on Information The. ory, 13(1967):21-27.

Google Scholar

[20]

$. Deerwester, S. T. Dumais, T.K. Landaner, G.W. Furhas, and R.A. Harshman. Indexing by latent semantic analysis. Journal of the Society fo~ Information Sci. ences, 41(1990):391-407.

Google Scholar

[21]

L. Devroye and T.J. Wagner, Nearest neighbor methods in discrimination. In: Handbook of Statistics, vol. 2, P.R. Krishnaiah and L.N. Kanal, eds., North-Holland, 1982.

Google Scholar

[22]

D. Dobkin and R. Lipton. Multidimensional search problems. SIAM Journal on Computing, 5(1976):181- 186.

Crossref

Google Scholar

[23]

D. Dolev, Y. Harari, N. Linial, N. Nisan, and M. Parhas. Neighborhood preserving hashing and approximate queries. In: Proceedings of the Fifth Annual A CM-SIAM Symposium on Discrete Algorithms, 1994, pp. 251-259.

Digital Library

Google Scholar

[24]

D. Dolev, Y. Harari, and M. Parnas. Finding the neighborhood of a query in a dictionary. In: Proceedings of the ~nd Israel Symposium on Theory and Computing Systems, 1993, pp. 33-42.

Crossref

Google Scholar

[25]

R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. John Wiley & Sons, NY, 1973.

Digital Library

Google Scholar

[26]

H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, 1987.

Digital Library

Google Scholar

[27]

D. Eppstein, Fast hierarchical clustering and other applicatiom~ of dynamic closest pairs. In: Proceedings of the Ninth A CM-SIAM Symposium on Discrete Algo. rithms, 1998.

Digital Library

Google Scholar

[28]

C. Faloutso$, R. Barber, M. Fliclmer, W. Niblack, D. Petkovic, and W. Equitz. Efficient and effective querying by image content. Journal of Intelligent Information Systems, 3( 1994):231-262.

Digital Library

Google Scholar

[29]

W. Feller. An introduction to Probability Theory and its Applications. John Wiley & Sons, NY, 1991.

Google Scholar

[30]

M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dora, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: the QBIC system. IEEE Computer, 2s(199~):ea-32.

Digital Library

Google Scholar

[31]

W. Frakes and R. Baeza-Yates, editors. Information Retrieval: Data Structures and Algorithms. Prentice- Hall, 1992.

Digital Library

Google Scholar

[32]

P. Franld and H. Maehara. The Johnson-Lindenstrauss Lemma and the Sphericity of Some Graphs. Journal of Combinatorial Theory B, 44(1988):355-362.

Digital Library

Google Scholar

[33]

M.L. Fredman, J. Koml6s, and E. Szemer~di. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(1984):538-544.

Digital Library

Google Scholar

[34]

J.K. Friedman, J.L. Bentley, and R.A. Finkel. An algorithm for finding best matches in logarithmic expected time. A CM Transactions on Mathematical Software, 3(1977):209-226.

Digital Library

Google Scholar

[35]

A. Gersho and R.M. Gray. Vector Quantization and Data Compression. Kluwer, 1991.

Digital Library

Google Scholar

[36]

A. Gionis, P. Indyk, and R. Motwani. Similarity Search in High Dimensions via Hashing. Manuscript, 1997.

Google Scholar

[37]

D. Greene, M. Parnas, and F. Yao. Multi-index hashing for information retrieval. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 722-731.

Digital Library

Google Scholar

[38]

T. Hastie and R. Tibshirani. Discriminant adaptive nearest neighbor classification. In: First InternaSonal Conference on Knowledge Discovery f.4 Data Mining, 1995, pp. 142-149.

Google Scholar

[39]

H. HoteUing. Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 27( 1933):417-441.

Crossref

Google Scholar

[40]

P. Indyk, R. Motwani, and S. Venkatasubramanian. Geometric Matching Under Noise- Combinatorial Bounds and Algorithms. Manuscript, 1997.

Google Scholar

[41]

W.B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space. Contemporary Mathematics, 26(1984):189-206.

Crossref

Google Scholar

[42]

W.B. Jotmson and G. Schechtman. Embedding l~~ into l{'. Acta Mathematica, 149(1982):71-85.

Google Scholar

[43]

K. Karhunen. Uber lineare Methoden in dew Wahrscheinlichkeitsrechnung. Ann. Acad. Sci. Fennicae, Set. A137, 1947.

Google Scholar

[44]

V. Koivune and S. Kassam. Nearest neighbor filters for multivariate data. IEEE l'~rkshop on Nonlinear Signal and Image Processing, 1995.

Google Scholar

[45]

J. Kleinberg. Two Algorithms for Nearest-Neighbor Search in High Dimensions. In: Proceeding.~ of the Twenty. Ninth Annual A CM Symposium on Theory of Computing, 1997.

Digital Library

Google Scholar

[46]

E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. These proceedings.

Digital Library

Google Scholar

[47]

R.M. Karp, O. Waarts, and G. Zweig. The bit. vector intersection problem. In: Proceedings of 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, pp. 621-630.

Digital Library

Google Scholar

[48]

N. Linial, E. London, and Y. Rabinovich. The geomctry of graphs and some of its algorithmic appllcation~. In: Proceedings of 85th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 577-591.

Digital Library

Google Scholar

[49]

M. Loire. Fonctions aleastoires de second ordere. Processus Stochastiques et mouvcment Brownian, Hermann, Paris, 1948.

Google Scholar

[50]

J. Matou~ek. Reporting points in halfspacc~. In: Computational Geometry: Theory and Applications, 2(1992):169-186.

Digital Library

Google Scholar

[51]

S. Meiser. Point location in arrangements of hyperplanes. Information and Computation, 106( 1993):236-- 303.

Digital Library

Google Scholar

[52]

N. Megiddo. Applying parallel computation algorlthm~ in the design of serial algorithms. Journal of the A CM al(1983), pp. $52-865.

Digital Library

Google Scholar

[53]

M. Minsky and S. Papert. Perceptrona. MIT Prcs~, Cambridge, MA, 1969.

Google Scholar

[54]

R. Mot~wani and P. Raghavan. Randomized Aigorithma. Cambridge University Press, 1995.

Digital Library

Google Scholar

[55]

A. Pentland, R.W. Picard, and S. Sdaroff. Photobook: tools for content-based manipulation of image databases. In Proceedings of the SPiE Confercncc on Storage and Retrieval of Image and Vidco Databases II, 1994.

Crossref

Google Scholar

[56]

G. Pisier. The volume of convex bodies and Banach space geometry. Cambridge Universit4' Press, 1989.

Google Scholar

[57]

G. Salton and M.J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill Book Company, New York, NY, 1983.

Digital Library

Google Scholar

[58]

H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1989.

Digital Library

Google Scholar

[59]

T. SeUis, N. Roussopoulos and C. Faloutso.q. Multidimensional Access Methods: Trees Have Grown Everywhere. Proceedings of the ~3rd International Conference on Very Large Data Bases (VLDB), 1997, pp. 13-15.

Digital Library

Google Scholar

[60]

A.W.M. Smeulders and R. JaJn, eds. Image Databaaca and Multi-media Search. Proceedings of the First International Workshop, IDB-MIvIS '96, Amsterdam Unlversky Press, Amsterdam, 1996.

Google Scholar

[61]

J.K. Uhlm~. Satisfying General Pro.,dmity/Similarit.y Queries with Metric Trees. Information ProccaMng Letters, 40(1991):175-179.

Crossref

Google Scholar

[62]

P.N. YiannJlos. Data Structures and Algorithms for Nearest Neighbor Search in General Met. tic Spaces. In: Proceedings of the Second Annual A CM. SIAM Symposium on Discrete Algorithms, 1993, pp. 311-321.

Digital Library

Google Scholar

[63]

T. Welch. Bounds on the information retrieval efficiency of static file structures. Technical Report 88, MIT, June 1971.

Digital Library

Google Scholar

[64]

A.C. Yao and F.F. Yao, A general approach to ddimensional geometric queries. In: Proceedings of thc Seventeenth Annual A CM Symposium on Theory of Computing, 1985, pp. 163-168.

Digital Library

Google Scholar

Cited By

View all

Gou YGao JXu YLong C(2025)SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/37097303:1(1-26)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709730
Yin ZGao JBalsebre PCong GLong C(2025)DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation GraphProceedings of the ACM on Management of Data10.1145/37096793:1(1-28)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709679
Dalvi AHonavar VNejdl WAuer SKarras OCha MMoens MNajork M(2025)Hyperdimensional Representation Learning for Node Classification and Link PredictionProceedings of the Eighteenth ACM International Conference on Web Search and Data Mining10.1145/3701551.3703492(88-97)Online publication date: 10-Mar-2025
https://dl.acm.org/doi/10.1145/3701551.3703492
Show More Cited By

Index Terms

Approximate nearest neighbors: towards removing the curse of dimensionality
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

On Approximate Nearest Neighbors under l∞ Norm

The nearest neighbor search (NNS) problem is the following: Given a set of n points P={p1, , pn} in some metric space X, preprocess P so as to efficiently answer queries which require finding a point in P closest to a query point q X. The approximate ...
Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours
Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition

Many pattern recognition tasks make use of the k nearest neighbour (k-NN) technique. In this paper we are interested on fast k- NN search algorithms that can work in any metric space i.e. they are not restricted to Euclidean-like distance functions. ...
Improving Locality Sensitive Hashing by Efficiently Finding Projected Nearest Neighbors
Similarity Search and Applications
Abstract
Similarity search in high-dimensional spaces is an important task for many multimedia applications. Due to the notorious curse of dimensionality, approximate nearest neighbor techniques are preferred over exact searching techniques since they can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

May 1998

684 pages

ISBN:0897919629

DOI:10.1145/276698

Chairman:
Jeffrey Vitter

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC98

Sponsor:

SIGACT

STOC98: The 30th Annual ACM Symposium on Theory of Computing

May 24 - 26, 1998

Texas, Dallas, USA

Acceptance Rates

STOC '98 Paper Acceptance Rate 75 of 169 submissions, 44%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2,913
Total Citations
View Citations
16,313
Total Downloads

Downloads (Last 12 months)1,846
Downloads (Last 6 weeks)230

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gou YGao JXu YLong C(2025)SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/37097303:1(1-26)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709730
Yin ZGao JBalsebre PCong GLong C(2025)DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation GraphProceedings of the ACM on Management of Data10.1145/37096793:1(1-28)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709679
Dalvi AHonavar VNejdl WAuer SKarras OCha MMoens MNajork M(2025)Hyperdimensional Representation Learning for Node Classification and Link PredictionProceedings of the Eighteenth ACM International Conference on Web Search and Data Mining10.1145/3701551.3703492(88-97)Online publication date: 10-Mar-2025
https://dl.acm.org/doi/10.1145/3701551.3703492
Clementi AGualà LPepè Sciarria LStraziota ANejdl WAuer SKarras OCha MMoens MNajork M(2025)Maintaining k-MinHash Signatures over Fully-Dynamic Data Streams with RecoveryProceedings of the Eighteenth ACM International Conference on Web Search and Data Mining10.1145/3701551.3703491(79-87)Online publication date: 10-Mar-2025
https://dl.acm.org/doi/10.1145/3701551.3703491
Wu WLi SJiang MLuo CLi F(2025)Time- and Space-Efficiently Sketching Billion-Scale Attributed NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.350825637:2(966-978)Online publication date: Feb-2025
https://doi.org/10.1109/TKDE.2024.3508256
Huang TEl Gamal H(2025)Efficient Solvers for Wyner Common Information With Application to Multi-Modal ClusteringIEEE Transactions on Information Theory10.1109/TIT.2025.353228071:3(2054-2074)Online publication date: Mar-2025
https://doi.org/10.1109/TIT.2025.3532280
Liu MYang ZHan WXie S(2025)Cluster Guided Truncated Hashing for Enhanced Approximate Nearest Neighbor SearchIEEE Signal Processing Letters10.1109/LSP.2024.350933332(181-185)Online publication date: 2025
https://doi.org/10.1109/LSP.2024.3509333
Wu JWang YHsueh PYen C(2025)SIFT Based on MediaPipe to Identify Athletic Posture2025 Australian & New Zealand Control Conference (ANZCC)10.1109/ANZCC65042.2025.10873344(23-28)Online publication date: 30-Jan-2025
https://doi.org/10.1109/ANZCC65042.2025.10873344
Yang XLuo HNie XKong X(2025)Tacit knowledge-informed approximate dynamic programming for last-mile delivery operations in online-to-offline pharmaciesIndustrial Management & Data Systems10.1108/IMDS-09-2024-0874Online publication date: 28-Jan-2025
https://doi.org/10.1108/IMDS-09-2024-0874
Jin XSun BLi D(2025)Audio feature enhancement based on quaternion filtering and deep hashingNeurocomputing10.1016/j.neucom.2024.128727612(128727)Online publication date: Jan-2025
https://doi.org/10.1016/j.neucom.2024.128727
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On Approximate Nearest Neighbors under l∞ Norm

Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours

Improving Locality Sensitive Hashing by Efficiently Finding Projected Nearest Neighbors