A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces
Explore this paper's citation graph
Summary
It is shown formally that partitioning and clustering techniques for similarity search in HDVSs exhibit linear complexity at high dimensionality, and that existing methods are outperformed on average by a simple sequential scan if the number of dimensions exceeds around 10.
- Type
- article
- Published
- 1998-08-24
- Cited by
- 1,859
- References
- 40
- OpenAlex
- https://openalex.org/W1541459201
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:8109758
Keywords
Curse of dimensionality, Computer science, Cluster analysis, Similarity (geometry), Simple (philosophy)
References
- Query by Image and Video Content
- Searching Multimedia Databases by Content
- Information extraction by local density analysis
- Similarity of color images
- Principles of database and knowledge-base systems, Vol. I
- An Algorithm for Finding Best Matches in Logarithmic Expected Time
- On the analysis of indexing schemes
- Multi-step processing of spatial joins
- Description and performance analysis of signature file methods for office filing
- The K-D-B-tree: a search structure for large multidimensional dynamic indexes
- Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space
- Access methods for text
- Multiattribute hashing using Gray codes
- Data Structures for Range Searching
- A cost model for nearest neighbor search in high-dimensional data space
- Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension
- The hB-tree: a multiattribute indexing method with good guaranteed performance
- R-trees: a dynamic index structure for spatial searching
- Comparison of approximations of complex objects used for approximation-based query processing in spatial database systems
- Fast parallel similarity search in multimedia databases
Cited by
- Text and content based image retrieval via locality sensitive hashing
- Generalized Density-Based Clustering for Spatial Data Mining (Abstract)
- Density-based clustering in large databases using projections and visualizations
- Kpyr, une structure efficace d'indexation de documents vidéo
- Using Multi-Scale Histograms to Answer Pattern Existence and Shape Match Queries
- The development of health care data warehouses to support data mining.
- Optimal Distance Bounds on Time-Series Data
- Hyperdatenbanken zur Verwaltung von Informationsräumen (Hyperdatabases for Managing Information Spaces)
- Das HERON-Projekt - Ein Zwischenbericht
- A Distributed Image-Database Architecture for Efficient Insertion and Retrieval
- Matching Slides to Presentation Videos
- Content-Based Image Retrieval: Theory and Applications
- Improving Probabilistic Roadmap Methods for Fast Motion Planning ; Reitinsuunnittelun nopeuttaminen reittikarttamenetelmiä parantamalla
- Classifications, Problems Identification and a New Approach
- Algorithmic Approaches to Statistical Questions
- Ein Ansatz zur Übertragung von Rangordnungen bei der Suche auf strukturierten Daten
- Improving Query Performance through Application-Driven Processing and Retrieval
- Physical Data Modeling for Multidimensional Access Methods
- Data Analysis, Machine Learning, and Applications
- Hashing-basierte Indizierung: Anwendungsszenarien, Theorie und Methoden
Related papers
- Multidimensional binary search trees used for associative searching
- Locality-sensitive hashing scheme based on p-stable distributions
- M-tree: An Efficient Access Method for Similarity Search in Metric Spaces
- Similarity indexing with the SS-tree
- The R*-tree: an efficient and robust access method for points and rectangles
- Approximate nearest neighbors
- The SR-tree: an index structure for high-dimensional nearest neighbor queries
- The pyramid-technique: towards breaking the curse of dimensionality
- Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases