Dynamic Kernel Density Estimation using Approximate Nearest Neighbor Search - A Dynamic Extension of the DEANN Algorithm

Abstract

Kernel Density Estimation (KDE) is a nonparametric method for estimating an unknown density from observed data. Exact KDE evaluates every data point for each query, which becomes expensive for large datasets. DEANN reduces this cost in the static setting by combining approximate nearest neighbor search with random sampling, but assumes that the dataset is fixed after preprocessing. This thesis extends DEANN to a dynamic setting where points can be inserted and deleted. The implemented Dynamic ANN Estimator (DAE) maintains a dynamic ANN component together with a dynamic random-sampling structure, allowing KDE queries to be evaluated against the current active dataset. The implementation is evaluated against an exact dynamic naïve KDE baseline on several benchmark datasets. The results show that DAE can reduce query time once the active dataset is sufficiently large. However, this comes at the cost of substantially higher construction and update time due to ANN maintenance. Experiments with longer update sequences indicate that query time and approximation error remain stable over repeated updates. These results suggest that dynamic DEANN is most suitable for large, query-heavy dynamic KDE workloads where the maintained estimator can be reused for many queries.