Parallel Online Similarity Join over Trajectory Streams

摘要

Trajectory Similarity Join (TS-Join), as a fundamental operation in trajectory data analytics, has been extensively investigated by existing studies in data science. However, existing solutions are almost designed for offline static trajectories, which cannot ensure real-time feedback. In addition, the join results retrieved from existing solutions generally contain a large proportion of outdated similar pairs, making them inapplicable to evolving trajectories. In this light, we study a novel problem of online time-aware trajectory similarity join: Given a stream of evolving trajectories, we aim to dynamically discover trajectory pairs whose spatio-temporal similarity is no less than a specified threshold in a real-time manner. We innovatively introduce a time-aware exponential-decaying similarity function to eliminate outdated results. To support real-time querying over large populations of trajectories, we develop a Parallel Online Trajectory Similarity Join (POTSJ) framework with workload balancing techniques. We further enhance join efficiency through pruning strategies and tailored approximation techniques. The POTSJ framework we propose, which incorporates these elements, is capable of processing online TS-Join while simultaneously satisfying three key objectives: real-time result updates, comprehensive trajectory evaluation, and scalability. Extensive experiments on real-world datasets validate the efficiency and scalability of our POTSJ framework in processing online TS-Join.