MASS: A Complexity-Optimal Solution for Product Kernel Density Visualization

Product Kernel Density Visualization (product KDV) has been widely used in various fields, including urban planning, epidemiology, traffic science, and crime science. However, product KDV is a time-consuming tool, which does not scale to support large-scale location datasets and high resolution sizes. Even worse, there is a lack of research studies for handling this tool. To tackle the efficiency issues of product KDV, we first develop the new indexing structure, called MAtrix of Search Space (MASS), and then develop two complexity-reduced methods, called MASSCR (the basic version) and MASSOPT (the advanced version). Note that MASSOPT is the first optimal solution (with O(XY+n) time) for generating exact product KDV, i.e., there will be no exact solution with the lower time complexity for supporting this tool in the future. Experimental results with four large-scale location datasets (up to 37.4 million data points) verify that our methods can achieve 3.08x to 135.31x speedups compared with existing methods for supporting this tool. The implementation of all methods can be found in https://github.com/YovelaZ/product_KDV/.