Spatiotemporal range pattern queries on large-scale co-movement pattern datasets

摘要

Thanks to recent prevalence of location sensors, collecting massive spatiotemporal datasets containing moving object trajectories has become possible, providing an exceptional opportunity to derive interesting insights about behavior of the moving objects such as people, animals, and vehicles. In particular, mining patterns from co-movements of objects (such as players of a sports team, joints of a person while walking, and cars in a transportation network) can lead to the discovery of interesting patterns (e.g., offense tactics of the sports team, gait signature of the person, and driving behaviors causing heavy traffic). With our prior work, we proposed efficient algorithms to mine frequent co-movement patterns from trajectory datasets. In this paper, we focus on the problem of efficient query processing on massive co-movement pattern datasets generated by such pattern mining algorithms. Given a dataset of frequent co-movement patterns, various spatiotemporal queries can be posed to retrieve relevant patterns among all generated patterns from the pattern dataset. We term such queries “pattern queries”. Co-movement patterns are often numerous due to combinatorial complexity of such patterns, and therefore, co-movement pattern datasets grow very large, rendering naive execution of the pattern queries ineffective. In this paper, we propose novel index structures and query processing algorithms for efficient answering of two families of range pattern queries on massive co-movement pattern datasets, namely, spatial range pattern queries and temporal range pattern queries. Our extensive empirical studies with three real datasets have demonstrated the efficiency of the proposed methods.