Dynamic Similarity Graph Construction with Kernel Density Estimation

In the kernel density estimation (KDE) problem, we are given a set X of data points in ℝd, a kernel function k: ℝd × ℝd rightarrow ℝ, and a query point q ∈ ℝd, and the objective is to quickly output an estimate of sumx ∈ X k(q, x). In this paper, we consider textsfKDE in the dynamic setting, and introduce a data structure that efficiently maintains the estimates for a set of query points as data points are added to X over time. Based on this, we design a dynamic data structure that maintains a sparse approximation of the fully connected similarity graph on X, and develop a fast dynamic spectral clustering algorithm. We further evaluate the effectiveness of our algorithms on both synthetic and real-world datasets.