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
8489
Venue
VLDB
Year
1998
Pagerank
0.00056385781
Overall Rank
78 | 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,316 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1098143e-05
6,359 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.0912204e-05
6,375 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 5.0868008e-05
6,388 Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories 2010 SIGMOD 5.079988e-05
7,006 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8606861e-05
7,083 RC-Index: Diversifying Answers to Range Queries 2018 VLDB 4.8331444e-05
7,255 Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search 2018 SIGMOD 4.7821026e-05
7,790 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 4.6458343e-05
7,843 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 4.6335219e-05
7,848 Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search 2025 SIGMOD 4.6323445e-05
8,419 Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search 2025 SIGMOD 4.5119865e-05
8,484 Maximum Inner Product is Query-Scaled Nearest Neighbor 2025 VLDB 4.4956257e-05
8,495 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 4.4938255e-05
8,559 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4893996e-05
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
8,759 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 4.4520434e-05
8,890 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4235206e-05
9,026 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 4.4030177e-05
9,092 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 4.3934714e-05
9,821 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 4.2716118e-05
9,863 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 4.2636378e-05
9,880 VStream: A Distributed Streaming Vector Search System 2025 VLDB 4.2602815e-05
9,913 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 4.2520778e-05
10,042 Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations 2026 SIGMOD 4.1905499e-05
10,058 Building Stateless Serverless Vector DBs via Block-based Data Partitioning 2026 SIGMOD 4.1905499e-05
10,201 RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search 2026 SIGMOD 4.1905499e-05
10,260 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.1905499e-05
10,284 An Experimental Evaluation of Hybrid Querying on Vectors 2026 VLDB 4.1905499e-05
10,326 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.1905499e-05
10,363 On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space 2025 PODS 4.1905499e-05
10,718 Cracking Vector Search Indexes 2025 VLDB 4.1905499e-05
11,131 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.1905499e-05
11,380 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 4.1905499e-05
11,545 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.1905499e-05
12,024 Effective Multi-Modal Retrieval based on Stacked Auto-Encoders 2014 VLDB 4.1905499e-05
12,099 QuEval: Beyond high-dimensional indexing a la carte 2013 VLDB 4.1905499e-05
12,184 Effective Data Co-Reduction for Multimedia Similarity Search 2011 SIGMOD 4.1905499e-05
12,235 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1905499e-05
12,285 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.1905499e-05
12,517 HISA: A Query System Bridging The Semantic Gap For Large Image Databases 2006 VLDB 4.1905499e-05
12,520 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 4.1905499e-05
12,530 Indexing for Function Approximation 2006 VLDB 4.1905499e-05
12,572 Database-Inspired Search 2005 VLDB 4.1905499e-05
12,634 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.1905499e-05
12,679 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.1905499e-05
13,581 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.0032118946
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018380955
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00051785122
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
301 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028396714
331 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00027199905
479 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00022182486
1,111 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.0001389881
1,485 On the Analysis of Indexing Schemes 1997 PODS 0.00011698762
3,549 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9792126e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,541 Similarity search in the blink of an eye with compressed indices 2023 VLDB 6.9910982e-05
1,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
1,923 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010079134
3,549 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9792126e-05
821 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00016232579
6,316 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1098143e-05
9,288 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 4.3589837e-05
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554
13,581 What's Wrong with High-Dimensional Similarity Search? 2008 VLDB -