SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization

Tsz Nam Chan; Leong Hou U; Byron Koon Kau Choi; Jianliang Xu

doi:10.1145/3514221.3517823

SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization

Tsz Nam Chan
, Leong Hou U
, Byron Koon Kau Choi
, Jianliang Xu

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

13 Citations (Scopus)

Abstract

Kernel Density Visualization (KDV) has been extensively used in a wide range of applications, including traffic accident hotspot detection, crime hotspot detection, disease outbreak detection, and ecological modeling. However, KDV is a computationally expensive operation, which is not scalable to large datasets (e.g., million-scale data points) and high resolution sizes (e.g., 1920 × 1080). To significantly improve the efficiency for generating KDV, we develop two efficient Sweep Line AlgorithMs (SLAM), which can theoretically reduce the time complexity for generating KDV. By incorporating the resolution-aware optimization (RAO) into SLAM, we can further achieve the lowest time complexity for generating KDV. Our extensive experiments on four large-scale real datasets (up to 4.33 million data points) show that all our methods can achieve one to two-order-of-magnitude speedup in many test cases and efficiently support KDV with exploratory operations (e.g., zooming and panning) compared with the state-of-the-art solutions.

Original language	English
Title of host publication	SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data
Publisher	Association for Computing Machinery (ACM)
Pages	2120–2134
Number of pages	15
ISBN (Electronic)	9781450392495
ISBN (Print)	9781450392495
DOIs	https://doi.org/10.1145/3514221.3517823
Publication status	Published - Jun 2022
Event	ACM SIGMOD International Conference on Management of Data, SIGMOD 2022 - Virtual, Online, Philadelphia, United States Duration: 12 Jun 2022 → 17 Jun 2022 https://2022.sigmod.org/ https://dl.acm.org/doi/proceedings/10.1145/3514221

Publication series

Name	Proceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)	0730-8078

Conference

Conference	ACM SIGMOD International Conference on Management of Data, SIGMOD 2022
Country/Territory	United States
City	Philadelphia
Period	12/06/22 → 17/06/22
Internet address	https://2022.sigmod.org/ https://dl.acm.org/doi/proceedings/10.1145/3514221

User-Defined Keywords

Kernel density visualization
SLAM
hotspot detection
reduce the time complexity
exploratory operations
kernel density visualization

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1145/3514221.3517823

Cite this

Chan, T. N., U, L. H., Choi, B. K. K., & Xu, J. (2022). SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization. In SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data (pp. 2120–2134). (Proceedings of the ACM SIGMOD International Conference on Management of Data). Association for Computing Machinery (ACM). https://doi.org/10.1145/3514221.3517823

@inproceedings{6646c1c951614470b06dd866c7447d76,

title = "SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization",

abstract = "Kernel Density Visualization (KDV) has been extensively used in a wide range of applications, including traffic accident hotspot detection, crime hotspot detection, disease outbreak detection, and ecological modeling. However, KDV is a computationally expensive operation, which is not scalable to large datasets (e.g., million-scale data points) and high resolution sizes (e.g., 1920 × 1080). To significantly improve the efficiency for generating KDV, we develop two efficient Sweep Line AlgorithMs (SLAM), which can theoretically reduce the time complexity for generating KDV. By incorporating the resolution-aware optimization (RAO) into SLAM, we can further achieve the lowest time complexity for generating KDV. Our extensive experiments on four large-scale real datasets (up to 4.33 million data points) show that all our methods can achieve one to two-order-of-magnitude speedup in many test cases and efficiently support KDV with exploratory operations (e.g., zooming and panning) compared with the state-of-the-art solutions.",

keywords = "Kernel density visualization, SLAM, hotspot detection, reduce the time complexity, exploratory operations, kernel density visualization",

author = "Chan, \{Tsz Nam\} and U, \{Leong Hou\} and Choi, \{Byron Koon Kau\} and Jianliang Xu",

note = "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), IRCMS/19-20/H01, Hong Kong RGC Projects 12201518, 12202221, C2004-21GF, and C6030-18GF. Publisher Copyright: {\textcopyright} 2022 ACM.; ACM SIGMOD International Conference on Management of Data, SIGMOD 2022 ; Conference date: 12-06-2022 Through 17-06-2022",

year = "2022",

month = jun,

doi = "10.1145/3514221.3517823",

language = "English",

isbn = "9781450392495",

series = "Proceedings of the ACM SIGMOD International Conference on Management of Data",

publisher = "Association for Computing Machinery (ACM)",

pages = "2120–2134",

booktitle = "SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data",

address = "United States",

url = "https://2022.sigmod.org/, https://dl.acm.org/doi/proceedings/10.1145/3514221",

}

Chan, TN, U, LH, Choi, BKK & Xu, J 2022, SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization. in SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data. Proceedings of the ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery (ACM), pp. 2120–2134, ACM SIGMOD International Conference on Management of Data, SIGMOD 2022, Philadelphia, Pennsylvania, United States, 12/06/22. https://doi.org/10.1145/3514221.3517823

SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization. / Chan, Tsz Nam; U, Leong Hou; Choi, Byron Koon Kau et al.
SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data. Association for Computing Machinery (ACM), 2022. p. 2120–2134 (Proceedings of the ACM SIGMOD International Conference on Management of Data).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - SLAM

T2 - ACM SIGMOD International Conference on Management of Data, SIGMOD 2022

AU - Chan, Tsz Nam

AU - U, Leong Hou

AU - Choi, Byron Koon Kau

AU - Xu, Jianliang

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), IRCMS/19-20/H01, Hong Kong RGC Projects 12201518, 12202221, C2004-21GF, and C6030-18GF. Publisher Copyright: © 2022 ACM.

PY - 2022/6

Y1 - 2022/6

N2 - Kernel Density Visualization (KDV) has been extensively used in a wide range of applications, including traffic accident hotspot detection, crime hotspot detection, disease outbreak detection, and ecological modeling. However, KDV is a computationally expensive operation, which is not scalable to large datasets (e.g., million-scale data points) and high resolution sizes (e.g., 1920 × 1080). To significantly improve the efficiency for generating KDV, we develop two efficient Sweep Line AlgorithMs (SLAM), which can theoretically reduce the time complexity for generating KDV. By incorporating the resolution-aware optimization (RAO) into SLAM, we can further achieve the lowest time complexity for generating KDV. Our extensive experiments on four large-scale real datasets (up to 4.33 million data points) show that all our methods can achieve one to two-order-of-magnitude speedup in many test cases and efficiently support KDV with exploratory operations (e.g., zooming and panning) compared with the state-of-the-art solutions.

AB - Kernel Density Visualization (KDV) has been extensively used in a wide range of applications, including traffic accident hotspot detection, crime hotspot detection, disease outbreak detection, and ecological modeling. However, KDV is a computationally expensive operation, which is not scalable to large datasets (e.g., million-scale data points) and high resolution sizes (e.g., 1920 × 1080). To significantly improve the efficiency for generating KDV, we develop two efficient Sweep Line AlgorithMs (SLAM), which can theoretically reduce the time complexity for generating KDV. By incorporating the resolution-aware optimization (RAO) into SLAM, we can further achieve the lowest time complexity for generating KDV. Our extensive experiments on four large-scale real datasets (up to 4.33 million data points) show that all our methods can achieve one to two-order-of-magnitude speedup in many test cases and efficiently support KDV with exploratory operations (e.g., zooming and panning) compared with the state-of-the-art solutions.

KW - Kernel density visualization

KW - SLAM

KW - hotspot detection

KW - reduce the time complexity

KW - exploratory operations

KW - kernel density visualization

UR - https://www.scopus.com/pages/publications/85130334524

U2 - 10.1145/3514221.3517823

DO - 10.1145/3514221.3517823

M3 - Conference proceeding

SN - 9781450392495

T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data

SP - 2120

EP - 2134

BT - SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data

PB - Association for Computing Machinery (ACM)

Y2 - 12 June 2022 through 17 June 2022

ER -

SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization

Abstract

Publication series

Conference

User-Defined Keywords

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this