# Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation

arXiv: https://arxiv.org/abs/2610.05174 · HTML: https://mlsanity.com/paper/2610.05174/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 4 Oct 2026.

## Builds on (most cited first, 14 of 14)

- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models](https://mlsanity.com/paper/1703.05160/) (2017)
- [Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data](https://mlsanity.com/paper/1912.02283/) (2019)
- [The Mondrian Kernel](https://mlsanity.com/paper/1606.05241/) (2016)
- [Scaling up Kernel Ridge Regression via Locality Sensitive Hashing](https://mlsanity.com/paper/2003.09756/) (2020)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [Stochastic geometry to generalize the Mondrian Process](https://mlsanity.com/paper/2002.00797/) (2020)
- [Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering](https://mlsanity.com/paper/2006.08569/) (2020)
- [Solving ℓp!-norm regularization with tensor kernels](https://mlsanity.com/paper/1707.05609/) (2017)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases](https://mlsanity.com/paper/2605.09472/) (2026)

## Built on by (most cited first, 1 of 1)

- [Random Fourier Features in Near-Linear Time](https://mlsanity.com/paper/2610.14751/) (2026)

## Abstract (arXiv)

A kernel k(x,y) is LSHable if there exists a locality sensitive hashing scheme H such that k(x,y)=Prh~ 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 rVertp) is LSHable in bounded regions for all 1<p≤2. Previously, this was known only for p=1. Our new "mosaic LSH" scheme is based on a Poisson hyperplane process with hyperplanes sampled as ℓ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.