{"ID":2899185,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.01696","arxiv_id":"2507.01696","title":"Dynamic Similarity Graph Construction with Kernel Density Estimation","abstract":"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 \\rightarrow \\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 $\\textsf{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.","short_abstract":"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 \\rightarrow \\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(\\math...","url_abs":"https://arxiv.org/abs/2507.01696","url_pdf":"https://arxiv.org/pdf/2507.01696v1","authors":"[\"Steinar Laenen\",\"Peter Macgregor\",\"He Sun\"]","published":"2025-07-02T13:25:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}