License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.9
URN: urn:nbn:de:0030-drops-59014
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5901/
Go to the corresponding LIPIcs Volume Portal

Andoni, Alexandr ; Razensteyn, Ilya

Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing

pdf-format:
LIPIcs-SoCG-2016-9.pdf (0.4 MB)

Abstract

We prove a tight lower bound for the exponent rho 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 rho<= 1/(2c-1)+o(1) for the 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 l_1 space, the tight bound is rho=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 rho>=1/(2c-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.

BibTeX - Entry

@InProceedings{andoni_et_al:LIPIcs:2016:5901,
  author =	{Alexandr Andoni and Ilya Razensteyn},
  title =	{{Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{9:1--9:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5901},
  URN =		{urn:nbn:de:0030-drops-59014},
  doi =		{10.4230/LIPIcs.SoCG.2016.9},
  annote =	{Keywords: similarity search, high-dimensional geometry, LSH, data structures, lower bounds}
}

Keywords: similarity search, high-dimensional geometry, LSH, data structures, lower bounds
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI