Space partitions of $\mathbb{R}^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.

本研究提出一种新的框架用于构建空间划分，将问题转化为平衡图划分和监督分类，并结合 KaHIP 图分区器和神经网络，实现了一种新的分区过程称为神经局部敏感哈希（Neural LSH），实验证明 Neural LSH 的分区在标准最近邻搜索（NNS）基准测试中，始终优于基于量化和树的方法，以及经典的数据无关 LSH。