EUVIMEDEUVIMED entdecken
Crossref

Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)

Ryan O’Donnell, Yi Wu, Yuan Zhou

ACM Transactions on Computation Theory · 2014-03 · 6 (1) · 1-13

DOI: 10.1145/2578221 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2014-03. Verfasst von Ryan O’Donnell und 2 weiteren Autor:innen. Die Arbeit wurde bisher 35-mal zitiert (Crossref) und nennt 17 Literaturangaben. Gefördert von: Sloan and Okawa, BSF, Division of Computing and Communication Foundations.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study lower bounds for Locality-Sensitive Hashing (LSH) in the strongest setting: point sets in {0,1} d under the Hamming distance. Recall that H is said to be an ( r , cr , p , q )-sensitive hash family if all pairs x , y ∈ {0,1} d with dist( x , y ) ≤ r have probability at least p of collision under a randomly chosen h ∈ H, whereas all pairs x , y ∈ {0, 1} d with dist( x , y ) ≥ cr have probability at most q of collision. Typically, one considers d → ∞, with c > 1 fixed and q bounded away from 0. For its applications to approximate nearest-neighbor search in high dimensions, the quality of an LSH family H is governed by how small its ρ parameter ρ = ln(1/ p )/ln(1/ q ) is as a function of the parameter c . The seminal paper of Indyk and Motwani [1998] showed that for each c ≥ 1, the extremely simple family H = { x ↦ x i : i ∈ [ d ]} achieves ρ ≤ 1/ c . The only known lower bound, due to Motwani et al. [2007], is that ρ must be at least ( e 1/c - 1)/( e 1/c + 1) ≥ .46/ c (minus o d (1)). The contribution of this article is twofold. (1) We show the “optimal” lower bound for ρ : it must be at least 1/ c (minus o d (1)). Our proof is very simple, following almost immediately from the observation that the noise stability of a boolean function at time t is a log-convex function of t . (2) We raise and discuss the following issue: neither the application of LSH to nearest-neighbor search nor the known LSH lower bounds hold as stated if the q parameter is tiny. Here, “tiny” means q = 2 -Θ(d) , a parameter range we believe is natural.

Förderung

  • Sloan and Okawa
  • BSF
  • Division of Computing and Communication Foundations

Zitieren

APA

O’Donnell, R., Wu, Y., & Zhou, Y. (2014). Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny). ACM Transactions on Computation Theory, 6(1), 1-13. https://doi.org/10.1145/2578221

Vancouver

O’Donnell R, Wu Y, Zhou Y. Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny). ACM Transactions on Computation Theory. 2014;6(1):1-13. doi:10.1145/2578221

BibTeX
@article{ODonnell2014,
  author = {O’Donnell, Ryan and Wu, Yi and Zhou, Yuan},
  title = {Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)},
  journal = {ACM Transactions on Computation Theory},
  year = {2014},
  volume = {6},
  number = {1},
  pages = {1--13},
  doi = {10.1145/2578221}
}
Kostenlos starten →