Most of the efficient sublinear-time indexing algorithms for the high-dimensional nearest neighbor search problem (NNS) are based on space partitions of the ambient space $\mathbb{R}^d$. 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 constructing such partitions that reduces 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 found by Neural LSH consistently outperform partitions found by quantization- and tree-based methods.

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

最近邻搜索的学习空间划分