Hashing-Based-Estimators for Kernel Density in High Dimensions

2018/08/30 by Moses Charikar, Charikar, Moses, Paris Siminelakis +1 · 1 citation
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1808.10530

openalex publication_date 2018/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a set of points P⊂ ℝ^d and a kernel k, the Kernel Density Estimate at a point x∈ℝ^d is defined as KDE_P(x)=(1)/(|P|)∑_{y∈ 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.

Citations

• A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators\n for Partition Function Computation in Log-Linear Models
• Lower Bounds on Near Neighbor Search via Metric Expansion

Cited by

• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions

Related

• Kernel Density Estimation through Density Constrained Near Neighbor Search
• Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory
• A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
• Kernel Density Estimators in Large Dimensions
• DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search