Generating geospatial heatmaps : Optimizing point-region quadtrees for window queries

Sammanfattning: This study aims to investigate and identify how to effectively generate blurred geospatial heatmaps for use in geo-spatial map engines. We focus on how to store the points in a way that facilitates efficient window querying, with support for zoom-level handling. We decide on primarily using a Morton-ordered variant of the point-region quadtree, which we name a HeatMap Quadtree (HMQ). The nodes of the HMQ each have access to the points they contain, through storing the number of points and the lower bound of where to look at in the input point set, which we also store in Morton order. The HMQ also has the functionality to allow for window querying at different levels of detail. We parallelize the generation of the HMQ as well as the Gaussian blurring of the raster resulting from the window query using CUDA, and compare this implementation with that of two naive solutions as well as a linear point-region quadtree. In conclusion we find that the HMQ provides a significant improvement in window querying time, at the cost of additional construction time.