Learning Space Partitions for Nearest Neighbor Search
Learning Space Partitions for Nearest Neighbor Search
复制标题
DOI：
--
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Yihe Dong;P. Indyk;Ilya P. Razenshteyn;Tal Wagner
中科院分区：
文献类型：
--
作者：
Yihe Dong;P. Indyk;Ilya P. Razenshteyn;Tal Wagner
$\mathbb{R}^d$的空间划分是一类重要的快速最近邻搜索（NNS）算法的基础。受最近关于一般度量空间的NNS理论工作的启发（Andoni et al. 2018 b，c），我们开发了一个新的框架来构建空间分区，将问题减少到平衡图分区，然后进行监督分类。我们分别用KaHIP图分割器（Sanders and Schulz 2013）和神经网络实例化这种通用方法，以获得一种新的分割过程，称为神经局部敏感哈希（Neural Locality-Sensitive Hashing，Neural LSH）。在NNS的几个标准基准测试中（Aumuller et al. 2017），我们的实验表明，通过神经LSH获得的分区始终优于基于量化和基于树的方法以及经典的数据无关LSH发现的分区。
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 et al. 2018b,c), 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 and Schulz 2013) and neural networks, respectively, to obtain a new partitioning procedure called Neural Locality-Sensitive Hashing (Neural LSH). On several standard benchmarks for NNS (Aumuller et al. 2017), 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.