mlsanityData to 7 Oct 2026

Hashing-Based-Estimators for Kernel Density in High Dimensions

arXiv 1808.10530 ↗First posted 30 Aug 2018cs.DScited by 31

Not on the map. Why?

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.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Aug 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 5; 2023: 7; 2024: 3; 2025: 3; 2026: 2.

31 papers.

Sort:

  1. 2023Fast Attention Requires Bounded Entriescited by 102
  2. 2021Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Methodcited by 61
  3. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  4. 2021Learning with Density Matrices and Random Featurescited by 17
  5. 2021You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Samplingcited by 17
  6. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  7. 2021Fast Statistical Leverage Score Approximation in Kernel Ridge Regressioncited by 14
  8. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  9. 2021DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Searchcited by 8
  10. 2024LookupFFN: Making Transformers Compute-lite for CPU inferencecited by 8
  11. 2021Faster Kernel Matrix Algebra via Density Estimationcited by 7
  12. 2023Fast Private Kernel Density Estimation via Locality Sensitive Quantizationcited by 7
19 more
  1. 2023The complexity of non-stationary reinforcement learningcited by 7
  2. 2022Quantum Adaptive Fourier Features for Neural Density Estimationcited by 6
  3. 2022Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theorycited by 6
  4. 2021Kernel approximation on algebraic varietiescited by 4
  5. 2025Tensor Sketch: Fast and Scalable Polynomial Kernel Approximationcited by 4
  6. 2025Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptionscited by 4
  7. 2021Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?cited by 3
  8. 2023Fast Approximation of Similarity Graphs with Kernel Density Estimationcited by 3
  9. 2021Efficient Inference via Universal LSH Kernelcited by 2
  10. 2022The Complexity of Dynamic Least-Squares Regressioncited by 2
  11. 2022Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimationcited by 2
  12. 2023BOLT: An Automated Deep Learning Framework for Training and Deploying Large-Scale Search and Recommendation Models on Commodity CPU Hardwarecited by 1
  13. 2021Density Sketches for Sampling and Estimationcited by 0
  14. 2023Dimension-Independent Kernel ε-Coverscited by 0
  15. 2024Spectral Toolkit of Algorithms for Graphs: Technical Report (2)cited by 0
  16. 2024Weighted Diversified Sampling for Efficient Data-Driven Single-Cell Gene-Gene Interaction Discoverycited by 0
  17. 2025Almost Linear Time Consistent Mode Estimation and Quick Shift Clusteringcited by 0
  18. 2026New Bounds for Kernel Sums via Fast Spherical Embeddingscited by 0
  19. 2026Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biasescited by 0