# Fast k-Nearest Neighbour Search via Prioritized DCI

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2017.

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

- [IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUs](https://mlsanity.com/paper/2405.02842/) (2024)
- [Rejection Sampling IMLE: Designing Priors for Better Few-Shot Image Synthesis](https://mlsanity.com/paper/2409.17439/) (2024)
- [IceCache: Memory-efficient KV-cache Management for Long-Sequence LLMs](https://mlsanity.com/paper/2604.10539/) (2026)
- [How Good Are Deep Generative Models for Solving Inverse Problems?](https://mlsanity.com/paper/2312.12691/) (2023)
- [A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search](https://mlsanity.com/paper/2609.02143/) (2026)

## Abstract (arXiv)

Most exact methods for k-nearest neighbour search suffer from the curse of dimensionality; that is, their query times exhibit exponential dependence on either the ambient or the intrinsic dimensionality. Dynamic Continuous Indexing (DCI) offers a promising way of circumventing the curse and successfully reduces the dependence of query time on intrinsic dimensionality from exponential to sublinear. In this paper, we propose a variant of DCI, which we call Prioritized DCI, and show a remarkable improvement in the dependence of query time on intrinsic dimensionality. In particular, a linear increase in intrinsic dimensionality, or equivalently, an exponential increase in the number of points near a query, can be mostly counteracted with just a linear increase in space. We also demonstrate empirically that Prioritized DCI significantly outperforms prior methods. In particular, relative to Locality-Sensitive Hashing (LSH), Prioritized DCI reduces the number of distance evaluations by a factor of 14 to 116 and the memory consumption by a factor of 21.