SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

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 languageEnglish
Title of host publicationSIGMOD '22: Proceedings of the 2022 International Conference on Management of Data
PublisherAssociation for Computing Machinery (ACM)
Pages2120–2134
Number of pages15
ISBN (Electronic)9781450392495
ISBN (Print)9781450392495
DOIs
Publication statusPublished - Jun 2022
EventACM SIGMOD International Conference on Management of Data, SIGMOD 2022 - Philadelphia, Philadelphia, United States
Duration: 12 Jun 202217 Jun 2022
https://2022.sigmod.org/

Publication series

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

Conference

ConferenceACM SIGMOD International Conference on Management of Data, SIGMOD 2022
Country/TerritoryUnited States
CityPhiladelphia
Period12/06/2217/06/22
Internet address

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

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

Fingerprint

Dive into the research topics of 'SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization'. Together they form a unique fingerprint.

Cite this