# Hashing-Based-Estimators for Kernel Density in High Dimensions

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2018.

## Built on by (most cited first, 30 of 33)

- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Sampling](https://mlsanity.com/paper/2111.09714/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [LookupFFN: Making Transformers Compute-lite for CPU inference](https://mlsanity.com/paper/2403.07221/) (2024)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Quantum Adaptive Fourier Features for Neural Density Estimation](https://mlsanity.com/paper/2208.00564/) (2022)
- [Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory](https://mlsanity.com/paper/2208.03915/) (2022)
- [Kernel approximation on algebraic varieties](https://mlsanity.com/paper/2106.02755/) (2021)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions](https://mlsanity.com/paper/2507.23539/) (2025)
- [Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?](https://mlsanity.com/paper/2101.10905/) (2021)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [Efficient Inference via Universal LSH Kernel](https://mlsanity.com/paper/2106.11426/) (2021)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [BOLT: An Automated Deep Learning Framework for Training and Deploying Large-Scale Search and Recommendation Models on Commodity CPU Hardware](https://mlsanity.com/paper/2303.17727/) (2023)
- [New Bounds for Kernel Sums via Fast Spherical Embeddings](https://mlsanity.com/paper/2605.01263/) (2026)
- [Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases](https://mlsanity.com/paper/2605.09472/) (2026)
- [Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation](https://mlsanity.com/paper/2610.05174/) (2026)
- [Density Sketches for Sampling and Estimation](https://mlsanity.com/paper/2102.12301/) (2021)
- [Dimension-Independent Kernel ε-Covers](https://mlsanity.com/paper/2306.16516/) (2023)
- [Spectral Toolkit of Algorithms for Graphs: Technical Report (2)](https://mlsanity.com/paper/2407.07096/) (2024)

## Abstract (arXiv)

Given a set of points Psubset ℝd and a kernel k, the Kernel Density Estimate at a point x∈ℝd is defined as KDEP(x)=frac1|P|sumy∈ 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.