Article

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

Authors:

Alexandr Andoni,

Piotr IndykAuthors Info & Claims

FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science

Pages 459 - 468

https://doi.org/10.1109/FOCS.2006.49

Published: 21 October 2006 Publication History

Publisher Site

Abstract

We present an algorithm for the c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time of O\left( {dn^{1/c^2+ o(1)} } \right) and space O\left( {dn + n^{1 + 1/c^2+ o(1)} } \right). This almost matches the lower bound for hashing-based algorithm recently obtained in [27]. We also obtain a space-efficient version of the algorithm, which uses dn+n log^{O(1)} n space, with a query time of dn^{O(1/c^2 )}. Finally, we discuss practical variants of the algorithms that utilize fast bounded-distance decoders for the Leech Lattice.

Cited By

View all

Filtser A(2024)A Face Cover Perspective to ℓ1 Embeddings of Planar GraphsACM Transactions on Algorithms10.1145/368680021:1(1-21)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3686800
Jayaram RWaingarten EZhang TMohar BShinkar IO'Donnell R(2024)Data-Dependent LSH for the Earth Mover’s DistanceProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649666(800-811)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649666
Huang RCui CLian JTowey DSun WChen H(2024)Toward Cost-Effective Adaptive Random Testing: An Approximate Nearest Neighbor ApproachIEEE Transactions on Software Engineering10.1109/TSE.2024.337959250:5(1182-1214)Online publication date: 21-Mar-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3379592
Show More Cited By

Index Terms

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity
Special Issue on SPAA 2016

We study the complexity of parallel data structures for approximate nearest neighbor search in d-dimensional Hamming space {0,1}^d. A classic model for static data structures is the cell-probe model [27]. We consider a cell-probe model with limited ...
Randomized Approximate Nearest Neighbor Search with Limited Adaptivity
SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures

We study the problem of approximate nearest neighbor search in $d$-dimensional Hamming space {0,1}^d. We study the complexity of the problem in the famous cell-probe model, a classic model for data structures. We consider algorithms in the cell-probe ...
Faster deterministic and Las Vegas algorithms for offline approximate nearest neighbors in high dimensions
SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms

We present a deterministic, truly subquadratic algorithm for offline (1 + ε)-approximate nearest or farthest neighbor search (in particular, the closest pair or diameter problem) in Hamming space in any dimension d ≤ n^δ, for a sufficiently small ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science

October 2006

748 pages

ISBN:0769527205

Publisher

IEEE Computer Society

United States

Publication History

Published: 21 October 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

263
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Filtser A(2024)A Face Cover Perspective to ℓ1 Embeddings of Planar GraphsACM Transactions on Algorithms10.1145/368680021:1(1-21)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3686800
Jayaram RWaingarten EZhang TMohar BShinkar IO'Donnell R(2024)Data-Dependent LSH for the Earth Mover’s DistanceProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649666(800-811)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649666
Huang RCui CLian JTowey DSun WChen H(2024)Toward Cost-Effective Adaptive Random Testing: An Approximate Nearest Neighbor ApproachIEEE Transactions on Software Engineering10.1109/TSE.2024.337959250:5(1182-1214)Online publication date: 21-Mar-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3379592
Epasto AMirrokni VNarayanan SZhong POh ANaumann TGloberson ASaenko KHardt MLevine S(2023)k-means clustering with distance-based privacyProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666981(19570-19593)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666981
Kreačić ENouri NPotluru VBalch TVeloso MEvans RShpitser I(2023)Differentially private synthetic data using KD-treesProceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence10.5555/3625834.3625942(1143-1153)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.5555/3625834.3625942
Peng PJi STian ZJiang HZheng WZhang XSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)Locality Sensitive Hashing for Optimizing Subgraph Query Processing in Parallel Computing SystemsProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599419(1885-1896)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599419
Nagarajan VMandarapu DKulkarni MGallivan KNikolopoulos DBeivide RGallopoulos E(2023)RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor SearchProceedings of the 37th International Conference on Supercomputing10.1145/3577193.3593738(289-300)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3577193.3593738
Peng ZZhang MLi KJin RRen BDehnavi MKulkarni MKrishnamoorthy S(2023)iQANProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577527(313-328)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577527
Luo XWang HWu DChen CDeng MHuang JHua X(2023)A Survey on Deep Hashing MethodsACM Transactions on Knowledge Discovery from Data10.1145/353262417:1(1-50)Online publication date: 20-Feb-2023
https://dl.acm.org/doi/10.1145/3532624
Guo JPrayuda APrasetyo HSeshathiri S(2023)Deep Learning-Based Image Retrieval With Unsupervised Double Bit HashingIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.326809133:11(7050-7065)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3268091
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Faster deterministic and Las Vegas algorithms for offline approximate nearest neighbors in high dimensions

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations