@inproceedings{dong2020learning,
author = {Dong, Yihe and Indyk, Piotr and Razenshteyn, Ilya and Wagner, Tal},
title = {Learning Space Partitions for Nearest Neighbor Search},
booktitle = {Eighth International Conference on Learning Representations (ICLR)},
year = {2020},
month = {April},
abstract = {Space partitions of Rd 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/learning-space-partitions-for-nearest-neighbor-search/},
note = {Code available: https://github.com/twistedcubic/learn-to-hash.},
}