EARTH: Accelerating Spatiotemporal Network K-function-based Analytics

The spatiotemporal network K-function is used widely in diverse domains, e.g., transportation science, criminology, and social science, for analyzing spatiotemporal point patterns in location datasets. Domain experts calculate multiple spatiotemporal network K-functions, considering different spatial and temporal thresholds, to generate a spatiotemporal network K-function plot. However, generating this plot is computationally expensive and does not scale to large-scale location datasets. To address this shortcoming, we propose two novel methods, called edge augmentation with range-tree (EAR) and multi-threshold sharing (MTS), that reduce the time complexity for computing a spatiotemporal network K-function and generating the corresponding plot. By wisely combining these two methods, our new approach, EARTH, achieves the lowest time complexity for generating a spatiotemporal network K-function plot. Experimental results based on four large-scale location datasets show that the new methods enable speedups ranging from 2.26x to 19.04x over the state-of-the-art solutions. The implementation of this paper can be found in https://github.com/edisonchan2013928/EARTH.