Locality sensitive hashing extends to new distance measures for density estimation
Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
Data Structures and AlgorithmsComputational GeometryMachine Learning
Summary
Some computers need to quickly find similar items in large sets of data, and they do this using a tool called locality sensitive hashing (LSH). This technique works well with certain kinds of similarity measurements called kernels. The authors show that a popular kind of similarity, called the p-exponential kernel, can be used with LSH for more types of distances than previously known. They developed a new method called mosaic LSH, which uses special randomly oriented cuts to group data efficiently. This helps improve ways to estimate data distributions in high-dimensional spaces.
What this means in practice
- •For data engineers: Improve scalable density estimation in high-dimensional data sets using new LSH methods for p-exponential kernels.
- •For signal processing teams: Use the mosaic LSH technique to efficiently find similar signals using advanced distance measures beyond previously supported cases.
Authors
Barak Gorodissky, Tal Wagner
Abstract
A kernel $k(x,y)$ is LSHable if there exists a locality sensitive hashing scheme $H$ such that $k(x,y)=\Pr_{h\sim H}[h(x)=h(y)]$ for all $x,y$. This notion plays a key role in efficient kernel methods in high dimensions. In this work, we show that the $p$-exponential kernel $k(x,y)=\exp(-\lVert x-y \rVert_p)$ is LSHable in bounded regions for all $1<p\leq2$. Previously, this was known only for $p=1$. Our new "mosaic LSH" scheme is based on a Poisson hyperplane process with hyperplanes sampled as $\ell_1$-biased $p$-stable vectors, for which we develop efficient sampling procedures. As applications, our results yield new and efficient density estimation methods based on LSHability for those $p$-exponential kernels.