Spatio-Temporal Kernel Density Estimation for Streaming Time-Varying Data

Kernel density estimation (KDE) is a fundamental tool across statistics, data science, visualization and machine learning. In particular, it is widely used in analyzing and visualizing multi-dimensional data sets, including, e.g., geo-spatial data. Spatio-temporal KDE is an important extension to the basic KDE problem that also takes into account the temporal relation of the data points, and provides a method to visualize evolving data patterns over time. With the explosive growth of Big Data in both size and complexity, it is typically not feasible to run naive exact algorithms due to the extremely high run time and memory-space requirements. Especially challenging is the streaming setting where the data points arrive in an online fashion, one time step at a time, and we can only access the data in one pass with a fixed, sub-linear memory. Such a challenging setting renders most of the existing methods to be inadmissible. In this paper, we take on this challenge by providing scalable approximate frameworks with low memory footprints under the streaming setting. We present randomized algorithms for efficient computation of spatio-temporal KDE with strong theoretical guarantees and empirical support. Specifically, we introduce a weighted sampling scheme and discuss a random-feature-based sketching method, and analyze their complexity and use cases. The proposed methods are sub-linear in memory and do not require the knowledge of the length of the data stream in advance. Also, the methods provide nice trade-offs between speed and accuracy. Moreover, the sketching method can easily support deletions of data points from the stream, which is not trivial for most sampling methods to perform robustly. In addition, we show how the sketching method can be easily used to answer aggregate density queries, with a computational advantage over any sampling approaches. Experiments on synthetic and real world datasets demonstrate the quality and efficiency of these proposed techniques.