mlsanityData to 7 Oct 2026

Optimal Data-Dependent Hashing for Approximate Near Neighbors

arXiv 1501.01062 ↗First posted 6 Jan 2015cs.DScited by 43

Not on the map. Why?

Abstract (arXiv)

We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an n-point data set in a d-dimensional space our data structure achieves query time O(d nρ+o(1)) and space O(n1+ρ+o(1) + dn), where ρ=tfrac12c2-1 for the Euclidean space and approximation c>1. For the Hamming space, we obtain an exponent of ρ=tfrac12c-1. Our result completes the direction set forth in [AINR14] who gave a proof-of-concept that data-dependent hashing can outperform classical Locality Sensitive Hashing (LSH). In contrast to [AINR14], the new bound is not only optimal, but in fact improves over the best (optimal) LSH data structures [IM98,AI06] for all approximation factors c>1. From the technical perspective, we proceed by decomposing an arbitrary dataset into several subsets that are, in a certain sense, pseudo-random.

Key facts. Cited by 43 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Jan 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 11; 2024: 5; 2025: 7; 2026: 7.

43 papers.

Sort:

By area:

  1. 2024The Faiss librarycited by 370
  2. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  3. 2024MagicPIG: LSH Sampling for Efficient LLM Generationcited by 112
  4. 2023A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challengecited by 55
  5. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  6. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  7. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  8. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  9. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  10. 2023A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graphcited by 10
  11. 2021SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddingscited by 9
  12. 2022Survival Kernets: Scalable and Interpretable Deep Kernel Survival Analysis with an Accuracy Guaranteecited by 9
31 more
  1. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  2. 2022Hardness and Algorithms for Robust and Sparse Optimizationcited by 8
  3. 2021Learning to Hash Robustly, Guaranteedcited by 7
  4. 2022Sublinear Time Algorithm for Online Weighted Bipartite Matchingcited by 7
  5. 2023Automating Nearest Neighbor Search Configuration with Constrained Optimizationcited by 7
  6. 2022Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Searchcited by 6
  7. 2023A Near-Linear Time Algorithm for the Chamfer Distancecited by 5
  8. 2023Data Structures for Density Estimationcited by 4
  9. 2026Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inferencecited by 4
  10. 2022Metric-Fair Classifier Derandomizationcited by 2
  11. 2025Explaining the Success of Nearest Neighbor Methods in Predictioncited by 2
  12. 2025Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectorscited by 2
  13. 2022Stars: Tera-Scale Graph Building for Clustering and Graph Learningcited by 1
  14. 2023BOLT: An Automated Deep Learning Framework for Training and Deploying Large-Scale Search and Recommendation Models on Commodity CPU Hardwarecited by 1
  15. 2026DASH-KV: Accelerating Long-Context LLM Inference via Asymmetric KV Cache Hashingcited by 1
  16. 2021Provable Hierarchical Lifelong Learning with a Sketch-based Modular Architecturecited by 0
  17. 2023The Power of External Memory in Increasing Predictive Model Capacitycited by 0
  18. 2023Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detectioncited by 0
  19. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  20. 2024Spectral Toolkit of Algorithms for Graphs: Technical Report (2)cited by 0
  21. 2024Faster and Simpler Greedy Algorithm for k-Median and k-Meanscited by 0
  22. 2025Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Paircited by 0
  23. 2025Contextual Tokenization for Graph Inverted Indicescited by 0
  24. 2025Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimationcited by 0
  25. 2025Approximate Diverse k-nearest Neighbor Search in Vector Databasecited by 0
  26. 2025Graph-based Nearest Neighbors with Dynamic Updates via Random Walkscited by 0
  27. 2026TStore: Rethinking AI Model Hub with Tensor-Centric Compressioncited by 0
  28. 2026FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distancescited by 0
  29. 2026RFHNet: Relational and Frequency-Aware Hashing Network for Large-Scale Fine-Grained Food Image Retrievalcited by 0
  30. 2026Learning Partition Trees for Nearest Neighbor Searchcited by 0
  31. 2026LeanStream: A Speculate-and-Refine Streaming Framework for Efficient on-Device LLM Inferencecited by 0