PLAN: Fast and Approximate Gaussian Kernel Density Visualization in Road Networks

Network Kernel Density Visualization (NKDV) is a widely used spatial analysis tool in various communities, including transportation science, criminology, and urban planning. However, generating NKDV is very time-consuming, which does not scale to support large-scale datasets. Although many efficient algorithms have been developed for supporting this tool, most of these algorithms cannot be used for handling the most popular Gaussian kernel function. To tackle this issue, we first develop the pioneering Piecewise-Linear Approximate solutioN (PLAN), which can simultaneously (1) reduce the time complexity, (2) retain the similar space complexity, and (3) achieve the accuracy guarantee for generating NKDV with the Gaussian kernel. By providing further optimization for PLAN, our best method, called PLAN+, can achieve the lowest time complexity for supporting this tool. Experiment results on four large-scale datasets verify that both PLAN and PLAN+ achieve 32.47x to 2936.88x speedups, only incur 1.26x to 2.15x space overhead, and provide accurate NKDV results compared with the state-of-the-art solution (SOTA). The implementation of all methods can be found in https://github.com/edisonchan2013928/PLAN.