An Efficient Algorithm for the Construction of Dynamically Updating Trajectory Networks
Deniz Gurevin, Chris J. Michael, Omer Khan · 2021
Trajectory based spatiotemporal networks (STN) are useful in a wide range of applications, such as crowd behavior analysis. Significant portion of trajectory network based research focuses on optimizing the analysis of STN to characterize, control, and predict network behavior. However, these mining algorithms are typically carried out on a pre-constructed network structure that tracks all moving objects and their trajectories in real time. The construction of such a trajectory network is itself a computationally expensive task and it is becoming a bigger burden with advancements in analysis algorithms. The traditional approach is to construct static networks from the temporal snapshots of trajectory data that cannot handle spatiotemporally changing data. This paper proposes an efficient algorithm that successfully generates and maintains an ST network from raw trajectory data. The proposed method is based on a customized R-Tree based constructor to keep track of object trajectories and their interactions. It avoids redundant updates as trajectories evolve over time, resulting in a significant reduction in STN construction time. Based on the experiments we conducted, our method reduces the number of updates by 71.25% as compared to the static naive STN construction method.