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

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

郭宁, 熊伟, 欧阳雪, 杨岸然, 吴烨, 陈荦, 景宁

文章导航 > 武汉大学学报 ● 信息科学版 > 优先出版

郭宁, 熊伟, 欧阳雪, 杨岸然, 吴烨, 陈荦, 景宁. 时空轨迹多层级相似子段匹配方法[J]. 武汉大学学报 ● 信息科学版. doi: 10.13203/j.whugis20200170

引用本文:

郭宁, 熊伟, 欧阳雪, 杨岸然, 吴烨, 陈荦, 景宁. 时空轨迹多层级相似子段匹配方法[J]. 武汉大学学报 ● 信息科学版. doi: 10.13203/j.whugis20200170

GUO Ning, XIONG Wei, OUYANG Xue, YANG Anran, WU Ye, CHEN Luo, JING Ning. Multi-level Similarity Sub-segment Matching Method for Spatiotemporal Trajectory[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20200170

Citation:

GUO Ning, XIONG Wei, OUYANG Xue, YANG Anran, WU Ye, CHEN Luo, JING Ning. Multi-level Similarity Sub-segment Matching Method for Spatiotemporal Trajectory[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20200170

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

doi: 10.13203/j.whugis20200170

郭宁^1,2,
熊伟^2, ,,
欧阳雪²,
杨岸然²,
吴烨²,
陈荦²,
景宁²

1 军事科学院战争研究院, 北京, 100091;
2 国防科技大学电子科学学院, 湖南长沙, 410073

基金项目:

国家自然科学基金（41971362，41871284）

作者简介:
郭宁,博士,研究方向为时空数据建模与分析、空间数据库与GIS。guoning10@nudt.edu.cn

中图分类号: P208

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

GUO Ning^1,2,
XIONG Wei^{2
, ,},
OUYANG Xue²,
YANG Anran²,
WU Ye²,
CHEN Luo²,
JING Ning²

1 Institute of War, Academy of Military Sciences, Beijing 100091, China;
2 College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China

Funds:

The National Natural Science Foundation of China (41971362, 41871284)

摘要: 轨迹子段匹配是轨迹数据挖掘的重要手段，针对其计算复杂度较高、受噪声影响大的问题，本文提出一种融合了自适应希尔伯特地理网格编码的多层级轨迹编码树结构，在可接受的建树代价下，形成了从轨迹整段到最小片段的层次化组织形式和子段从属关系表达结构，并在轨迹片段编码树的基础上设计了相似子段匹配算法，将复杂的空间计算转化为空间编码的字符串前缀匹配操作，极大地降低轨迹子段匹配的计算复杂度。实际轨迹数据上的实验表明，在不影响匹配准确率的前提下，本文提出的子段匹配方法的效率相比于基于经典距离的相似性度量方法获得了超过一个数量级的性能提升。
- 子段匹配 /
- 相似性 /
- 多层级 /
- 编码树 /
- 轨迹分段
Abstract: Addressing the problem of high complexity of trajectory sub-segment similarity matching and result sensitivity of trajectory noise, this paper proposes 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, and a sub-segment similarity matching algorithm is designed on the basis of 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. 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.
- sub-segment match /
- similarity /
- multi-level /
- code tree /
- trajectory segmentation

[1]	Keogh E, Ratanamahatana C A. Exact indexing of dynamic time warping[J]. Knowledge and information systems. 2005, 7(3):358-386
[2]	Lim E-C, Shim C-B. Similarity search algorithm for efficient sub-trajectory matching in moving databases[C]. In International Conference on Computational Science. 2007:821-828.
[3]	Godau M. A Natural Metric for Curves -Computing the Distance for Polygonal Chains and Approximation Algorithms[C]. In Symposium on Theoretical Aspects of Computer Science. 1991:127-136.
[4]	Buchin K, Buchin M, Gudmundsson J, et al. Detecting commuting patterns by clustering subtrajectories[J]. International Journal of Computational Geometry & Applications. 2011, 21(03):253-282.
[5]	Buchin K, Buchin M, Van Kreveld M, et al. Finding long and similar parts of trajectories[J]. Computational Geometry. 2011, 44(9):465-476.
[6]	Xie M. EDS:a segment-based distance measure for sub-trajectory similarity search[C]. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014:1609-1610.
[7]	Chen Y, Shen H, Tian H. Clustering subtrajectories of moving objects based on a distance metric with multi-dimensional weights[C]. In 2014 Sixth International Symposium on Parallel Architectures, Algorithms and Programming. 2014:203-208.
[8]	Furtado A S, Kopanaki D, Alvares L O, et al. Multidimensional similarity measuring for semantic trajectories[J]. Transactions in GIS. 2016, 20(2):280-298.
[9]	Mao Y, Zhong H, Xiao X, et al. A segment-based trajectory similarity measure in the urban transportation systems[J]. Sensors. 2017, 17(3):524.
[10]	Yoo J-J, Loh W-K, Whang K-Y. Indexable sub-trajectory matching using multi-segment approximation:a partition-and-stitch framework[J]. The Journal of Supercomputing. 2019:1-29.
[11]	Vlachos M, Kollios G, Gunopulos D. Discovering Similar Multidimensional Trajectories[J]. Proc. of the 18th Int. Conf. on Data Engineering, 2002.
[12]	Chen L, Ng R. On the marriage of lp-norms and edit distance[C]. In Proceedings of the Thirtieth International Conference on Very Large Data Bases, Volume 30. 2004:792-803.
[13]	Lei C, Özsu M T, Oria V. Robust and fast similarity search for moving object trajectories[C]. In ACM SIGMOD International Conference on Management of Data. 2005.
[14]	Hong Van L, Takasu A. An efficient distributed index for geospatial databases[C]. In Database and Expert Systems Applications. 2015:28-42.
[15]	Lu N, Cheng C, Jin A, et al. An index and retrieval method of spatial data based on GeoSOT global discrete grid system[C]. In 2013 IEEE International Geoscience and Remote Sensing Symposium-IGARSS. July 2013:4519-4522.
[16]	Morton G M. A computer oriented geodetic data base and a new technique in file sequencing[J]. 1966.

[1]	赵云鹏, 孙群, 刘新贵, 程绵绵, 俞童, 李元復. 面向地理实体的语义相似性度量方法及其在道路匹配中的应用 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis20190039
[2]	张萍, 李必军, 郑玲, 王建培. 一种基于改进LCSS的相似轨迹提取方法 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis20180406
[3]	职露, 余旭初, 邹滨, 刘冰. 多层级二值模式的高光谱影像空-谱分类 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis20180004
[4]	李兆兴, 翟京生, 武芳. 线要素综合的形状相似性评价方法 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis20180164
[5]	朱杰, 游雄, 夏青. 利用作战任务本体计算战场环境要素语义相似性 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis20170409
[6]	朱进, 胡斌, 邵华. 基于多重运动特征的轨迹相似性度量模型 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis20150594
[7]	张卡, 盛业华, 管忠诚, 李佳. 基于NSCT的立体影像匹配相似性测度计算 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis20130346
[8]	郭继发, 刘玉洁, 毛健, 崔铁军. 高阶模糊区域的交叉拓扑关系形式化研究 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis20120691
[9]	陈科, 王家耀, 成毅, 谢明霞. 利用流形学习进行空间信息服务分类 . 武汉大学学报 ● 信息科学版,
[10]	孟妮娜, 艾廷华, 周校东. 顾及排序差异的对象群邻近关系相似性计算 . 武汉大学学报 ● 信息科学版,
[11]	许俊奎, 武芳, 钱海忠, 马芳博. 一种空间关系相似性约束的居民地匹配算法 . 武汉大学学报 ● 信息科学版,
[12]	安晓亚, 孙群, 尉伯虎. 利用相似性度量的不同比例尺地图数据网状要素匹配算法 . 武汉大学学报 ● 信息科学版,
[13]	孟妮娜, 艾廷华, 周校东. 建筑群邻近关系相似性计算 . 武汉大学学报 ● 信息科学版,
[14]	林立宇, 茅力非, 王雷光, 秦前清. 一种基于分段线性系数变换的编码预处理算法 . 武汉大学学报 ● 信息科学版,
[15]	王育红, 陈军. 基于实例的GIS数据库模式匹配方法 . 武汉大学学报 ● 信息科学版,
[16]	黄培之. 基于等高线特性的三维表面重建方法的研究 . 武汉大学学报 ● 信息科学版,
[17]	郭庆胜, 丁虹. 基于栅格数据的面状目标空间方向相似性研究 . 武汉大学学报 ● 信息科学版, doi: 10.13203/j.whugis2004.05.016
[18]	邵巨良. 无需相似性量测的多片影像匹配 . 武汉大学学报 ● 信息科学版,
[19]	曾湧, 廖明生, 张剑清, 沈未名. 保持匹配一致性的遥感影像压缩编码 . 武汉大学学报 ● 信息科学版,
[20]	王桥. 线状地图要素的自相似性分析及其自动综合 . 武汉大学学报 ● 信息科学版,

WeChat

点击查看大图

计量

文章访问数: 475
HTML全文浏览量: 92
PDF下载量: 22
被引次数: 0

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

doi: 10.13203/j.whugis20200170

1 军事科学院战争研究院, 北京, 100091;

2 国防科技大学电子科学学院, 湖南长沙, 410073

基金项目:

国家自然科学基金（41971362，41871284）

作者简介:
郭宁,博士,研究方向为时空数据建模与分析、空间数据库与GIS。guoning10@nudt.edu.cn

收稿日期: 2020-04-17
网络出版日期: 2021-05-07

中图分类号: P208

关键词:

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

English Abstract

郭宁, 熊伟, 欧阳雪, 杨岸然, 吴烨, 陈荦, 景宁. 时空轨迹多层级相似子段匹配方法[J]. 武汉大学学报 ● 信息科学版. doi: 10.13203/j.whugis20200170

引用本文:

郭宁, 熊伟, 欧阳雪, 杨岸然, 吴烨, 陈荦, 景宁. 时空轨迹多层级相似子段匹配方法[J]. 武汉大学学报 ● 信息科学版. doi: 10.13203/j.whugis20200170

GUO Ning, XIONG Wei, OUYANG Xue, YANG Anran, WU Ye, CHEN Luo, JING Ning. Multi-level Similarity Sub-segment Matching Method for Spatiotemporal Trajectory[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20200170

Citation:

GUO Ning, XIONG Wei, OUYANG Xue, YANG Anran, WU Ye, CHEN Luo, JING Ning. Multi-level Similarity Sub-segment Matching Method for Spatiotemporal Trajectory[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20200170

全文HTML

参考文献 (16)

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

我要投稿

投稿攻略

联系我们

二维码