PWPiotr Wygocki
Piotr Wygocki
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Piotr Wygocki has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Andrzej Pacuk
University of Warsaw, Warsaw, Poland
1 shared publication - Karol Węgrzycki
MPI-INF, Saarbrücken, Germany
1 shared publication Piotr Sankowski
University of Warsaw
1 shared publication
Latest Publications
- Open Access
On fast bounded locality sensitive hashing
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.Open AccessOn fast bounded locality sensitive hashing
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. - 20 July 2016
- Published by Springer Nature
- p. 105-118
Locality-Sensitive Hashing Without False Negatives for $l_p$- 20 July 2016
- Published by Springer Nature
- p. 105-118
Locality-Sensitive Hashing Without False Negatives for $l_p$