TY - JOUR
T1 - Fast augmentation algorithms for network kernel density visualization
AU - Chan, Tsz Nam
AU - Li, Zhe
AU - U, Leong Hou
AU - Xu, Jianliang
AU - Cheng, Reynold
N1 - Funding Information:
This work was supported by the National Key Research and Development Plan of China (No.2019YFB2102100), the Science and Technology Development Fund Macau (SKL-IOTSC-2021-2023, 0015/2019/AKP), University of Macau (MYRG2019- 00119-FST), Guangdong Basic and Applied Basic Research Foundation (Project No. 2019B1515130001), the Research Grants Council of Hong Kong (RGC Projects HKBU 12201018, HKU 17229116 and 17205015), University of Hong Kong (Projects 104005858, 104005994), HKU-TCL Joint Research Center for Artificial Intelligence (Project no. 200009430), and Guangdong-Hong Kong-Macau Joint Laboratory Program 2020 (Project No: 2020B1212030009).
PY - 2021/5
Y1 - 2021/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85115120399&partnerID=8YFLogxK
U2 - 10.14778/3461535.3461540
DO - 10.14778/3461535.3461540
M3 - Conference article
AN - SCOPUS:85115120399
SN - 2150-8097
VL - 14
SP - 1503
EP - 1516
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 9
T2 - 47th International Conference on Very Large Data Bases, VLDB 2021
Y2 - 16 August 2021 through 20 August 2021
ER -
