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
8679
Venue
VLDB
Year
1998
Pagerank
0.00044853085
Overall Rank
46 | 99.69%
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 47 of 97 citing papers.

Rank Citing Paper Year Venue Pagerank
6,093 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.978635e-05
6,472 PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories 2021 VLDB 5.8700652e-05
6,483 Similarity Search: A Matching Based Approach 2006 VLDB 5.8667204e-05
6,597 Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories 2010 SIGMOD 5.8280739e-05
6,646 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.8148791e-05
6,851 Maximum Inner Product is Query-Scaled Nearest Neighbor 2025 VLDB 5.7546877e-05
6,894 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.744549e-05
7,119 RC-Index: Diversifying Answers to Range Queries 2018 VLDB 5.6971547e-05
7,124 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 5.6961208e-05
7,145 Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search 2025 SIGMOD 5.6908957e-05
7,240 Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search 2018 SIGMOD 5.6643589e-05
7,259 Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search 2025 SIGMOD 5.6613405e-05
7,708 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 5.5628618e-05
7,761 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 5.550467e-05
8,655 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.3910353e-05
8,765 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.3766157e-05
8,898 Cracking Vector Search Indexes 2025 VLDB 5.3495662e-05
9,115 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.3215443e-05
9,165 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.3101672e-05
9,238 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 5.3015807e-05
9,407 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 5.2751121e-05
9,964 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 5.18753e-05
10,017 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 5.1758281e-05
10,036 VStream: A Distributed Streaming Vector Search System 2025 VLDB 5.173224e-05
10,209 CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation 2026 SIGMOD 5.093636e-05
10,336 Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations 2026 SIGMOD 5.093636e-05
10,350 Building Stateless Serverless Vector DBs via Block-based Data Partitioning 2026 SIGMOD 5.093636e-05
10,490 RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search 2026 SIGMOD 5.093636e-05
10,548 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 5.093636e-05
10,571 An Experimental Evaluation of Hybrid Querying on Vectors 2026 VLDB 5.093636e-05
10,612 Index Intersection for High-Dimensional Range Queries 2026 VLDB 5.093636e-05
10,645 On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space 2025 PODS 5.093636e-05
11,334 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 5.093636e-05
11,576 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 5.093636e-05
11,738 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 5.093636e-05
12,214 Effective Multi-Modal Retrieval based on Stacked Auto-Encoders 2014 VLDB 5.093636e-05
12,288 QuEval: Beyond high-dimensional indexing à la carte 2013 VLDB 5.093636e-05
12,371 Effective Data Co-Reduction for Multimedia Similarity Search 2011 SIGMOD 5.093636e-05
12,422 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 5.093636e-05
12,472 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 5.093636e-05
12,701 HISA: A Query System Bridging The Semantic Gap For Large Image Databases 2006 VLDB 5.093636e-05
12,704 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 5.093636e-05
12,714 Indexing for Function Approximation 2006 VLDB 5.093636e-05
12,756 Database-Inspired Search 2005 VLDB 5.093636e-05
12,818 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 5.093636e-05
12,863 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 5.093636e-05
13,768 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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00082404462
42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00046170812
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040719947
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
353 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00020370587
522 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00017133516
1,129 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00012061727
1,512 On the Analysis of Indexing Schemes 1997 PODS 0.00010536001
3,866 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 7.061829e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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