Locality-Sensitive Hashing Without False Negatives for l_p

DOI10.1007/978-3-319-42634-1_9MaRDI QIDQ2817854zbMATH OpenOpenAlexFDO

Authors Andrzej Pacuk, Piotr Sankowski, Karol Węgrzycki, Piotr Wygocki

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: In this paper, we show a construction of locality-sensitive hash functions without false negatives, i.e., which ensure collision for every pair of points within a given radius $R$ in $d$ dimensional space equipped with $l_p$ norm when $pin[1,infty]$. Furthermore, we show how to use these hash functions to solve the $c$-approximate nearest neighbor search problem without false negatives. Namely, if there is a point at distance $R$, we will certainly report it and points at distance greater than $cR$ will not be reported for $c=Omega(sqrtd,d^{1-frac1p})$. The constructed algorithms work: - with preprocessing time $mathcalO(nlog(n))$ and sublinear expected query time, - with preprocessing time $mathcalO(mathrmpoly(n))$ and expected query time $mathcalO(log(n))$. Our paper reports progress on answering the open problem presented by Pagh [8] who considered the nearest neighbor search without false negatives for the Hamming distance.

Recommendations

• Locality-sensitive hashing without false negatives
• CoveringLSH: locality-sensitive hashing without false negatives
• On the Distortion of Locality Sensitive Hashing
• The distortion of locality sensitive hashing
• Beyond locality-sensitive hashing
• Locality-sensitive hashing scheme based on p-stable distributions
• scientific article; zbMATH DE number 5506204
• Lower Bounds on Locality Sensitive Hashing
• scientific article; zbMATH DE number 1559577

Cites work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• Locality-sensitive hashing scheme based on p-stable distributions
• Locality-sensitive hashing without false negatives
• On Khintchine inequalities with a weight
• Optimal data-dependent hashing for approximate near neighbors
• Probability Inequalities for Sums of Bounded Random Variables
• The best constants in the Khintchine inequality

Cited in

(9)

• Index structures for fast similarity search for real-valued vectors. I
• I/O-efficient similarity join
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Lower Bounds on Locality Sensitive Hashing
• CoveringLSH: locality-sensitive hashing without false negatives
• Locality-sensitive hashing without false negatives
• On the Distortion of Locality Sensitive Hashing
• Approximate nearest neighbors search without false negatives for \(l_2\) for \(c>\sqrt{\log\log n}\)
• A locality-sensitive hash for real vectors

This page was built for publication: Locality-Sensitive Hashing Without False Negatives for $$l_p$$

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