DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis

Generating a spatiotemporal $K$-function plot is frequently adopted to analyze point patterns by domain experts in a wide range of application domains, including criminology, transportation science, urban planning, and epidemiology. However, with the high worst-case time complexity of computing a spatiotemporal $K$-function plot, the state-of-the-art methods are unable to efficiently (or feasibly) support this tool. To overcome this issue, we develop Distribution-aNd-Aggregation (DNA), which is the first solution that can reduce the worst-case time complexity for supporting this tool. Experiment results on four large-scale location datasets show that DNA achieves speedups of 4.58x to 57.42x over the state-of-the-art methods, without incurring significant space overhead. The implementation of all methods can be found in https://github.com/edisonchan2013928/DNA.