A Fast and Accurate Block Compression Solution for Spatiotemporal Kernel Density Visualization

摘要

Spatiotemporal Kernel Density Visualization (STKDV) has been widely used across various domains in geospatial analysis, e.g., urban planning, traffic/traffic accident hotspot analysis, crime hotspot analysis, and disease spread modeling. However, STKDV is a computationally expensive tool, which has been complained by many domain experts. Although many recent solutions, including the sliding-window-based solution (SWS) and the prefix-matrix-based solution (PREFIX), have been proposed for improving the efficiency of generating an exact STKDV, these solutions still cannot be scalable to handle large-scale location datasets. To tackle this efficiency issue, we propose the pioneering block compression solution, called COMP, which can compress (or represent) a location dataset by a small amount of blocks. By combining COMP with the existing exact solutions, i.e., SWS and PREFIX, we show that COMPSWS and COMPPREFIX can generate approximate STKDV with an ε-absolute error guarantee based on properly tuning the block size. Experimental results on four large-scale location datasets (up to 6.782 million data points) also verify that COMPSWS and COMP_PREFIX can achieve speedups of 4.1x to 677.16x and 1.45x to 143.52x compared with SWS and PREFIX, respectively, without degrading the visualization results. The code of this paper can be found in https://github.com/YovelaZ/COMP.