Hashing-based-estimators For Kernel Density In High Dimensions

Charikar Moses, Siminelakis Paris. Arxiv 2018

[Paper]    
ARXIV Independent

Given a set of points $P\subset {\mathbb{R}}^d$ and a kernel $k$, the Kernel Density Estimate at a point $x\in {\mathbb{R}}^d$ is defined as \(\mathrm{KDE}{P}(x)=\frac{1}{|P|}\sum{y\in P} k(x,y)\). We study the problem of designing a data structure that given a data set $P$ and a kernel function, returns approximations to the kernel density of a query point in sublinear time. We introduce a class of unbiased estimators for kernel density implemented through locality-sensitive hashing, and give general theorems bounding the variance of such estimators. These estimators give rise to efficient data structures for estimating the kernel density in high dimensions for a variety of commonly used kernels. Our work is the first to provide data-structures with theoretical guarantees that improve upon simple random sampling in high dimensions.

Similar Work

• Kernel Density Estimation Through Density Constrained Near Neighbor Search
• Kernel Diff-hash
• Generalized Intersection Kernel
• Core Kernels