Database Paper Browser

Back to papers

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

Summary: Formal analysis shows HDVS partitioning methods have linear complexity and degrade beyond ~10 dimensions; sequential scans often win. It proposes VA-file, an approximate vector-encoding, comparing with R*-tree and X-tree, and shows near-sequential speed. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8488
Venue
VLDB
Year
1998
Pagerank
0.00056242144
Overall Rank
79 | 99.46%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 46 of 96 citing papers.

Rank Citing Paper Year Venue Pagerank
6,325 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1105081e-05
6,360 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.0961051e-05
6,376 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 5.0916875e-05
6,399 Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories 2010 SIGMOD 5.0818596e-05
7,005 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8654221e-05
7,101 RC-Index: Diversifying Answers to Range Queries 2018 VLDB 4.8322751e-05
7,301 Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search 2018 SIGMOD 4.768971e-05
7,791 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 4.6502309e-05
7,837 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 4.6379694e-05
7,843 Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search 2025 SIGMOD 4.6367909e-05
8,425 Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search 2025 SIGMOD 4.5163161e-05
8,485 Maximum Inner Product is Query-Scaled Nearest Neighbor 2025 VLDB 4.4999394e-05
8,497 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 4.4981377e-05
8,562 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4937074e-05
8,647 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4768766e-05
8,763 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 4.456315e-05
8,889 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4278238e-05
9,025 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 4.4072367e-05
9,096 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 4.3974472e-05
9,822 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 4.2757088e-05
9,864 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 4.2675822e-05
9,881 VStream: A Distributed Streaming Vector Search System 2025 VLDB 4.2643674e-05
9,914 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 4.2561557e-05
10,042 Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations 2026 SIGMOD 4.1945683e-05
10,058 Building Stateless Serverless Vector DBs via Block-based Data Partitioning 2026 SIGMOD 4.1945683e-05
10,201 RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search 2026 SIGMOD 4.1945683e-05
10,260 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.1945683e-05
10,273 An Experimental Evaluation of Hybrid Querying on Vectors 2026 VLDB 4.1945683e-05
10,314 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.1945683e-05
10,351 On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space 2025 PODS 4.1945683e-05
10,711 Cracking Vector Search Indexes 2025 VLDB 4.1945683e-05
11,128 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.1945683e-05
11,378 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 4.1945683e-05
11,541 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.1945683e-05
12,016 Effective Multi-Modal Retrieval based on Stacked Auto-Encoders 2014 VLDB 4.1945683e-05
12,091 QuEval: Beyond high-dimensional indexing a la carte 2013 VLDB 4.1945683e-05
12,176 Effective Data Co-Reduction for Multimedia Similarity Search 2011 SIGMOD 4.1945683e-05
12,227 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1945683e-05
12,277 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.1945683e-05
12,508 HISA: A Query System Bridging The Semantic Gap For Large Image Databases 2006 VLDB 4.1945683e-05
12,511 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 4.1945683e-05
12,521 Indexing for Function Approximation 2006 VLDB 4.1945683e-05
12,563 Database-Inspired Search 2005 VLDB 4.1945683e-05
12,625 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.1945683e-05
12,670 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.1945683e-05
13,568 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.0032169493
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018397217
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0005181666
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
284 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028994728
330 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00027229588
478 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.0002222104
1,114 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00013901031
1,488 On the Analysis of Indexing Schemes 1997 PODS 0.00011699446
3,555 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9772546e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,609 Similarity search in the blink of an eye with compressed indices 2023 VLDB 6.9215236e-05
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
3,555 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9772546e-05
825 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00016228517
6,325 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1105081e-05
9,283 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 4.3631652e-05
8,647 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4768766e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
13,568 What's Wrong with High-Dimensional Similarity Search? 2008 VLDB -