The DOI matches its Crossref record; 51 of the 51 references it cites were found in a registry or an index.
Index-driven similarity search in metric spaces (Survey Article)
Abstract
Similarity search is a very important operation in multimedia databases and other database applications involving complex objects, and involves finding objects in a data set S similar to a query object q , based on some similarity measure. In this article, we focus on methods for similarity search that make the general assumption that similarity is represented with a distance metric d . Existing methods for handling similarity search in this setting typically fall into one of two classes. The first directly indexes the objects based on distances (distance-based indexing), while the second is based on mapping to a vector space (mapping-based approach). The main part of this article is dedicated to a survey of distance-based indexing methods, but we also briefly outline how search occurs in mapping-based methods. We also present a general framework for performing search based on distances, and present algorithms for common types of queries that operate on an arbitrary "search hierarchy." These algorithms can be applied on each of the methods presented, provided a suitable search hierarchy is defined.
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
Artificial intelligence: a modern approach
(1995) · Choice Reviews Online · doi:10.5860/choice.33-1577 · Cited by 21,974
Identification of common molecular subsequences
Smith, T. F., & Waterman, M. S. (1981) · Journal of Molecular Biology · doi:10.1016/0022-2836(81)90087-5 · Cited by 9,940
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
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
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · Proceedings of the 1990 ACM SIGMOD international conference on Management of data · doi:10.1145/93597.98741 · Cited by 4,161
The Art of Computer Programming: Volume 3: Sorting and Searching
Knuth, D. E. (1973) · Cited by 3,955
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,813
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,380
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
Voronoi, G. (1908) · Journal für die reine und angewandte Mathematik (Crelles Journal) · doi:10.1515/crll.1908.134.198 · Cited by 2,248
Clustering to minimize the maximum intercluster distance
Gonzalez, T. F. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90224-5 · Cited by 1,717
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces
Ciaccia, P., Patella, M., & Zezula, P. (1997) · Cited by 1,527
The art of computer programming, volume 3: (2nd ed.) sorting and searching
Knuth, D. E. (1998) · Addison-Wesley Longman Publishing Co., Inc. eBooks · Cited by 1,421
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
Chávez, E., Navarro, G., Baeza-Yates, R., & Marroquín, J. L. (2001) · ACM Computing Surveys · doi:10.1145/502807.502808 · Cited by 1,246
Optimal aggregation algorithms for middleware
Fagin, R., Lotem, A., & Naor, M. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375567 · Cited by 1,086
(1993) · doi:10.5555/313559.313789 · Cited by 998
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (1995) · Combinatorica · doi:10.1007/bf01200757 · Cited by 952
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
A Branch and Bound Algorithm for Computing k-Nearest Neighbors
Fukunaga, K., & Narendra, P. M. (1975) · IEEE Transactions on Computers · doi:10.1109/t-c.1975.224297 · Cited by 736
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
Near Neighbor Search in Large Metric Spaces
Brin, S. (1995) · Very Large Data Bases · Cited by 656
Similarity indexing with the SS-tree
White, D. A., & Jain, R. (2002) · Proceedings of the Twelfth International Conference on Data Engineering · doi:10.1109/icde.1996.492202 · Cited by 635
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
Computer graphics: principles and practice (2nd ed.)
Foley, J. D., van Dam, A., Feiner, S., & Hughes, J. F. (1990) · Addison-Wesley Longman Publishing Co., Inc. eBooks · Cited by 498
Approximating polyhedra with spheres for time-critical collision detection
Hubbard, P. M. (1996) · ACM Transactions on Graphics · doi:10.1145/231731.231732 · Cited by 491
Optimal multi-step k-nearest neighbor search
Seidl, T., & Kriegel, H.-P. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276319 · Cited by 442
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
An Algorithm for Finding Nearest Neighbors
Friedman, J. H., Baskett, F., & Shustek, L. J. (1975) · IEEE Transactions on Computers · doi:10.1109/t-c.1975.224110 · Cited by 394
A cost model for nearest neighbor search in high-dimensional data space
Berchtold, S., Böhm, C., Keim, D. A., & Kriegel, H.-P. (1997) · Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/263661.263671 · Cited by 373
Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence
Boutilier, C. E., & Goldszmidt, M. (2000) · Cited by 359
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
Fast Nearest Neighbor Search in Medical Image Databases
Korn, F. R., Sidiropoulos, N., Faloutsos, C., Siegal, E., & Protopapas, Z. (2018) · University Libraries (University of Maryland) · doi:10.1184/r1/6605588 · Cited by 316
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
Searching in metric spaces by spatial approximation
Navarro, G. (2002) · The VLDB Journal The International Journal on Very Large Data Bases · doi:10.1007/s007780200060 · Cited by 272
Performance guarantees for hierarchical clustering
Dasgupta, S., & Long, P. M. (2005) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.10.006 · Cited by 234
Properties of embedding methods for similarity searching in metric spaces
Hjaltason, G. R., & Samet, H. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1195989 · Cited by 216
Self-citationThe hybrid tree: an index structure for high dimensional feature spaces
Chakrabarti, K., & Mehrotra, S. (1999) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1999.754960 · Cited by 207
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
The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data
Moore, A. (2000) · Cited by 152
Statistical models of video structure for content analysis and characterization
Vasconcelos, N. M., & Lippman, A. (2000) · IEEE Transactions on Image Processing · doi:10.1109/83.817595 · Cited by 133
Hierarchical browsing and search of large image databases
Chen, J.-Y., Bouman, C. A., & Dalton, J. C. (2000) · IEEE Transactions on Image Processing · doi:10.1109/83.826781 · Cited by 127
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
Vidal, E. (1994) · Pattern Recognition Letters · doi:10.1016/0167-8655(94)90094-9 · Cited by 92
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
Evaluating a class of distance-mapping algorithms for data mining and clustering
Wang, J. T.-L., Wang, X., Lin, K.-I., et al. (1999) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/312129.312264 · Cited by 78
A Nearest Trajectory Strategy for Time Series Prediction
McNames, J. (2000) · 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
WINNING ENTRY OF THE K. U. LEUVEN TIME-SERIES PREDICTION COMPETITION
McNames, J., Suykens, J. A. K., & Vandewalle, J. P. L. (1999) · International Journal of Bifurcation and Chaos · doi:10.1142/s0218127499001048 · Cited by 39
Cited by
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
A Complexity-Invariant Distance Measure for Time Series
Batista, G. E. A. P. A., Wang, X., & Keogh, E. J. (2011) · Proceedings of the 2011 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972818.60 · Cited by 329
Boyack, K. W., Newman, D., Duhon, R. J., Klavans, R., Patek, M., Biberstine, J. R., Schijvenaars, B., Skupin, A., Ma, N., & Börner, K. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018029 · Cited by 271
Metadata
- Authors
- Hjaltason, G. R., & Samet, H.
- Venue
- ACM Transactions on Database Systems
- Published
- 2003-12
- Volume
- 28
- Issue
- 4
- Pages
- 517-580
- ISSN
- 0362-5915 (ISSN-L)
- 1557-4644
- OpenAlex
- W2065528935
- Cited by
- 439
- References
- 51
- Type
- paratext
- 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.