Accompanying Trajectory Query Based on Secondary Temporal and Spatial Indexing
With the proliferation of mobile sensor devices,an increasing amount of position data is being collected,and the scale of trajectory data also grows rapidly.It has always been a challenge to find the top-k trajectories most similar to a given query trajectory from massive spatial-temporal data.Existing trajectory-query methods comprises three main stages:(1)offline trajectory indexing on a massive dataset,(2)searching for candidate trajectories similar to the query trajectory based on the indexed structure,and(3)computing the precise similarity between the query trajectory and candidate trajectories,and returning the top-k most similar trajectories.However,most existing methods fail to effectively exploit the temporal and spatial information during trajectory clustering indexing,Trajectories with low temporal similarity are mistakenly partitioned into the same index,degrading query accuracy and efficiency.Furthermore,existing spatial-temporal trajectory similarity-calculation methods involve numerous unnecessary operations,resulting in low query efficiency.To address these issues,this paper proposes a novel secondary trajectory index structure.Firstly,a trajectory is divided into sub-trajectories by a sliding time window.Then,sub-trajectories are clustered for first-level indexing based on their time slots.Then,sub-trajectories within the same time slot are grouped into second-level spatial clusters.Sub-trajectories with continuous identical locations are partitioned into the same spatial-temporal bucket by a hash algorithm.Compared to existing indexing methods,this approach provides better distinction between different trajectories during indexing,resulting in more strict filtering conditions in the query process,reducing the size of the candidate trajectory set.To tackle the computational efficiency problem of existing trajectory similarity calculation methods,we propose a trajectory similarity calculation method based on the constraints of time difference,eliminating many unnec-essary location comparisons and thus reducing the computational complexity of trajectory similarity calculation.Additionally,we devise a new variant of the similarity calculation approach based on upper and lower bound filtering.This scheme further reduces unnecessary computations during the search of accompanying trajectories.Finally,we conduct experiments to evaluate the effectiveness of the proposed method based on four large-scale real trajectory datasets.The experimental results demonstrate that the proposed method achieves 9 to 20 times faster trajectory retrieval efficiency than state-of-the-art approaches,confirming the effectiveness of the algorithms.
NETL
NSTL
万方数据
