On fast bounded locality sensitive hashing
Author:
Preprint
Abstract
In this paper, we examine the hash functions expressed as scalar products, i.e., $f(x)=$, for some bounded random vector $v$. Such hash functions have numerous applications, but often there is a need to optimize the choice of the distribution of $v$. In the present work, we focus on so-called anti-concentration bounds, i.e. the upper bounds of $\mathbb{P}\left[|| < \alpha \right]$. In many applications, $v$ is a vector of independent random variables with standard normal distribution. In such case, the distribution of $$ is also normal and it is easy to approximate $\mathbb{P}\left[|| < \alpha \right]$. Here, we consider two bounded distributions in the context of the anti-concentration bounds. Particularly, we analyze $v$ being a random vector from the unit ball in $l_{\infty}$ and $v$ being a random vector from the unit sphere in $l_{2}$. We show optimal up to a constant anti-concentration measures for functions $f(x)=$. As a consequence of our research, we obtain new best results for \newline \textit{$c$-approximate nearest neighbors without false negatives} for $l_p$ in high dimensional space for all $p\in[1,\infty]$, for $c=\Omega(\max\{\sqrt{d},d^{1/p}\})$. These results improve over those presented in [16]. Finally, our paper reports progress on answering the open problem by Pagh~[17], who considered the nearest neighbor search without false negatives for the Hamming distance.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Locality-Sensitive Hashing Without False Negatives for $l_p$2016
- Optimal Data-Dependent Hashing for Approximate Near Neighbors2015
- On Concentration Functions of Random VariablesJournal of Theoretical Probability, 2013
- Approximate range searching in higher dimensionComputational Geometry, 2008
- Near-optimal hashing algorithms for approximate nearest neighbor in high dimensionsCommunications of the ACM, 2008
- Uncertainty principles, extractors, and explicit embeddings of l2 into l12007
- A new algorithm for optimal 2-constraint satisfaction and its implicationsTheoretical Computer Science, 2005
- The (B) conjecture for the Gaussian measure of dilates of symmetric convex sets and related problemsJournal of Functional Analysis, 2004
- On approximate nearest neighbors in non-Euclidean spaces2002
- Approximate nearest neighbors1998