Learning Space Partitions For Nearest Neighbor Search

Abstract

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keydong2019learning

Related papers

• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• A Multilabel Classification Framework For Approximate Nearest Neighbor Search (2019)0.00
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Fast And Bayes-consistent Nearest Neighbors (2019)0.00
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
• LIRA: A Learning-based Query-aware Partition Framework For Large-scale ANN Search (2025)6.98
• Sparse-inductive Generative Adversarial Hashing For Nearest Neighbor Search (2023)0.00