# Randomized partition trees for exact nearest neighbor search

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2013.

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

- [A Comprehensive Survey on Trustworthy Recommender Systems](https://mlsanity.com/paper/2209.10117/) (2022)
- [Demystifying and Enhancing the Efficiency of Large Language Model Based Search Agents](https://mlsanity.com/paper/2505.12065/) (2025)
- [Curator: Efficient Indexing for Multi-Tenant Vector Databases](https://mlsanity.com/paper/2401.07119/) (2024)
- [Monitoring Robustness and Individual Fairness](https://mlsanity.com/paper/2506.00496/) (2025)
- [A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment](https://mlsanity.com/paper/2209.02905/) (2022)
- [Unsupervised Space Partitioning for Nearest Neighbor Search](https://mlsanity.com/paper/2206.08091/) (2022)
- [Nearest Neighbor Search Under Uncertainty](https://mlsanity.com/paper/2103.05057/) (2021)
- [IRLI: Iterative Re-partitioning for Learning to Index](https://mlsanity.com/paper/2103.09944/) (2021)
- [Eigen Memory Trees](https://mlsanity.com/paper/2210.14077/) (2022)
- [Fast Exact Retrieval for Nearest-neighbor Lookup (FERN)](https://mlsanity.com/paper/2405.04435/) (2024)
- [Relevance-Based Embeddings: Lightweight Candidate Retrieval via Heavy-Ranker Calls](https://mlsanity.com/paper/2607.03515/) (2026)
- [RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2608.30384/) (2026)

## Abstract (arXiv)

The k-d tree was one of the first spatial data structures proposed for nearest neighbor search. Its efficacy is diminished in high-dimensional spaces, but several variants, with randomization and overlapping cells, have proved to be successful in practice. We analyze three such schemes. We show that the probability that they fail to find the nearest neighbor, for any data set and any query point, is directly related to a simple potential function that captures the difficulty of the point configuration. We then bound this potential function in two situations of interest: the first, when data come from a doubling measure, and the second, when the data are documents from a topic model.