Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
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 thos...
| Authors | Barak Gorodissky, Tal Wagner |
|---|---|
| Primary category | cs.DS |
| Published | 4 October 2026 |
| Last updated at source | 4 October 2026 |
Popularity, last 2 days
0 now. Counts as reported by the source, snapshotted daily by Silytics.
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.