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

Barak Gorodissky, Tal Wagner

A kernel $k(x,y)$ is LSHable if there exists a locality sensitive hashing scheme $H$ such that $k(x,y)={\mathrm{Pr}}_{h\sim H}[h(x)=h(y)]$ for all $x,y$. This notion plays a key role in effi…