Efficient Multiple Temporal Network Kernel Density Estimation

Yu Shao, Peng Cheng, Xiang Lian, Lei Chen, Wangze Ni, Xuemin Lin, Chen Zhang, Liping WangarXiv 2025 · OpenReview

Abstract

Kernel density estimation (KDE) is essential for identifying hotspots in discrete datasets, yet traditional methods often fail in urban environments by ignoring road network constraints and temporal dynamics. This paper introduces TN-KDE, a framework designed for spatiotemporal road networks. By employing a novel Range Forest Solution (RFS) and optimizations like Lixel Sharing (LS), TN-KDE achieves up to a 6x speedup over state-of-the-art methods while supporting complex non-polynomial kernels.

Addressing the Limitations of Traditional KDE

Traditional KDE techniques face two significant hurdles when applied to urban data:

  1. Planar Overestimation: Standard KDE uses Euclidean distance ("as the crow flies"), which often overestimates density in cities where actual travel is restricted to a road network.
  2. Temporal Blindness: Most tools treat data as static or handle time inefficiently, failing to capture how hotspots—like traffic congestion or crime clusters—evolve throughout the day.
Comparison between Euclidean and Network distance in KDE.
Temporal variation in traffic density hotspots between early morning and late afternoon.

Methodology: The TN-KDE Framework

The authors propose several innovations to enhance efficiency and flexibility:

  • Range Forest Solution (RFS): To manage temporal queries, the framework uses a persistent range tree structure. By sharing nodes between versions of the tree at different timestamps, the system can efficiently query specific time windows $[T_1, T_2]$ through simple tree subtraction.
  • Dynamic Range Forest (DRFS) & Quantization: For streaming data, a dynamic version allows for continuous updates. Quantization further optimizes performance by allowing a controlled trade-off between accuracy and computational speed.
  • Lixel Sharing (LS): Road networks are discretized into "lixels" (linear pixels). The LS optimization identifies "dominated edges"—those fully covered by a query range—and calculates their contributions in bulk, significantly reducing redundant calculations.
  • Non-Polynomial Kernel Support: The framework can handle complex kernels (e.g., Gaussian, Exponential) by decomposing them into query and aggregate vectors, ensuring precision for transcendental functions.

Experimental Results

The framework was tested on real-world datasets from OpenStreetMap, including massive-scale taxi trip data from New York (38M+ events).

  • Performance: RFS demonstrated a 6x speedup over the previous state-of-the-art (ADA) and was nearly 89x faster than index-free methods.
  • Scalability and Accuracy: Even on the New York dataset, indexing remained efficient. The DRFS version maintained over 99.9% accuracy even with significant quantization, which simultaneously reduced memory costs by 60%.

Conclusion and Future Work

TN-KDE provides a robust solution for real-time urban monitoring. While it introduces some memory overhead due to its complex tree structures, the gains in speed and temporal awareness are substantial. Future research may explore more aggressive quantization techniques and adaptations for networks with dynamic travel times.

Summary updated

Abstract

Kernel density estimation (KDE) has become a popular method for visual analysis in various fields, such as financial risk forecasting, crime clustering, and traffic monitoring. KDE can identify high-density areas from discrete datasets. However, most existing works only consider planar distance and spatial data. In this paper, we introduce a new model, called TN-KDE, that applies KDE-based techniques to road networks with temporal data. Specifically, we introduce a novel solution, Range Forest Solution (RFS), which can efficiently compute KDE values on spatiotemporal road networks. To support the insertion operation, we present a dynamic version, called Dynamic Range Forest Solution (DRFS). We also propose an optimization called Lixel Sharing (LS) to share similar KDE values between two adjacent lixels. Furthermore, our solutions support many non-polynomial kernel functions and still report exact values. Experimental results show that our solutions achieve up to 6 times faster than the state-of-the-art method.
BibTeX
@misc{shao2025efficient,
  author = {Yu Shao and Peng Cheng and Xiang Lian and Lei Chen and Wangze Ni and Xuemin Lin and Chen Zhang and Liping Wang},
  title = {{Efficient Multiple Temporal Network Kernel Density Estimation}},
  year = {2025},
  eprint = {2501.07106},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.07106},
}
Figure