DBScholar

Back to papers

A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces

Summary: Quantifies the dimensional curse: partitioning/clustering indexes become linear and lose to sequential scan beyond ~10 dimensions. Introduces VA-file, a compact vector-approximation organization that accelerates the unavoidable scan, outperforming R*- and X-trees experimentally. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h2bac67f6fc1b0b73
Venue
VLDB
Year
1998
Pagerank
0.00044967652
Overall Rank
45 | 99.71%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{weber_vldb98,
        title = {{A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces}},
        author = {Weber, Roger and Schek, Hans-J. and Blott, Stephen},
        journal = {PVLDB},
        series = {{VLDB} '98},
        pages = {194--205},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 100 citing papers.

Rank Citing Paper Year Venue Pagerank
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00057610161
75 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037163157
143 LOF: Identifying Density-Based Local Outliers 2000 SIGMOD 0.00029095978
229 Robust and Fast Similarity Search for Moving Object Trajectories 2005 SIGMOD 0.00023850907
281 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022262975
307 On The Marriage of Lp-norms and Edit Distance 2004 VLDB 0.00021496009
325 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020930941
335 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.0002067515
562 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00016344855
578 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016079505
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015142453
802 RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search 2024 SIGMOD 0.00013822222
837 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00013530806
925 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013026835
1,298 Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials 2004 SIGMOD 0.00011104678
1,311 Continuous Nearest Neighbor Search 2002 VLDB 0.00011063629
1,318 VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning 2020 VLDB 0.00011035606
1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.00010045437
1,641 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 9.9814769e-05
1,642 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 9.9812004e-05
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
1,928 ATLAS: A Probabilistic Algorithm for High Dimensional Similarity Search 2011 SIGMOD 9.3476482e-05
2,129 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 8.9877592e-05
2,293 FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems 2017 SIGMOD 8.6780858e-05
2,501 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.359489e-05
2,836 Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search 2025 SIGMOD 7.9410774e-05
2,879 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.8951769e-05
2,952 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8061763e-05
2,968 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.7879589e-05
3,025 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7214661e-05
3,118 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.6114853e-05
3,192 General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows 2002 SIGMOD 7.5334132e-05
3,244 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.479122e-05
3,330 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.406702e-05
3,342 FTW: Fast Similarity Search under the Time Warping Distance 2005 PODS 7.3874144e-05
3,425 Angle-based Space Partitioning for Efficient Parallel Skyline Computation 2008 SIGMOD 7.2968417e-05
3,516 Approximate Embedding-Based Subsequence Matching of Time Series 2008 SIGMOD 7.2220655e-05
3,646 Location-based Spatial Queries 2003 SIGMOD 7.1177166e-05
3,666 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.0975312e-05
3,774 On the Complexity of Inner Product Similarity Join 2016 PODS 7.0102162e-05
4,171 Inter-Media Hashing for Large-scale Retrieval from Heterogeneous Data Sources 2013 SIGMOD 6.7511262e-05
4,215 Top-k Publish-Subscribe for Social Annotation of News 2013 VLDB 6.7179506e-05
4,735 Maximum Inner Product is Query-Scaled Nearest Neighbor 2025 VLDB 6.4310678e-05
4,868 Permutation Search Methods are Efficient, Yet Faster Search is Possible 2015 VLDB 6.3593681e-05
4,873 Neighbor-Sensitive Hashing 2016 VLDB 6.3580715e-05
5,010 Indexing Large Human-Motion Databases 2004 VLDB 6.3030754e-05
5,227 Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere 2021 SIGMOD 6.2080477e-05
5,526 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 6.0804398e-05
5,737 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.9955855e-05
5,814 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 5.9684385e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0019892478
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011386412
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081207565
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045231517
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0004024707
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
350 The Query By Image Content (QBIC) System 1995 SIGMOD 0.0002018411
530 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016832286
1,143 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011810737
1,527 On the Analysis of Indexing Schemes 1997 PODS 0.00010326893
3,893 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9232481e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,521 Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search 2026 SIGMOD
2 650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
3 1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB
4 3,893 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD
5 812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD
6 6,760 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS
7 9,434 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB
8 8,844 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD
9 20 Similarity Search in High Dimensions via Hashing 1999 VLDB
10 14,124 What's Wrong with High-Dimensional Similarity Search? 2008 VLDB