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 community. However, existing solutions are almost designed for offline static trajectories, which cannot guarantee real-time feedback. In addition, the join results retrieved from existing solutions generally contains a large proportion of out-of-date 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 out-of-date results. To support real-time querying over large populations of trajectories, we develop a Parallel Online Trajectory Similarity Join (POTSJ) framework incorporating with well-designed workload balancing techniques. We further enhance join efficiency through effective 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 superiority of our POTSJ framework in processing online TS-Join.