An Efficient Parallel Mechanism for Processing Trajectory Split-and-Combine
Shuo Shang, Chengrui Huang, Xiaocheng Hu, Lisi Chen · IEEE Internet of Things Journal · 2025
With the increasing availability of time-dependent objects on Social internet of Things (SIoT), taking advantage of this data for SIoT-based route planning and recommendation is becoming increasingly imperative. To facilitate IoT-based route planning and recommendation, Trajectory Search by Locations (TSL) has been serving as a fundamental operation for data cleaning based on personalized requirements. However, existing TSL methods regard each trajectory as an indivisible object of time series. Because that the lengths and spatial distributions of trajectories may vary, traditional TRL methods often fail to return high-quality results, especially when the trajectory data is spare. Such limitation is considered to be a major bottleneck for improving the effectiveness of SIoT-based route planning and recommendation. To address the limitation, we propose a parallel mechanism for handling the problem of Trajectory Search by Locations through Parallel split-and-combine (TSL-Psc). The TSL-Psc problem is described as follows. Given a set of trajectories, a query sequence Q consisting of a sequence of timestamped locations, and a spatio-temporal similarity threshold θ, we retrieve a combined trajectory composed of sub-trajectories that (i) has similarity to Q no less than θ and (ii) contains the minimum number of sub-trajectory combinations. The resulting functionality of TSL-Psc targets a broad range of time-sensitive applications regarding SIoT, including traffic analysis, real-time group route planning, and ridesharing. To enable efficient TSL-Psc computation of trajectory data, we develop a three-phase Joint-Split Parallel Search (JSPS) algorithm on the basis of FSPS and GSPS. JSPS consists of pre-checking, split, and combine phases. We develop a spatial-first expansion algorithm and a temporal-first expansion algorithm that are capable of pruning search space in both spatial and temporal domains. Comprehensive experiments conducted on real-world datasets provide valuable insights into the algorithm’s performance, demonstrating that the proposed TSL-Psc problem formulation produces high-quality outcomes while the search algorithms deliver high-standard efficiency and scalability.