cs.DS — Data Structures and Algorithms

Diameter-Free Pointwise Gaussian KDE in Near-Additive Query Time

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

Wagner asked whether Gaussian kernel density estimation in $\mathbb R^d$ admits query time $\widetilde O(d+\varepsilon^{-2})$ without dependence on the diameter of the data. We answer this affirmatively for each fixed query: a randomized data structure answers a query to additive error $\varepsilon$ with probability $1-\delta$ in time $O((d+\varepsilon^{-2})\log(d+1)\log(2/\delta))$, independently of the number of data points and of their diameter. The key ingredient is a variance bound for a Fastfood-type structured Fourier block that holds uniformly in the norm of the displacement.