时空轨迹多层级相似子段匹配方法

Multi‑level Similarity Sub‑segment Matching Method for Spatiotemporal Trajectory

轨迹子段匹配是轨迹数据挖掘的重要手段,针对其计算复杂度较高、受噪声影响大的问题,提出了一种融合自适应希尔伯特地理网格编码的多层级轨迹编码树结构,在可接受的建树代价下,形成了从轨迹整段到最小片段的层次化组织形式和子段从属关系表达结构,并在轨迹片段编码树的基础上,设计了相似子段匹配算法,将复杂的空间计算转化为空间编码的字符串前缀匹配操作,极大地降低轨迹子段匹配的计算复杂度。实际轨迹数据的实验表明,在不影响匹配准确率的前提下,提出的子段匹配方法的效率与基于经典距离的相似性度量方法相比,有超过一个数量级的性能提升。

Objectives:Trajectory subsegment matching is an important part of trajectory pattern mining.Its applications span many scenarios,such as user recommendation,abnormal movement detection and pre⁃vention of infectious diseases.Traditional trajectory matching methods are mainly based on classical dis⁃tances or similarity measures,which are of high complexity and the accuracy is seriously affected by data noise.Methods:We firstly propose a multi-level trajectory code tree structure that integrates adaptive Hil⁃bert geographic grid coding.A hierarchical organizational form and sub-segment subordinate relationship expression structure are formed from the entire segment of the trajectory to the smallest segment.Then a sub-segment similarity matching algorithm is designed based on the trajectory segment code tree to trans⁃form complex spatial calculation into string matching operation,which greatly reduces the computational complexity of similar matching of sub-segments.Results:Experiments on actual trajectory data show that the efficiency of the proposed method achieved more than an order of magnitude improvement over the clas⁃sical distance-based similarity measurement method without affecting accuracy.Conclusions:We proposed trajectory subsegment matching method greatly reduce the computational complexity with acceptable accu⁃racy,which has high application value in the field of multi-granulate trajectory pattern mining and similarity analysis.