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
5,991 Query-Sensitive Embeddings 2005 SIGMOD 5.9060962e-05
6,076 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.8774917e-05
6,262 RC-Index: Diversifying Answers to Range Queries 2018 VLDB 5.8140253e-05
6,475 Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search 2025 SIGMOD 5.7553067e-05
6,605 PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories 2021 VLDB 5.719368e-05
6,623 Similarity Search: A Matching Based Approach 2006 VLDB 5.7134273e-05
6,656 Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories 2010 SIGMOD 5.7034822e-05
6,760 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.6706378e-05
6,941 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 5.6229105e-05
6,962 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.6181217e-05
7,286 Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search 2025 SIGMOD 5.5493084e-05
7,326 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 5.5375978e-05
7,349 Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search 2018 SIGMOD 5.5301663e-05
7,456 Cracking Vector Search Indexes 2025 VLDB 5.5083275e-05
7,616 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 5.4672835e-05
7,876 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 5.4194298e-05
8,844 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2501688e-05
8,880 VStream: A Distributed Streaming Vector Search System 2025 VLDB 5.2447315e-05
8,955 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.2361195e-05
9,321 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.1825641e-05
9,364 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.1726938e-05
9,446 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 5.1630452e-05
10,162 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 5.0579479e-05
10,248 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 5.0412958e-05
10,503 CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation 2026 SIGMOD 4.9605343e-05
10,616 Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations 2026 SIGMOD 4.9605343e-05
10,626 Building Stateless Serverless Vector DBs via Block-based Data Partitioning 2026 SIGMOD 4.9605343e-05
10,749 RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search 2026 SIGMOD 4.9605343e-05
10,801 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.9605343e-05
10,824 An Experimental Evaluation of Hybrid Querying on Vectors 2026 VLDB 4.9605343e-05
10,898 Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization 2026 VLDB 4.9605343e-05
10,900 RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search 2026 VLDB 4.9605343e-05
10,944 BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector 2026 VLDB 4.9605343e-05
11,129 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.9605343e-05
11,158 On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space 2025 PODS 4.9605343e-05
11,705 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.9605343e-05
11,934 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 4.9605343e-05
12,091 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.9605343e-05
12,554 Effective Multi-Modal Retrieval based on Stacked Auto-Encoders 2014 VLDB 4.9605343e-05
12,628 QuEval: Beyond high-dimensional indexing à la carte 2013 VLDB 4.9605343e-05
12,711 Effective Data Co-Reduction for Multimedia Similarity Search 2011 SIGMOD 4.9605343e-05
12,762 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.9605343e-05
12,812 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.9605343e-05
13,039 HISA: A Query System Bridging The Semantic Gap For Large Image Databases 2006 VLDB 4.9605343e-05
13,042 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 4.9605343e-05
13,052 Indexing for Function Approximation 2006 VLDB 4.9605343e-05
13,094 Database-Inspired Search 2005 VLDB 4.9605343e-05
13,155 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.9605343e-05
13,200 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.9605343e-05
14,124 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.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