# Learning Space Partitions for Nearest Neighbor Search

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2019.

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

- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2306.06611/) (2023)
- [On Storage Neural Network Augmented Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2501.16375/) (2025)
- [Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue](https://mlsanity.com/paper/2502.20233/) (2025)

## Abstract (arXiv)

Space partitions of ℝd underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metric spaces [Andoni, Naor, Nikolov, Razenshteyn, Waingarten STOC 2018, FOCS 2018], we develop a new framework for building space partitions reducing the problem to balanced graph partitioning followed by supervised classification. We instantiate this general approach with the KaHIP graph partitioner [Sanders, Schulz SEA 2013] and neural networks, respectively, to obtain a new partitioning procedure called Neural Locality-Sensitive Hashing (Neural LSH). On several standard benchmarks for NNS, our experiments show that the partitions obtained by Neural LSH consistently outperform partitions found by quantization-based and tree-based methods as well as classic, data-oblivious LSH.