Fast Network K-function-based Spatial Analysis

Tsz Nam Chan, Leong Hou U, Yun Peng, Byron Choi, Jianliang Xu

Research output: Contribution to journalConference articlepeer-review

4 Citations (Scopus)


Network K-function has been the de facto operation for analyzing point patterns in spatial networks, which is widely used in many communities, including geography, ecology, transportation science, social science, and criminology. To analyze a location dataset, domain experts need to generate a network K-function plot that involves computing multiple network K-functions. However, network K-function is a computationally expensive operation that is not feasible to support large-scale datasets, let alone to generate a network K-function plot. To handle this issue, we develop two efficient algorithms, namely count augmentation (CA) and neighbor sharing (NS), which can reduce the worst-case time complexity for computing network K-functions. In addition, we incorporate the advanced shortest path sharing (ASPS) approach into these two methods to further lower the worst-case time complexity for generating network K-function plots. Experiment results on four large-scale location datasets (up to 7.33 million data points) show that our methods can achieve up to 165.85x speedup compared with the state-of-the-art methods.

Original languageEnglish
Pages (from-to)2853-2866
Number of pages14
JournalProceedings of the VLDB Endowment
Issue number11
Publication statusPublished - Jul 2022
Event48th International Conference on Very Large Data Bases, VLDB 2022 - Sydney, Australia
Duration: 5 Sept 20229 Sept 2022

Scopus Subject Areas

  • Computer Science (miscellaneous)
  • Computer Science(all)


Dive into the research topics of 'Fast Network K-function-based Spatial Analysis'. Together they form a unique fingerprint.

Cite this