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.0004503446
Overall Rank
45 | 99.70%
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
5,982 Query-Sensitive Embeddings 2005 SIGMOD 5.9276742e-05
6,181 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.8595125e-05
6,247 RC-Index: Diversifying Answers to Range Queries 2018 VLDB 5.8360766e-05
6,459 Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search 2025 SIGMOD 5.7771353e-05
6,596 PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories 2021 VLDB 5.7410544e-05
6,610 Similarity Search: A Matching Based Approach 2006 VLDB 5.7350971e-05
6,646 Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories 2010 SIGMOD 5.7218669e-05
6,740 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.6916981e-05
6,919 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 5.644237e-05
6,943 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.6380615e-05
7,264 Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search 2025 SIGMOD 5.5703557e-05
7,305 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 5.5586007e-05
7,329 Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search 2018 SIGMOD 5.5505604e-05
7,432 Cracking Vector Search Indexes 2025 VLDB 5.5292193e-05
7,593 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 5.4880197e-05
7,856 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 5.4399688e-05
8,818 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2700772e-05
8,849 VStream: A Distributed Streaming Vector Search System 2025 VLDB 5.2646236e-05
8,927 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.2559789e-05
9,288 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.2021887e-05
9,329 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.1923126e-05
9,412 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 5.1826275e-05
10,121 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 5.0771316e-05
10,206 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 5.059736e-05
10,425 CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation 2026 SIGMOD 4.9793485e-05
10,540 Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations 2026 SIGMOD 4.9793485e-05
10,551 Building Stateless Serverless Vector DBs via Block-based Data Partitioning 2026 SIGMOD 4.9793485e-05
10,677 RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search 2026 SIGMOD 4.9793485e-05
10,730 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.9793485e-05
10,753 An Experimental Evaluation of Hybrid Querying on Vectors 2026 VLDB 4.9793485e-05
10,827 Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization 2026 VLDB 4.9793485e-05
10,829 RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search 2026 VLDB 4.9793485e-05
10,874 BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector 2026 VLDB 4.9793485e-05
11,059 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.9793485e-05
11,088 On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space 2025 PODS 4.9793485e-05
11,652 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.9793485e-05
11,884 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 4.9793485e-05
12,041 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.9793485e-05
12,505 Effective Multi-Modal Retrieval based on Stacked Auto-Encoders 2014 VLDB 4.9793485e-05
12,579 QuEval: Beyond high-dimensional indexing à la carte 2013 VLDB 4.9793485e-05
12,662 Effective Data Co-Reduction for Multimedia Similarity Search 2011 SIGMOD 4.9793485e-05
12,713 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.9793485e-05
12,763 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.9793485e-05
12,991 HISA: A Query System Bridging The Semantic Gap For Large Image Databases 2006 VLDB 4.9793485e-05
12,994 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 4.9793485e-05
13,004 Indexing for Function Approximation 2006 VLDB 4.9793485e-05
13,046 Database-Inspired Search 2005 VLDB 4.9793485e-05
13,108 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.9793485e-05
13,153 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.9793485e-05
14,079 What's Wrong with High-Dimensional Similarity Search? 2008 VLDB -
Previous Page 2 / 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.001992968
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0008122792
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045337853
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040370171
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
353 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00020222998
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016880616
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011848523
1,527 On the Analysis of Indexing Schemes 1997 PODS 0.00010350889
3,887 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9458013e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,443 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,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB
4 3,887 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD
5 811 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD
6 6,740 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS
7 9,400 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB
8 8,818 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,079 What's Wrong with High-Dimensional Similarity Search? 2008 VLDB