一种融合图结构的时空轨迹相似性查询算法

针对海量时空轨迹数据相似性查询速度慢的问题，提出一种融合图结构的时空轨迹相似性查询算法。从空间维和时间维将轨迹建模为图结构中的一条路径，设计了一种同步匹配空间和时间距离的轨迹相似性度量函数。在此基础上，设计了一种结合时间过滤的基于边的倒排索引结构支持轨迹时空相似性查询，同时利用距离上界的剪枝策略提高查询性能。计算返回的相似轨迹集合中每条轨迹的距离并进行排序，得到相似度最高的前k个轨迹。最后将所提算法与NTrajI算法、SHQ算法、SHQT算法在合成数据集和真实数据集上进行实验对比。结果表明：该算法在索引建立、查询效率和查询质量方面均优于其他对比方法，因此是可行而有效的。

A Spatio-Temporal Similarity Query Algorithm for Trajectory Based on Graph Structure

To address the problem of slow similarity query of massive spatio-temporal trajectory data, a similarity query algorithm based on graph structure is proposed. Firstly, the trajectory is modeled as a path with spatial and temporal dimensions in a graph, and a trajectory similarity metric function is designed to match spatial and temporal distances simultaneously. Secondly, based on the similarity metric function, an edge-based inverted index structure combined with time filtering is designed, which supports spatio-temporal similarity query of trajectories while improving query performance using a pruning strategy with distance upper bound. The query algorithm performs distance calculation for each trajectory in the returned set of similar trajectories and sorts to obtain the top k results with the highest similarity. Finally, synthetic dataset and real dataset are used to compare the proposed algorithm with NTrajI algorithm, SHQ algorithm and SHQT algorithm. Experimental results show that the proposed method outperforms the comparison methods in index building and query processing, and obtains higher quality of query results. Therefore, the proposed algorithm is feasible and effective.