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

arXiv: https://arxiv.org/abs/1804.06829 · HTML: https://mlsanity.com/paper/1804.06829/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2018.

## Built on by (most cited first, 8 of 8)

- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints](https://mlsanity.com/paper/2203.13601/) (2022)
- [Flashlight: Scalable Link Prediction with Effective Decoders](https://mlsanity.com/paper/2209.10100/) (2022)
- [MicroNN: An On-device Disk-resident Updatable Vector Database](https://mlsanity.com/paper/2504.05573/) (2025)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search](https://mlsanity.com/paper/2505.17152/) (2025)
- [UpANNS: Enhancing Billion-Scale ANNS Efficiency with Real-World PIM Architecture](https://mlsanity.com/paper/2410.23805/) (2024)
- [Experimental comparison of graph-based approximate nearest neighbor search algorithms on edge devices](https://mlsanity.com/paper/2411.14006/) (2024)

## Abstract (arXiv)

Nearest neighbor searching of large databases in high-dimensional spaces is inherently difficult due to the curse of dimensionality. A flavor of approximation is, therefore, necessary to practically solve the problem of nearest neighbor search. In this paper, we propose a novel yet simple indexing scheme, HD-Index, to solve the problem of approximate k-nearest neighbor queries in massive high-dimensional databases. HD-Index consists of a set of novel hierarchical structures called RDB-trees built on Hilbert keys of database objects. The leaves of the RDB-trees store distances of database objects to reference objects, thereby allowing efficient pruning using distance filters. In addition to triangular inequality, we also use Ptolemaic inequality to produce better lower bounds. Experiments on massive (up to billion scale) high-dimensional (up to 1000+) datasets show that HD-Index is effective, efficient, and scalable.