Hybrid Indexing for Parallel Analysis of Spatiotemporal Point Patterns
Alexander Hohl, Irene Amil Casas, Eric M. Delmelle, Wenwu Tang · International Conference on GIScience Short Paper Proceedings · 2016
High-performance parallel computing outperforms desktop workstations for computationally demanding problem solving.Domain decomposition and spatial indexing are widely used to accelerate spatial search.A single index method for spatiotemporal data processing lacks retrieval efficiency for massive computation.Combining multiple indexing methods to a hybrid spatiotemporal index holds potential for addressing this data retrieval challenge.We perform adaptive octree decomposition of the spatiotemporal domain and build local k-d trees to accelerate nearest neighbour search for space-time kernel density estimation (STKDE).Our parallel implementation reaches substantial speedup compared to sequential processing.The hybrid index outperforms octree decomposition alone, especially at lower-levels of parallelization.This approach facilitates finer-scale computation, enabling us to discover patterns that would be hidden otherwise.