文章基本信息

标题：Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing
本地全文：下载
作者：Alexandr Andoni ; Ilya Razensteyn
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：51
页码：9:1-9:11
DOI：10.4230/LIPIcs.SoCG.2016.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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). 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.
关键词：similarity search; high-dimensional geometry; LSH; data structures; lower bounds