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

Area of Science:

• Data Science
• Machine Learning
• Statistics
• Geospatial Analysis

Background:

• Kernel Density Estimation (KDE) is crucial for analyzing and visualizing multi-dimensional data.
• Spatio-temporal KDE extends this by incorporating temporal data relations, vital for visualizing evolving patterns.
• Big Data challenges necessitate efficient methods for streaming data, which traditional KDE algorithms struggle with due to high runtime and memory demands.

Purpose of the Study:

• To develop scalable approximate frameworks for spatio-temporal KDE in streaming settings.
• To address the limitations of existing methods in handling high-dimensional, high-velocity data streams with sub-linear memory constraints.
• To provide efficient, theoretically guaranteed randomized algorithms for spatio-temporal KDE.

Main Methods:

• Introduced a weighted sampling scheme for efficient computation.
• Developed a random-feature-based sketching method for spatio-temporal KDE.
• Analyzed the complexity and use cases of both randomized algorithms.

Main Results:

• Proposed methods are sub-linear in memory and do not require prior knowledge of stream length.
• Algorithms offer effective trade-offs between computational speed and accuracy.
• The sketching method efficiently supports data point deletions and aggregate density queries.

Conclusions:

• The developed randomized algorithms provide scalable and efficient solutions for spatio-temporal KDE in data streams.
• These methods offer practical advantages in terms of memory footprint, speed, and flexibility, outperforming traditional approaches.
• Empirical results on synthetic and real-world datasets validate the quality and efficiency of the proposed techniques.