Parallel In-Memory Trajectory-based Spatiotemporal Topological Join

Suprio Ray, Angela Demke Brown, Nick Koudas, Rolando Blanco, Anil K. Goel

IEEE Conference on Big Data, Santa Clara, California, October 2015

 

Abstract

The explosive growth of spatiotemporal and spatial data is fueling the emergence and growth of many spatiotemporal applications. Many of these applications are characterized by complex spatiotemporal queries. An important category of such queries is the trajectory-based spatiotemporal topological join queries, which combine a trajectory dataset and a spatial objects dataset based on spatiotemporal predicates. Although these queries have many important use cases, they have not received much attention from the research community. We systematically evaluate several applicable in-memory spatiotemporal topological join algorithms, using existing trajectory index (TB-tree) and spatial index (STR). We show that even the best among these algorithms is long running and not scalable. To address the performance problems of these algorithms we introduce PISTON, a parallel in-memory indexing system targeted for spatiotemporal topological join. With extensive evaluations, we demonstrate that even the single-threaded performance of PISTON is significantly better than the applicable approaches that use existing trajectory and spatial indexes. Moreover, the parallel performance of PISTON is orders of magnitude better than these approaches.

 

Manuscript

Pdf

 

Bibtex

Bib