时空轨迹多层级相似子段匹配方法 |
| |
引用本文: | 郭宁,熊伟,欧阳雪,杨岸然,吴烨,陈荦,景宁. 时空轨迹多层级相似子段匹配方法[J]. 武汉大学学报(信息科学版), 2022, 47(9): 1390-1397. DOI: 10.13203/j.whugis20200170 |
| |
作者姓名: | 郭宁 熊伟 欧阳雪 杨岸然 吴烨 陈荦 景宁 |
| |
作者单位: | 1.军事科学院战争研究院,北京,100091 |
| |
基金项目: | 国家自然科学基金41971362国家自然科学基金41871284 |
| |
摘 要: | 轨迹子段匹配是轨迹数据挖掘的重要手段,针对其计算复杂度较高、受噪声影响大的问题,提出了一种融合自适应希尔伯特地理网格编码的多层级轨迹编码树结构,在可接受的建树代价下,形成了从轨迹整段到最小片段的层次化组织形式和子段从属关系表达结构,并在轨迹片段编码树的基础上,设计了相似子段匹配算法,将复杂的空间计算转化为空间编码的字符串前缀匹配操作,极大地降低轨迹子段匹配的计算复杂度。实际轨迹数据的实验表明,在不影响匹配准确率的前提下,提出的子段匹配方法的效率与基于经典距离的相似性度量方法相比,有超过一个数量级的性能提升。
|
关 键 词: | 子段匹配 相似性 多层级 编码树 轨迹分段 |
收稿时间: | 2020-04-17 |
Multi-level Similarity Sub-segment Matching Method for Spatiotemporal Trajectory |
| |
Affiliation: | 1.Institute of War Research, Academy of Military Sciences, Beijing 100091, China2.College of Electronic Science, National University of Defense Technology, Changsha 410073, China |
| |
Abstract: | 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 prevention of infectious diseases. Traditional trajectory matching methods are mainly based on classical distanc?es 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 Hilbert 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 transform 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 classical distance-based similarity measurement method without affecting accuracy. Conclusions We proposed trajectory subsegment matching method greatly reduce the computational complexity with acceptable accuracy, which has high application value in the field of multi-granulate trajectory pattern mining and similarity analysis. |
| |
Keywords: | |
|
| 点击此处可从《武汉大学学报(信息科学版)》浏览原始摘要信息 |
|
点击此处可从《武汉大学学报(信息科学版)》下载免费的PDF全文 |
|