mlsanityData to 14 Oct 2026

Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory

arXiv 2208.03915 ↗First posted 8 Aug 2022cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

Kernel density estimation (KDE) stands out as a challenging task in machine learning. The problem is defined in the following way: given a kernel function f(x,y) and a set of points x1, x2, cdots, xn subset ℝd, we would like to compute frac1nsumi=1n f(xi,y) for any query point y ∈ ℝd. Recently, there has been a growing trend of using data structures for efficient KDE. However, the proposed KDE data structures focus on static settings. The robustness of KDE data structures over dynamic changing data distributions is not addressed. In this work, we focus on the dynamic maintenance of KDE data structures with robustness to adversarial queries. Especially, we provide a theoretical framework of KDE data structures. In our framework, the KDE data structures only require subquadratic spaces. Moreover, our data structure supports the dynamic update of the dataset in sublinear time. Furthermore, we can perform adaptive queries with the potential adversary in sublinear time.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 14 of its 44 references that are in the map. First posted on arXiv 8 Aug 2022.

Builds on

14 of 44 references.

References · 14

  1. 2016Kernel Mean Embedding of Distributions: A Review and Beyondcited by 364
  2. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  3. 2018Hashing-Based-Estimators for Kernel Density in High Dimensionscited by 33
  4. 2018Near-Optimal Coresets of Kernel Density Estimatescited by 30
  5. 2019Semi-Supervised Learning by Augmented Distribution Alignmentcited by 30
  6. 2020Kernel Density Estimation through Density Constrained Near Neighbor Searchcited by 29
  7. 2020Algorithms and Hardness for Linear Algebra on Geometric Graphscited by 22
  8. 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
  9. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  10. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  11. 2019Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Datacited by 14
  12. 2022Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structurescited by 9
2 more
  1. 2021DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Searchcited by 8
  2. 2015Sparse Approximation of a Kernel Meancited by 4

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 4.

6 papers.

  1. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  2. 2025Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretrainingcited by 7
  3. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  4. 2024Differentially Private Kernel Density Estimationcited by 3
  5. 2025CoVE: Compressed Vocabulary Expansion Makes Better LLM-based Recommender Systemscited by 3
  6. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2