STARS: A Sampling and Threshold Sharing Solution for Network K-function Analytics

Network K-function analytics is an important tool for different application domains, including transportation science, criminology, and urban planning. Despite this, this tool is computationally demanding, which does not scale to support large datasets. Although the state-of-the-art method, called neighbor sharing (NS), can successfully reduce the time complexity for supporting network K-function analytics, this method is still very slow. To address the efficiency issue, we propose the sampling and threshold sharing solution (STARS), which is the first work that can simultaneously (1) reduce the time complexity, (2) retain the similar space complexity, and (3) achieve the non-trivial absolute error (accuracy) guarantee. Experimental results with four large-scale datasets (up to 8.19 million data points) show that STARS achieves (1) 1.52x to 21.57x speedups, (2) negligible additional space overhead, and (3) negligible practical accuracy degradation compared with NS. The implementation of this paper can be found in https://github.com/fastnsa/STARS/.