DBScholar

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
11981
Venue
VLDB
Year
2018
Pagerank
0.00014829964
Overall Rank
705 | 95.17%
DOI
10.14778/3204028.3204034

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{arora_vldb18,
        title = {{HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces}},
        author = {Arora, Akhil and Sinha, Sakshi and Kumar, Piyush and Bhattacharya, Arnab},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {8},
        pages = {906--919},
        doi = {10.14778/3204028.3204034},
        url = {https://doi.org/10.14778/3204028.3204034},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank Citing Paper Year Venue Pagerank
93 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00034701237
398 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.00019194947
1,430 VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning 2020 VLDB 0.0001080902
2,010 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 9.3085202e-05
2,044 Detecting Logic Bugs of Join Optimizations in DBMS 2023 SIGMOD 9.2663577e-05
2,534 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 8.4561875e-05
2,572 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4027322e-05
2,734 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.190416e-05
3,240 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.6071649e-05
4,965 LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System 2022 VLDB 6.4241124e-05
5,653 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 6.1332953e-05
6,133 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 5.9654376e-05
6,148 Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes 2024 VLDB 5.9593368e-05
6,691 Dumpy: A Compact and Adaptive Index for Large Data Series Collections 2023 SIGMOD 5.8011086e-05
6,765 AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models 2025 SIGMOD 5.7808599e-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,166 Accelerating Graph Indexing for ANNS on Modern CPUs 2025 SIGMOD 5.6846045e-05
7,376 LiteHST: A Tree Embedding based Method for Similarity Search 2023 SIGMOD 5.6298131e-05
7,761 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 5.550467e-05
7,843 BigVectorBench: Heterogeneous Data Embedding and Compound Queries are Essential in Evaluating Vector Databases 2025 VLDB 5.5333312e-05
8,855 ANN Softmax: Acceleration of Extreme Classification Training 2022 VLDB 5.3573227e-05
9,163 Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study 2026 SIGMOD 5.3104846e-05
9,236 Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates 2025 VLDB 5.3016261e-05
9,407 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 5.2751121e-05
9,820 How to Design Robust Algorithms using Noisy Comparison Oracle 2021 VLDB 5.214913e-05
9,915 MicroNN: An On-device Disk-resident Updatable Vector Database 2025 SIGMOD 5.1955087e-05
9,919 Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search 2025 VLDB 5.1955087e-05
9,964 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 5.18753e-05
10,362 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 2026 SIGMOD 5.093636e-05
10,377 High-Throughput, Cost-Effective Billion-Scale Vector Search with a Single GPU 2026 SIGMOD 5.093636e-05
10,443 Distribution-Aware Exploration for Adaptive HNSW Search 2026 SIGMOD 5.093636e-05
10,476 On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations 2026 SIGMOD 5.093636e-05
10,544 I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration 2026 VLDB 5.093636e-05
10,548 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 5.093636e-05
11,538 Scalable Time Series Compound Infrastructure 2022 SIGMOD 5.093636e-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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
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
287 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022323585
332 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00020920444
369 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00019945234
580 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00016157635
581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016153395
690 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.0001492934
864 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013522522
990 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00012796562
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
2,979 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.8984588e-05
6,894 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.744549e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD
2 9,165 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB
3 1,934 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB
4 3,363 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD
5 2,158 What is the nearest neighbor in high dimensional spaces? 2000 VLDB
6 580 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB
7 581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
8 1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS
9 8,765 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD
10 21 Similarity Search in High Dimensions via Hashing 1999 VLDB