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
h956067ef3934eccc
Venue
VLDB
Year
2018
Pagerank
0.00015156941
Overall Rank
648 | 95.65%
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 38 of 38 citing papers.

Rank Citing Paper Year Venue Pagerank
74 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037145866
344 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.00020455839
1,325 VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning 2020 VLDB 0.00011016872
1,894 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 9.4129766e-05
1,930 Detecting Logic Bugs of Join Optimizations in DBMS 2023 SIGMOD 9.3522789e-05
2,264 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 8.7286407e-05
2,444 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4556406e-05
2,730 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0842027e-05
2,872 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.9191725e-05
4,347 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 6.6457039e-05
4,600 Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes 2024 VLDB 6.5055567e-05
4,987 LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System 2022 VLDB 6.3237807e-05
6,244 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 5.8355024e-05
6,612 Dumpy: A Compact and Adaptive Index for Large Data Series Collections 2023 SIGMOD 5.732933e-05
6,873 AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models 2025 SIGMOD 5.6572631e-05
6,921 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 5.641565e-05
7,006 Accelerating Graph Indexing for ANNS on Modern CPUs 2025 SIGMOD 5.6212001e-05
7,308 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 5.5559693e-05
7,337 Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates 2025 VLDB 5.5472184e-05
7,397 LiteHST: A Tree Embedding based Method for Similarity Search 2023 SIGMOD 5.5344479e-05
7,600 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 5.4854217e-05
8,007 BigVectorBench: Heterogeneous Data Embedding and Compound Queries are Essential in Evaluating Vector Databases 2025 VLDB 5.4066174e-05
8,265 Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study 2026 SIGMOD 5.3639904e-05
8,376 MicroNN: An On-device Disk-resident Updatable Vector Database 2025 SIGMOD 5.3422998e-05
9,006 ANN Softmax: Acceleration of Extreme Classification Training 2022 VLDB 5.2375792e-05
9,568 Distribution-Aware Exploration for Adaptive HNSW Search 2026 SIGMOD 5.154741e-05
10,013 How to Design Robust Algorithms using Noisy Comparison Oracle 2021 VLDB 5.0954911e-05
10,094 Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search 2025 VLDB 5.0783086e-05
10,125 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 5.0747281e-05
10,330 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 2026 SIGMOD 5.0322912e-05
10,585 High-Throughput, Cost-Effective Billion-Scale Vector Search with a Single GPU 2026 SIGMOD 4.9769913e-05
10,674 On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations 2026 SIGMOD 4.9769913e-05
10,736 I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration 2026 VLDB 4.9769913e-05
10,740 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.9769913e-05
10,839 RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search 2026 VLDB 4.9769913e-05
10,877 CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data 2026 VLDB 4.9769913e-05
10,883 BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector 2026 VLDB 4.9769913e-05
11,853 Scalable Time Series Compound Infrastructure 2022 SIGMOD 4.9769913e-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.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00045027197
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040363819
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034847854
278 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022310642
281 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022303081
297 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00021849337
338 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020600264
562 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00016350316
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016118297
674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00014886449
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013253709
927 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013028642
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6212318e-05
3,017 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7455245e-05
6,945 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.6357936e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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