Efficient Parallel Processing of Semantic Trajectory Similarity Joins
Shuo Shang, Chengrui Huang, Lisi Chen · IEEE Internet of Things Journal · 2024
Matching similar pairs of trajectories, called trajectory similarity join, is a fundamental functionality for the Internet of Everything (IoE). We obverse that keyword-augmented trajectories are becoming increasingly popular. In this light, we investigate semantic trajectory similarity (STS) join that consists of two subproblems, threshold-based STS Join and top-k STS (k-STS) Join. Each semantic trajectory is a sequence of geo-textual objects with both location and text information. Specifically, given two sets of semantic trajectories and a threshold$\theta $or result number k, the STS Join returns all pairs of semantic trajectories from the two sets with spatio-textual similarity no less than$\theta $, and the k-STS Join returns k most similar pairs of semantic trajectories from the two sets. To enable efficient STS and k-STS Joins processing on large sets of semantic trajectories, we present a two-phase parallel search algorithm. We first group semantic trajectories based on their text information. The algorithm’s per-group searches are independent of each other and thus can be performed in parallel. We generate spatial and textual summaries for each trajectory batch and develop batch filtering techniques to prune unqualified trajectory pairs in a batch mode. Next, we propose a divide-and-conquer algorithm to derive bounds of spatial similarity and textual similarity between two semantic trajectories, which enable us filter out dissimilar trajectory pairs efficiently. Further, hierarchical batch filtering join algorithm is developed to process k-STS Join. Experimental study with large semantic trajectory data confirms that our algorithm of processing semantic trajectory join is capable of substantially outperforming well-designed baselines.