The DOI matches its Crossref record; 64 of the 64 references it cites were found in a registry or an index.
Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases
Open accessAbstract
During the last decade, multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. An important research issue in the field of multimedia databases is the content-based retrieval of similar multimedia objects such as images, text, and videos. However, in contrast to searching data in a relational database, a content-based retrieval requires the search of similar objects as a basic functionality of the database system. Most of the approaches addressing similarity search use a so-called feature transformation that transforms important properties of the multimedia objects into high-dimensional points (feature vectors). Thus, the similarity search is transformed into a search of points in the feature space that are close to a given query point in the high-dimensional feature space. Query processing in high-dimensional spaces has therefore been a very active research area over the last few years. A number of new index structures and algorithms have been proposed. It has been shown that the new index structures considerably improve the performance in querying large multimedia databases. Based on recent tutorials [Berchtold and Keim 1998], in this survey we provide an overview of the current state of the art in querying multimedia databases, describing the index structures and algorithms for an efficient query processing in high-dimensional spaces. We identify the problems of processing queries in high-dimensional space, and we provide an overview of the proposed approaches to overcome these problems.
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
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
The Fractal Geometry of Nature
Mandelbrot, B. B., & Wheeler, J. A. (1983) · American Journal of Physics · doi:10.1119/1.13295 · Cited by 21,832
The Fractal Geometry of Nature.
Sparrow, C., & Mandelbrot, B. (1984) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2981858 · Cited by 14,546
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
(1999) · Cited by 3,186
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
Automatic subspace clustering of high dimensional data for data mining applications
Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276314 · Cited by 2,412
When Is ''Nearest Neighbor'' Meaningful?
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49257-7_15 · Cited by 2,403
Quad trees a data structure for retrieval on composite keys
Finkel, R. A., & Bentley, J. L. (1974) · Acta Informatica · doi:10.1007/bf00288933 · Cited by 2,041
Efficient similarity search in sequence databases
Agrawal, R., Faloutsos, C., & Swami, A. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-57301-1_5 · Cited by 1,979
Comer, D. (1979) · ACM Computing Surveys · doi:10.1145/356770.356776 · Cited by 1,859
Fast subsequence matching in time-series databases
Faloutsos, C., Ranganathan, M., & Manolopoulos, Y. (1994) · Proceedings of the 1994 ACM SIGMOD international conference on Management of data · doi:10.1145/191839.191925 · Cited by 1,709
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
Sagan, H. (1994) · Universitext · doi:10.1007/978-1-4612-0871-6 · Cited by 1,336
Techniques for automatically correcting words in text
Kukich, K. (1992) · ACM Computing Surveys · doi:10.1145/146370.146380 · Cited by 1,257
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
An efficient approach to clustering in large multimedia databases with noise
Hinneburg, A., & Keim, D. A. (1998) · KOPS (University of Konstanz) · Cited by 1,181
Self-citationBerchtold, 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
Self-citation(1993) · doi:10.5555/313559.313789 · Cited by 998
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
The K-D-B-tree: a search structure for large multidimensional dynamic indexes
Robinson, J. T. (1981) · Proceedings of the 1981 ACM SIGMOD international conference on Management of data - SIGMOD '81 · doi:10.1145/582318.582321 · Cited by 888
The SR-tree: an index structure for high-dimensional nearest neighbor queries
Katayama, N., & Satoh, S. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253347 · Cited by 817
Fractals, chaos, power laws: minutes from an infinite paradise
(1992) · Choice Reviews Online · doi:10.5860/choice.29-2770 · Cited by 811
The Art of Computer Programming, Volume 3, Sorting and Searching
Wilkes, M. V. (1974) · The Computer Journal · doi:10.1093/comjnl/17.4.324 · Cited by 707
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
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases
Agrawal, R., Lin, K.-I., Sawhney, H., & Shim, K. (1995) · Cited by 649
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
Near Neighbor Search in Large Metric Spaces
Brin, S. (1995) · Cited by 556
Influence sets based on reverse nearest neighbor queries
Korn, F. R., & Muthukrishnan, S. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335415 · Cited by 534
The TV-tree: An index structure for high-dimensional data
Lin, K.-I., Jagadish, H. V., & Faloutsos, C. (1994) · The VLDB Journal · doi:10.1007/bf01231606 · Cited by 494
Molecular docking using shape descriptors
Shoichet, B. K., Kuntz, I. D., & Bodian, D. L. (1992) · Journal of Computational Chemistry · doi:10.1002/jcc.540130311 · Cited by 425
The X Tree: An Index Structure for High Dimensional Data
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (1996) · KOPS (University of Konstanz) · Cited by 414
Self-citationSome 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
Berchtold, S., Böhm, C., & Kriegal, H.-P. (1998) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/276304.276318 · Cited by 402
Self-citationA 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
Self-citationRefinements to nearest-neighbor searching ink-dimensional trees
Sproull, R. F. (1991) · Algorithmica · doi:10.1007/bf01759061 · Cited by 349
A Dynamic Index Structure for Spatial Searching
Guttman, A. (1984) · Medical Entomology and Zoology · 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
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
Independent quantization: an index compression technique for high-dimensional data spaces
Berchtold, S., Bohm, C., Jagadish, H. V., Kriegel, H.-P., & Sander, J. (2002) · Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073) · doi:10.1109/icde.2000.839456 · Cited by 291
Self-citationActive Storage for Large-Scale Data Mining and Multimedia
Riedel, E., Gibson, G. A., & Faloutsos, C. (1998) · Cited by 270
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
Closest pair queries in spatial databases
Corral, A., Manolopoulos, Y., Theodoridis, Y., & Vassilakopoulos, M. G. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335414 · Cited by 225
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
Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension
Belussi, A., & Faloutsos, C. (2018) · University Libraries (University of Maryland) · doi:10.1184/r1/6605282 · Cited by 173
Fast parallel similarity search in multimedia databases
Berchtold, S., Böhm, C., Braunmüller, B., Keim, D. A., & Kriegel, H.-P. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253263 · Cited by 168
Self-citationSimilarity indexing: algorithms and performance:
White, D. A., & Jain, R. C. (1996) · SPIE Proceedings · doi:10.1117/12.234810 · Cited by 162
Fast nearest neighbor search in high-dimensional space
Berchtold, S., Ertl, B., Keim, D. A., et al. (2002) · Proceedings - International Conference on Data Engineering · doi:10.1109/icde.1998.655779 · Cited by 155
Self-citationOn the analysis of indexing schemes
Hellerstein, J. M., Koutsoupias, E., & Papadimitriou, C. H. (1997) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/263661.263688 · Cited by 146
A general approach to d-dimensional geometric queries
Yao, A. C.-C., & Yao, F. F. (1985) · doi:10.1145/22145.22163 · Cited by 144
Fractals, chaos, power laws: Minutes from an infinite paradise
Abraham, R. (1994) · Journal of Economic Dynamics and Control · doi:10.1016/0165-1889(94)90045-0 · Cited by 111
The LSD/sup h/-tree: an access structure for feature vectors
Henrich, A. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1998.655799 · Cited by 86
Feature-based retrieval of similar shapes
Mehrotra, R., & Gary, J. E. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1993.344072 · Cited by 82
Ip, L., JagadishH., V., & FaloutsosChristos (1994) · Very Large Data Bases · doi:10.5555/615204.615210 · Cited by 53
Accounting for boundary effects in nearest neighbor searching
Arya, S., Mount, D. M., & Narayan, O. (1995) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/220279.220315 · Cited by 43
Nearest neighbor searching and applications
Arya, S. (1996) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 41
High-dimensional index structures database support for next decade's applications (tutorial)
Berchtold, S., & Keim, D. A. (1998) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/276304.276353 · Cited by 36
Self-citationAnalysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension
Faloutsos, C., & Gaede, V. (2018) · Figshare · doi:10.1184/r1/6603476 · Cited by 33
Cited by
Image retrieval: Ideas, influences, and trends of the new age
Datta, R., Joshi, D., Li, J., & Wang, J. Z. (2008) · ACM Computing Surveys · doi:10.1145/1348246.1348248 · Cited by 3,040
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
“Nearest neighbor search is inherently expensive due to the curse of dimensionality [3], [4].”
BackgroundChávez, E., Navarro, G., Baeza-Yates, R., & Marroquín, J. L. (2001) · ACM Computing Surveys · doi:10.1145/502807.502808 · Cited by 1,246
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
A survey on unsupervised outlier detection in high‐dimensional numerical data
Zimek, A., Schubert, E., & Kriegel, H. (2012) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.11161 · Cited by 864
Metadata
- Authors
- Böhm, C., Berchtold, S., & Keim, D. A.
- Venue
- ACM Computing Surveys
- Published
- 2001-09
- Volume
- 33
- Issue
- 3
- Pages
- 322-373
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2124222502
- Cited by
- 827
- References
- 64
- FWCI
- 46.50
- 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.