QUAD: Quadratic-Bound-based Kernel Density Visualization

Tsz Nam Chan, Reynold Cheng, Man Lung Yiu

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

19 Citations (Scopus)


Kernel density visualization, or KDV, is used to view and understand data points in various domains, including traffic or crime hotspot detection, ecological modeling, chemical geology, and physical modeling. Existing solutions, which are based on computing kernel density (KDE) functions, are computationally expensive. Our goal is to improve the performance of KDV, in order to support large datasets (e.g., one million points) and high screen resolutions (e.g., 1280 x 960 pixels). We examine two widely-used variants of KDV, namely approximate kernel density visualization (EKDV) and thresholded kernel density visualization (TKDV). For these two operations, we develop fast solution, called QUAD, by deriving quadratic bounds of KDE functions for different types of kernel functions, including Gaussian, triangular etc. We further adopt a progressive visualization framework for KDV, in order to stream partial visualization results to users continuously. Extensive experiment results show that our new KDV techniques can provide at least one-order-of-magnitude speedup over existing methods, without degrading visualization quality. We further show that QUAD can produce the reasonable visualization results in real-time (0.5 sec) by combining the progressive visualization framework in single machine setting without using GPU and parallel computation.

Original languageEnglish
Title of host publicationSIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
PublisherAssociation for Computing Machinery (ACM)
Number of pages16
ISBN (Electronic)9781450367356
Publication statusPublished - 11 Jun 2020
EventACM SIGMOD International Conference on Management of Data, SIGMOD 2020 - Portland, United States
Duration: 14 Jun 202019 Jun 2020

Publication series

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


ConferenceACM SIGMOD International Conference on Management of Data, SIGMOD 2020
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • KDV
  • kernel density visualization
  • QUAD
  • quadratic bounds


Dive into the research topics of 'QUAD: Quadratic-Bound-based Kernel Density Visualization'. Together they form a unique fingerprint.

Cite this