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)
Incoming Non-self Citations Over Time
Authors
- 1. Akhil Arora (EPFL)
- 2. Sakshi Sinha (Fresh Gravity Inc.)
- 3. Piyush Kumar (Visa Inc.)
- 4. Arnab Bhattacharya (Indian Institute of Technology Kanpur)
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.
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.
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,329 | Dimensional Testing for Reverse k-Nearest Neighbor Search | 2017 | VLDB |
| 3 | 1,625 | Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces | 2023 | VLDB |
| 4 | 3,325 | Efficient k-NN Search on Vertically Decomposed Data | 2002 | SIGMOD |
| 5 | 2,113 | What is the nearest neighbor in high dimensional spaces? | 2000 | VLDB |
| 6 | 562 | SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index | 2015 | VLDB |
| 7 | 576 | Quality and Efficiency in High Dimensional Nearest Neighbor Search | 2009 | SIGMOD |
| 8 | 1,157 | A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space | 1997 | PODS |
| 9 | 8,927 | Contorting High Dimensional Data for Efficient Main Memory KNN Processing | 2003 | SIGMOD |
| 10 | 20 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB |