Practical and Optimal LSH for Angular Distance
arXiv:1509.02897
Abstract
We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optimal running time exponent. Unlike earlier algorithms with this property (e.g., Spherical LSH [Andoni, Indyk, Nguyen, Razenshteyn 2014], [Andoni, Razenshteyn 2015]), our algorithm is also practical, improving upon the well-studied hyperplane LSH [Charikar, 2002] in practice. We also introduce a multiprobe version of this algorithm, and conduct experimental evaluation on real and synthetic data sets. We complement the above positive results with a fine-grained lower bound for the quality of any LSH family for angular distance. Our lower bound implies that the above LSH family exhibits a trade-off between evaluation time and quality that is close to optimal for a natural class of LSH functions.
22 pages, an extended abstract is to appear in the proceedings of the 29th Annual Conference on Neural Information Processing Systems (NIPS 2015)
Cited by in corpus (62)
- Reformer: The Efficient Transformer
- Neural Networks for Entity Matching: A Survey
- Generalisation error in learning with random features and the hidden manifold model
- Fast k-NN search
- Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
- Differentiable Reasoning over a Virtual Knowledge Base
- Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
- A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations
- Deep Cross-Modal Hashing
- ETC: Encoding Long and Structured Inputs in Transformers
- Convolutional Embedding for Edit Distance
- Pigeonring: A Principle for Faster Thresholded Similarity Search
- Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search
- Structured adaptive and random spinners for fast machine learning computations
- Learning Space Partitions for Nearest Neighbor Search
- Bolt: Accelerated Data Mining with Fast Vector Compression
- Foundations of Vector Retrieval
- Parameter-free Locality Sensitive Hashing for Spherical Range Reporting
- SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search
- Communication-Efficient Distributed SGD with Compressed Sensing
- Towards Similarity Graphs Constructed by Deep Reinforcement Learning
- Rubik: A Hierarchical Architecture for Efficient Graph Learning
- Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
- Locality Sensitive Hashing with Extended Differential Privacy
- Approximate Nearest Neighbors in the Space of Persistence Diagrams
- Making Online Sketching Hashing Even Faster
- Minimizing FLOPs to Learn Efficient Sparse Representations
- Shifted Chunk Transformer for Spatio-Temporal Representational Learning
- Improving Similarity Search with High-dimensional Locality-sensitive Hashing
- DartMinHash: Fast Sketching for Weighted Sets
- Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
- Nearest neighbor decoding for Tardos fingerprinting codes
- SAH: Shifting-aware Asymmetric Hashing for Reverse -Maximum Inner Product Search
- Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
- 3D Scene Geometry-Aware Constraint for Camera Localization with Deep Learning
- Android Malware Clustering using Community Detection on Android Packages Similarity Network
- McKernel: A Library for Approximate Kernel Expansions in Log-linear Time
- Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science
- Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring
- SMYRF: Efficient Attention using Asymmetric Clustering
- Efficient Approximate Search for Sets of Vectors
- A Generic Distributed Clustering Framework for Massive Data
- Deep auxiliary learning for visual localization using colorization task
- Practical Near Neighbor Search via Group Testing
- Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance
- A Note on Graph-Based Nearest Neighbor Search
- MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS in Distance
- Single Shot Scene Text Retrieval
- Generic LSH Families for the Angular Distance Based on Johnson-Lindenstrauss Projections and Feature Hashing LSH
- TripleSpin - a generic compact paradigm for fast machine learning computations
- Multi-Level Spherical Locality Sensitive Hashing For Approximate Near Neighbors
- Streaming Binary Sketching based on Subspace Tracking and Diagonal Uniformization
- Approximate Inference via Clustering
- Segmentation of Objects by Hashing
- CNN with large memory layers
- Optimizing Offer Sets in Sub-Linear Time
- Sublinear Maximum Inner Product Search using Concomitants of Extreme Order Statistics
- Algorithms for Similarity Search and Pseudorandomness
- DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search
- Optimal Las Vegas Approximate Near Neighbors in
- IRLI: Iterative Re-partitioning for Learning to Index
- Exact Computation of a Manifold Metric, via Lipschitz Embeddings and Shortest Paths on a Graph