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 ${\mathbb{R}}^d$, a kernel function $k:{\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R}$, and a query point $\mathbf{q}\in {\mathbb{R}}^d$, and the objective is to quickly output an estimate of ${\sum }_{\mathbf{x}\in X}k(\mathbf{q},\mathbf{x})$. In this paper, we consider $\mathsf{\text{KDE}}$ 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.