Fast augmentation algorithms for network kernel density visualization

Tsz Nam Chan, Zhe Li, Leong Hou U, Jianliang Xu, Reynold Cheng

Research output: Contribution to journalConference articlepeer-review

10 Citations (Scopus)


Network kernel density visualization, or NKDV, has been extensively used to visualize spatial data points in various domains, including traffic accident hotspot detection, crime hotspot detection, disease outbreak detection, and business and urban planning. Due to a wide range of applications for NKDV, some geographical software, e.g., ArcGIS, can also support this operation. However, computing NKDV is very time-consuming. Although NKDV has been used for more than a decade in different domains, existing algorithms are not scalable to million-sized datasets. To address this issue, we propose three efficient methods in this paper, namely aggregate distance augmentation (ADA), interval augmentation (IA), and hybrid augmentation (HA), which can significantly reduce the time complexity for computing NKDV. In our experiments, ADA, IA and HA can achieve at least 5x to 10x speedup, compared with the state-of-the-art solutions.

Original languageEnglish
Pages (from-to)1503-1516
Number of pages14
JournalProceedings of the VLDB Endowment
Issue number9
Publication statusPublished - May 2021
Event47th International Conference on Very Large Data Bases, VLDB 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Scopus Subject Areas

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


Dive into the research topics of 'Fast augmentation algorithms for network kernel density visualization'. Together they form a unique fingerprint.

Cite this