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.

arXiv commentICLR 2020

References in corpus (11)

• Learning Combinatorial Optimization Algorithms over Graphs
• Compressed Sensing using Generative Models
• Practical and Optimal LSH for Angular Distance
• Learned D-AMP: Principled Neural Network based Compressive Image Recovery
• Improving Online Algorithms via ML Predictions
• Learning-based Compressive Subsampling
• Learning to Branch
• A Model for Learned Bloom Filters, and Optimizing by Sandwiching
• Spreading vectors for similarity search
• Randomized partition trees for exact nearest neighbor search
• Spectral Approaches to Nearest Neighbor Search

Cited by in corpus (14)

• The Primal-Dual method for Learning Augmented Algorithms
• Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
• A Survey on Locality Sensitive Hashing Algorithms and their Applications
• Learning-based Support Estimation in Sublinear Time
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
• LES3: Learning-based Exact Set Similarity Search
• Graph Reordering for Cache-Efficient Near Neighbor Search
• Learning-Augmented $k$-means Clustering
• Semi-bandit Optimization in the Dispersed Setting
• A Note on Graph-Based Nearest Neighbor Search
• Practical Near Neighbor Search via Group Testing
• Learning-Augmented Sketches for Hessians
• Embracing Structure in Data for Billion-Scale Semantic Product Search
• IRLI: Iterative Re-partitioning for Learning to Index