The DOI matches its Crossref record; 51 of the 51 references it cites were found in a registry or an index.
Searching in metric spaces
Open accessAbstract
The problem of searching the elements of a set that are close to a given query element under some similarity criterion has a vast number of applications in many branches of computer science, from pattern recognition to textual and multimedia information retrieval. We are interested in the rather general case where the similarity criterion defines a metric space, instead of the more restricted case of a vector space. Many solutions have been proposed in different areas, in many cases without cross-knowledge. Because of this, the same ideas have been reconceived several times, and very different presentations have been given for the same approaches. We present some basic results that explain the intrinsic difficulty of the search problem. This includes a quantitative definition of the elusive concept of "intrinsic dimensionality." We also present a unified view of all the known proposals to organize metric spaces, so as to be able to understand them under a common framework. Most approaches turn out to be variations on a few different concepts. We organize those works in a taxonomy that allows us to devise new algorithms from combinations of concepts not noticed before because of the lack of communication between different communities. We present experiments validating our results and comparing the existing approaches. We finish with recommendations for practitioners and open questions for future development.
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
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Reinforcement Learning: An Introduction
(2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 24,496
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Baeza-Yates, R. A., & Ribeiro-Neto, B. A. (1999) · Cited by 11,505
Self-citationIntroduction to Modern Information Retrieval
Salton, G., & McGill, M. J. (1983) · Virtual Defense Library (Ministerio de Defensa) · Cited by 11,392
Reinforcement Learning: An Introduction
Johnson, J. D., Li, J., & Chen, Z. (2000) · Neurocomputing · doi:10.1016/s0925-2312(00)00324-6 · Cited by 8,414
Algorithms for Clustering Data
Sarle, W. S. (1990) · Technometrics · doi:10.1080/00401706.1990.10484648 · Cited by 7,865
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520
Introduction to Reinforcement Learning
Sutton, R. S., & Barto, A. G. (1998) · The MIT Press eBooks · Cited by 6,855
R-trees: a dynamic index structure for spatial searching
Guttman, A. (1984) · Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 · doi:10.1145/602259.602266 · Cited by 6,580
Introduction to modern information retrieval
Dillon, M. (1983) · Information Processing & Management · doi:10.1016/0306-4573(83)90062-6 · Cited by 5,909
Multivariate Data Analysis with Readings.
Rutherford, G. S. W., Hair, J. F., Anderson, R. E., & Tatham, R. L. (1988) · The Statistician · doi:10.2307/2348783 · Cited by 5,830
Multivariate Data Analysis with Readings.
Jolliffe, I. T., Hair, J. F., Anderson, R. E., & Tatham, R. L. (1988) · Journal of the Royal Statistical Society. Series A (Statistics in Society) · doi:10.2307/2983017 · Cited by 5,077
Pattern Classification and Scene Analysis
Thompson, M., Duda, R. O., & Hart, P. E. (1974) · Leonardo · doi:10.2307/1573081 · Cited by 4,495
Voronoi diagrams—a survey of a fundamental geometric data structure
Aurenhammer, F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116880 · Cited by 4,340
Information Retrieval: Data Structures and Algorithms
Frakes, W. B., & Baeza-Yates, R. A. (1992) · Cited by 2,757
Self-citationAn optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
The Quadtree and Related Hierarchical Data Structures
Samet, H. (1984) · ACM Computing Surveys · doi:10.1145/356924.356930 · Cited by 2,205
Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison
Sankoff, D., & Kruskal, J. B. (1983) · Medical Entomology and Zoology · Cited by 1,915
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces
Ciaccia, P., Patella, M., & Zezula, P. (1997) · Cited by 1,527
Roussopoulos, N., Kelley, S., & Vincent, F. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223794 · Cited by 1,402
Efficient and effective Querying by Image Content
Faloutsos, C., Barber, R., Flickner, M., Hafner, J., Niblack, W., Petkovic, D., & Equitz, W. (1994) · Journal of Intelligent Information Systems · doi:10.1007/bf00962238 · Cited by 1,249
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (2002) · Readings in Multimedia Computing and Networking · doi:10.1016/b978-155860651-7/50124-8 · Cited by 1,118
(1993) · doi:10.5555/313559.313789 · Cited by 998
Introduction to Computational Biology
Waterman, M. S. (1995) · Springer eBooks · doi:10.1007/978-1-4899-6846-3 · Cited by 960
Faloutsos, C., & Lin, K.-I. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223812 · Cited by 897
Böhm, C., Berchtold, S., & Keim, D. A. (2001) · ACM Computing Surveys · doi:10.1145/502807.502809 · Cited by 827
Satisfying general proximity / similarity queries with metric trees
Uhlmann, J. K. (1991) · Information Processing Letters · doi:10.1016/0020-0190(91)90074-r · Cited by 690
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 594
Near Neighbor Search in Large Metric Spaces
Brin, S. (1995) · Cited by 556
A Course in Density Estimation.
Jones, M. C., & Devroye, L. (1988) · Journal of the Royal Statistical Society. Series A (Statistics in Society) · doi:10.2307/2982771 · Cited by 503
Some approaches to best-match file searching
Burkhard, W. A., & Keller, R. M. (1973) · Communications of the ACM · doi:10.1145/362003.362025 · Cited by 413
Multidimensional Binary Search Trees in Database Applications
Bentley, J. L. (1979) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1979.234200 · Cited by 410
A survey on content-based retrieval for multimedia databases
Yoshitaka, A., & Ichikawa, T. (1999) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.755617 · Cited by 334
Distance-based indexing for high-dimensional metric spaces
Bozkaya, T., & Ozsoyoglu, M. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253345 · Cited by 332
Optimal Expected-Time Algorithms for Closest Point Problems
Bentley, J. L., Weide, B. W., & Yao, A. C.-C. (1980) · ACM Transactions on Mathematical Software · doi:10.1145/355921.355927 · Cited by 314
A simple algorithm for nearest neighbor search in high dimensions
Nene, S. A., & Nayar, S. K. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.615448 · Cited by 311
Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection
Brito, M. R., Chávez, E. L., Quiroz, A. J., & Yukich, J. E. (1997) · Statistics & Probability Letters · doi:10.1016/s0167-7152(96)00213-1 · Cited by 250
Self-citationCombining textual and visual cues for content-based image retrieval on the World Wide Web
La Cascia, M., Sethi, S., & Sclaroff, S. (2002) · Proceedings. IEEE Workshop on Content-Based Access of Image and Video Libraries (Cat. No.98EX173) · doi:10.1109/ivl.1998.694480 · Cited by 248
Beyond uniformity and independence
Faloutsos, C., & Kamel, I. (1994) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/182591.182593 · Cited by 239
A cost model for similarity queries in metric spaces
Ciaccia, P., Patella, M., & Zezula, P. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275495 · Cited by 194
Faloutsos, C., & Lin, K.-I. (1995) · ACM SIGMOD Record · doi:10.1145/568271.223812 · Cited by 190
Nearest Neighbor Queries in Metric Spaces
Clarkson, K. L. (1999) · Discrete & Computational Geometry · doi:10.1007/pl00009449 · Cited by 169
A fast branch & bound nearest neighbour classifier in metric spaces
Micó, L., Oncina, J., & Carrasco, R. C. (1996) · Pattern Recognition Letters · doi:10.1016/0167-8655(96)00032-3 · Cited by 108
The choice of reference points in best-match file searching
Shapiro, M. B. (1977) · Communications of the ACM · doi:10.1145/359581.359599 · Cited by 79
Introduction to Computational Biology: Maps, sequences and genomes
Waterman, M. S. (2018) · Chapman & Hall/CRC eBooks · doi:10.1201/9780203750131 · Cited by 71
Fast approximate string matching in a dictionary
(2002) · doi:10.1109/spire.1998.712978 · Cited by 68
Voronoi trees and clustering problems
Dehne, F., & Noltemeier, H. (1987) · Information Systems · doi:10.1016/0306-4379(87)90041-x · Cited by 61
Computational geometry: a retrospective
Chazelle, B. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195110 · Cited by 52
Locally lifting the curse of dimensionality for nearest neighbor search
Yianilos, P. N. (2002) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/059/08 · Cited by 33
Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract)
Yianilos, P. N. (2000) · doi:10.5555/338219.338273 · Cited by 26
Cited by
LOCI: fast outlier detection using the local correlation integral
Papadimitriou, S., Kitagawa, H., Gibbons, P. B., & Faloutsos, C. (2004) · Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405) · doi:10.1109/icde.2003.1260802 · Cited by 846
On The Marriage of Lp-norms and Edit Distance
Chen, L., & Ng, R. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50070-x · Cited by 774
Index-driven similarity search in metric spaces (Survey Article)
Hjaltason, G. R., & Samet, H. (2003) · ACM Transactions on Database Systems · doi:10.1145/958942.958948 · Cited by 439
Approximate nearest neighbor algorithm based on navigable small world graphs
Malkov, Y., Ponomarenko, A., Logvinov, A., & Krylov, V. (2014) · Information Systems · doi:10.1016/j.is.2013.10.006 · Cited by 419
CID: an efficient complexity-invariant distance for time series
Batista, G. E. A. P. A., Keogh, E. J., Tataw, O. M., & de Souza, V. M. A. (2014) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-013-0312-3 · Cited by 359
Metadata
- Authors
- Chávez, E., Navarro, G., Baeza-Yates, R., & Marroquín, J. L.
- Venue
- ACM Computing Surveys
- Published
- 2001-09
- Volume
- 33
- Issue
- 3
- Pages
- 273-321
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2038044292
- Cited by
- 1,246
- References
- 51
- FWCI
- 61.64
- Type
- journal article
- Language
- en
- Open access
- green
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.