# Kernel Density Estimation through Density Constrained Near Neighbor Search

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2020.

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

- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [An Over-parameterized Exponential Regression](https://mlsanity.com/paper/2303.16504/) (2023)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [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)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory](https://mlsanity.com/paper/2208.03915/) (2022)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)
- [Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions](https://mlsanity.com/paper/2507.23539/) (2025)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [Towards Tight Bounds for Streaming Attention](https://mlsanity.com/paper/2606.07205/) (2026)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (2025)
- [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)
- [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)
- [Almost Linear Time Consistent Mode Estimation and Quick Shift Clustering](https://mlsanity.com/paper/2503.07995/) (2025)
- [Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2505.15636/) (2025)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)
- [Random Fourier Features in Near-Linear Time](https://mlsanity.com/paper/2610.14751/) (2026)

## Abstract (arXiv)

In this paper we revisit the kernel density estimation problem: given a kernel K(x, y) and a dataset of n points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query q, a (1+ε)-approximation to μ:=frac1|P|sump∈ P K(p, q). First, we give a single data structure based on classical near neighbor search techniques that improves upon or essentially matches the query time and space complexity for all radial kernels considered in the literature so far. We then show how to improve both the query complexity and runtime by using recent advances in data-dependent near neighbor search. We achieve our results by giving a new implementation of the natural importance sampling scheme. Unlike previous approaches, our algorithm first samples the dataset uniformly (considering a geometric sequence of sampling rates), and then uses existing approximate near neighbor search techniques on the resulting smaller dataset to retrieve the sampled points that lie at an appropriate distance from the query. We show that the resulting sampled dataset has strong geometric structure, making approximate near neighbor search return the required samples much more efficiently than for worst case datasets of the same size. As an example application, we show that this approach yields a data structure that achieves query time μ-(1+o(1))/4 and space complexity μ-(1+o(1)) for the Gaussian kernel. Our data dependent approach achieves query time μ-0.173-o(1) and space μ-(1+o(1)) for the Gaussian kernel. The data dependent analysis relies on new techniques for tracking the geometric structure of the input datasets in a recursive hashing process that we hope will be of interest in other applications in near neighbor search.