Database Paper Browser

Back to papers

HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces

Summary: HD-Index proposes RDB-trees built on Hilbert keys for scalable, approximate kNN in massive high-dimensional data. Leaves store distances to reference objects, enabling distance-filter pruning; by applying triangular and Ptolemaic inequalities, it tightens lower bounds for billion-scale, 1000+‑dimensional workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
11793
Venue
VLDB
Year
2018
Pagerank
0.00014652858
Overall Rank
1,010 | 92.98%
DOI
10.14778/3204028.3204034

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank Citing Paper Year Venue Pagerank
212 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00033913475
770 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.00016917602
1,757 VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning 2020 VLDB 0.00010660932
2,435 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 8.8252237e-05
2,650 Detecting Logic Bugs of Join Optimizations in DBMS 2023 SIGMOD 8.3708191e-05
3,183 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 7.4228241e-05
3,225 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 7.3463484e-05
3,400 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 7.1405533e-05
4,731 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 5.966659e-05
5,551 LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System 2022 VLDB 5.4421769e-05
7,095 Dumpy: A Compact and Adaptive Index for Large Data Series Collections 2023 SIGMOD 4.8350023e-05
7,193 AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models 2025 SIGMOD 4.8039257e-05
7,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.792836e-05
7,316 Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes 2024 VLDB 4.7640297e-05
7,611 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 4.6964271e-05
7,654 LiteHST: A Tree Embedding based Method for Similarity Search 2023 SIGMOD 4.687476e-05
7,837 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 4.6379694e-05
8,439 Accelerating Graph Indexing for ANNS on Modern CPUs 2025 SIGMOD 4.5128946e-05
8,497 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 4.4981377e-05
8,712 ANN Softmax: Acceleration of Extreme Classification Training 2022 VLDB 4.4626362e-05
9,394 BigVectorBench: Heterogeneous Data Embedding and Compound Queries are Essential in Evaluating Vector Databases 2025 VLDB 4.3441378e-05
9,684 How to Design Robust Algorithms using Noisy Comparison Oracle 2021 VLDB 4.3047774e-05
9,822 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 4.2757088e-05
9,914 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 4.2561557e-05
10,052 Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study 2026 SIGMOD 4.1945683e-05
10,071 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
10,086 High-Throughput, Cost-Effective Billion-Scale Vector Search with a Single GPU 2026 SIGMOD 4.1945683e-05
10,154 Distribution-Aware Exploration for Adaptive HNSW Search 2026 SIGMOD 4.1945683e-05
10,187 On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations 2026 SIGMOD 4.1945683e-05
10,256 I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration 2026 VLDB 4.1945683e-05
10,260 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.1945683e-05
10,409 MicroNN: An On-device Disk-resident Updatable Vector Database 2025 SIGMOD 4.1945683e-05
10,602 Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates 2025 VLDB 4.1945683e-05
10,737 Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search 2025 VLDB 4.1945683e-05
11,340 Scalable Time Series Compound Infrastructure 2022 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
79 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056242144
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
400 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.0002427237
562 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00020091752
605 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.000193396
682 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018201541
709 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00017768547
867 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015792021
931 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00015238406
1,229 SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013157271
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
3,300 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2516103e-05
7,005 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8654221e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
575 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00019882723
9,025 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 4.4072367e-05
2,971 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7970531e-05
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05
2,107 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5330494e-05
867 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015792021
682 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018201541
1,183 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455596
8,562 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4937074e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636