Tight lower bounds for data-dependent locality-sensitive hashing

DOI10.4230/LIPICS.SOCG.2016.9MaRDI QIDQ3132842zbMATH OpenOpenAlexFDO

Authors Alexandr Andoni, Ilya Razensteyn

Publication date 30 January 2018

Full work available at URL https://arxiv.org/abs/1507.04299

zbMATH Keywords

data structureshigh-dimensional geometrylower boundsLSHsimilarity search

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We prove a tight lower bound for the exponent $ho$ for data-dependent Locality-Sensitive Hashing schemes, recently used to design efficient solutions for the $c$-approximate nearest neighbor search. In particular, our lower bound matches the bound of $holefrac12c-1+o(1)$ for the $el{l}_1$ space, obtained via the recent algorithm from [Andoni-Razenshteyn, STOC'15]. In recent years it emerged that data-dependent hashing is strictly superior to the classical Locality-Sensitive Hashing, when the hash function is data-independent. In the latter setting, the best exponent has been already known: for the $el{l}_1$ space, the tight bound is $ho=1/c$, with the upper bound from [Indyk-Motwani, STOC'98] and the matching lower bound from [O'Donnell-Wu-Zhou, ITCS'11]. We prove that, even if the hashing is data-dependent, it must hold that $hogefrac12c-1-o(1)$. To prove the result, we need to formalize the exact notion of data-dependent hashing that also captures the complexity of the hash functions (in addition to their collision properties). Without restricting such complexity, we would allow for obviously infeasible solutions such as the Voronoi diagram of a dataset. To preclude such solutions, we require our hash functions to be succinct. This condition is satisfied by all the known algorithmic results.

Recommendations

• Optimal data-dependent hashing for approximate near neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Lower Bounds on Locality Sensitive Hashing
• Data-dependent hashing via nonlinear spectral gaps
• Beyond locality-sensitive hashing

Cited in

(6)

• Index structures for fast similarity search for real-valued vectors. I
• Locality sensitive hashing with extended differential privacy
• Optimal data-dependent hashing for approximate near neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Lower Bounds on Locality Sensitive Hashing
• Data-dependent hashing via nonlinear spectral gaps

This page was built for publication: Tight lower bounds for data-dependent locality-sensitive hashing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132842)