mlsanityData to 7 Oct 2026

Beyond Locality-Sensitive Hashing

arXiv 1306.1547 ↗First posted 6 Jun 2013cs.DS cs.CGcited by 23

Not on the map. Why?

Abstract (arXiv)

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in Rd, our algorithm achieves O(nρ + d log n) query time and O(n1 + ρ + d log n) space, where ρ <= 7/(8c2) + O(1 / c3) + o(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ℓ1 norm with ρ <= 7/(8c) + O(1/c3/2) + o(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Jun 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 2; 2023: 6; 2024: 4; 2025: 3; 2026: 4.

23 papers.

Sort:

By area:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  2. 2024A Survey on Retrieval-Augmented Text Generation for Large Language Modelscited by 77
  3. 2023A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challengecited by 55
  4. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  5. 2021SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddingscited by 9
  6. 2021Learning to Hash Robustly, Guaranteedcited by 7
  7. 2022Sublinear Time Algorithm for Online Weighted Bipartite Matchingcited by 7
  8. 2024MemoryFormer: Minimize Transformer Computation by Removing Fully-Connected Layerscited by 4
  9. 2026Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inferencecited by 4
  10. 2025Monitoring Robustness and Individual Fairnesscited by 3
  11. 2022Metric-Fair Classifier Derandomizationcited by 2
  12. 2023Deep Hashing via Householder Quantizationcited by 2
11 more
  1. 2023BOLT: An Automated Deep Learning Framework for Training and Deploying Large-Scale Search and Recommendation Models on Commodity CPU Hardwarecited by 1
  2. 2024Leveraging High-Resolution Features for Improved Deep Hashing-based Image Retrievalcited by 1
  3. 2021Provable Hierarchical Lifelong Learning with a Sketch-based Modular Architecturecited by 0
  4. 2023The Power of External Memory in Increasing Predictive Model Capacitycited by 0
  5. 2023Massively-Parallel Heat Map Sorting and Applications To Explainable Clusteringcited by 0
  6. 2024SPINEX-Clustering: Similarity-based Predictions with Explainable Neighbors Exploration for Clustering Problemscited by 0
  7. 2025Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Searchcited by 0
  8. 2025Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimationcited by 0
  9. 2026SubQuad: Near-Quadratic-Free Structure Inference with Distribution-Balanced Objectives in Adaptive Receptor frameworkcited by 0
  10. 2026Hyperdimensional Cross-Modal Alignment of Frozen Language and Image Models for Efficient Image Captioningcited by 0
  11. 2026Learning Partition Trees for Nearest Neighbor Searchcited by 0