Scalable Detection of Spatiotemporal Encounters in Historical Movement Data

Abstract

The widespread adoption of location-aware devices is resulting in the generation of large amounts of spatiotemporal movement data, collected and stored in digital repositories. This forms a fertile ground for domain experts and scientists to analyze such historical data and discover interesting movement behavioral patterns. Experts in many domains, such as transportation, logistics and retail, are interested in detecting and understanding movement patterns and behavior of objects in relation to each other. Their insights can point to optimization potential and reveal deviations from planned behavior. In this paper, we focus on the detection of the encounter patterns as one possible type in movement behavior. These patterns refer to objects being close to one another in terms of space and time. We define scalability as a core requirement when dealing with historical movement data, in order to allow the domain expert to set parameters of the encounter detection algorithm. Our approach leverages a designated data structure and requires only a single pass over chronological data, thus resulting in highly scalable and fast technique to detect encounters. Consequently, users are able to explore their data by interactively specifying the spatial and temporal windows that define encounters. We evaluate our proposed method as a function of its input parameters and data size. We instantiate the proposed method on urban public transportation data, where we found a large number of encounters. We show that single encounters emerge into higher level patterns that are of particular interest and value to the domain.