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

GUO Ning; XIONG Wei; OUYANG Xue; YANG Anran; WU Ye; CHEN Luo; JING Ning

doi:10.13203/j.whugis20200170

Volume 47 Issue 9

Sep. 2022

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2022 > 47(9): 1390-1397. > 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, 2022, 47(9): 1390-1397. DOI: 10.13203/j.whugis20200170

Citation:

PDF (4440 KB)

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 Research, Academy of Military Sciences, Beijing 100091, China
2.
College of Electronic Science, National University of Defense Technology, Changsha 410073, China

Funds:

The National Natural Science Foundation of China 41971362

The National Natural Science Foundation of China 41871284

More Information

Author Bio:
GUO Ning, PhD, specializes in spatiotemporal data modeling and analysis, battlefield environment simulation, spatial database and GIS. E-mail: guoning10@nudt.edu.cn
Corresponding author:
XIONG Wei, PhD, associate professor. E-mail: xiongwei@nudt.edu.cn
Received Date: April 16, 2020
Available Online: September 19, 2022
Published Date: September 04, 2022

Graphical Abstract

Abstract

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.
- subsegment match,
- similarity,
- multi-layer,
- code tree,
- trajectory segmentation

FullText(HTML)

References (19)

References

[1]	Lim E C, Shim C B. Similarity Search Algorithm for Efficient Sub-trajectory Matching in Moving Databases[C]// Computational Science-ICCS, Beijing, China, 2007
[2]	Keogh E, Ratanamahatana C A. Exact Indexing of Dynamic Time Warping[J]. Knowledge and Information Systems, 2005, 7(3): 358-386 doi: 10.1007/s10115-004-0154-9
[3]	Buchin K, Buchin M, Gudmundsson J, et al. Detecting Commuting Patterns by Clustering Subtrajectories[M]// Algorithms and Computation. Berlin, Germany: Springer, 2008
[4]	Godau M. A Natural Metric for Curves-Computing the Distance for Polygonal Chains and Approximation Algorithms[C]//The 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, 1991
[5]	Buchin K, Buchin M, Kreveld M, et al. Finding Long and Similar Parts of Trajectories[J]. Computational Geometry, 2011, 44(9): 465-476 doi: 10.1016/j.comgeo.2011.05.004
[6]	Xie M. EDS: A Segment-Based Distance Measure for Sub-trajectory Similarity Search[C]// ACM SIGMOD International Conference on Management of Data, Snowbird, USA, 2014
[7]	Chen Y J, Shen H, Tian H. Clustering Subtrajectories of Moving Objects Based on a Distance Metric with Multi-dimensional Weights[C]//The 6th International Symposium on Parallel Architectures, Algorithms and Programming, Beijing, China, 2014
[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 doi: 10.1111/tgis.12156
[9]	Mao Y C, Zhong H S, Xiao X J, et al. A SegmentBased Trajectory Similarity Measure in the Urban Transportation Systems[J]. Sensors, 2017, 17(3), DOI: org/ 10.3390/s17030524
[10]	Yoo J J, Loh W K, Whang K Y. Indexable SubTrajectory Matching Using Multi-segment Approximation: A Partition-and-Stitch Framework[J]. The Journal of Supercomputing, 2019, 75(9): 6129-6157 doi: 10.1007/s11227-019-02813-w
[11]	Vlachos M, Kollios G, Gunopulos D. Discovering Similar Multidimensional Trajectories[C]//The 18th International Conference on Data Engineering, San Jose, USA, 2002
[12]	Chen L, Ng R. On the Marriage of Lp-Norms and Edit Distance[C]// The 30th International Conference on Very Large Data Bases, Toronto, Canada, 2004
[13]	Chen L, Tamer Özsu M, Oria V. Robust and Fast Similarity Search for Moving Object Trajectories [C]// The 31st International Conference on Management of Data, Baltimore, USA, 2005
[14]	叶小平, 郭欢, 汤庸, 等. 基于相点分析的移动数据索引技术[J]. 计算机学报, 2011, 34(2): 256-274 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201102008.htm Ye Xiaoping, Guo Huan, Tang Yong, et al. Index of Mobile Data Based on Phrase Points Analysis[J]. Chinese Journal of Computers, 2011, 34(2): 256-274 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201102008.htm
[15]	朱庆, 龚俊. 一种改进的真三维R树空间索引方法[J]. 武汉大学学报·信息科学版, 2006(4): 340-343 http://ch.whu.edu.cn/article/id/2438 Zhu Qing, Gong Jun. An I mproved Full 3D R-Tree Spatial Index Method[J]. Geomatics and Information Science of Wuhan University, 2006(4): 340-343 http://ch.whu.edu.cn/article/id/2438
[16]	王飞, 庞悦, 周向东, 等. 一种面向相似查询的轨迹索引方法[J]. 计算机应用与软件, 2017, 34(11): 1-5 https://www.cnki.com.cn/Article/CJFDTOTAL-JYRJ201711001.htm Wang Fei, Pang Yue, Zhou Xiangdong, et al. A Method of Track Index for Similarity Search[J]. Computer Applications and Software, 2017, 34 (11): 1-5 https://www.cnki.com.cn/Article/CJFDTOTAL-JYRJ201711001.htm
[17]	Van L H, Takasu A. An Efficient Distributed Index for Geospatial Databases[M]// Database and Expert Systems Applications. Cham: Springer, 2015
[18]	Lu N, Cheng C Q, Jin A, et al. An Index and Retrieval Method of Spatial Data Based on GeoSOT Global Discrete Grid System[C]//IEEE International Geoscience and Remote Sensing Symposium, Melbourne, Australia, 2013
[19]	宋树华, 程承旗, 濮国梁, 等. 全球遥感数据剖分组织的GeoSOT网格应用[J]. 测绘学报, 2014, 43 (8): 869-876 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201408016.htm Song Shuhua, Cheng Chengqi, Pu Guoliang, et al. Global Remote Sensing Data Subdivision Organization Based on GeoSOT[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(8): 869-876 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201408016.htm

[1]	XIAO Tianyuan, LIU Pengcheng, AI Tinghua, LI Jingzhong. A Fractal Description and Multi-scale Expression Method of Fourier Information Metrics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 119-125. DOI: 10.13203/j.whugis20180336
[2]	DIAN Yuanyong, YANG Guang, FANG Shenghui. Combining Fourier Spectrum Texture and Spectral Information for Land Cover Classification with High Resolution Remote Sensing Images[J]. Geomatics and Information Science of Wuhan University, 2017, 42(3): 362-368. DOI: 10.13203/j.whugis20140952
[3]	LIU Li, LI Jinling. Determination and Analysis of Station Parameters ofthe Chinese VLBI Network[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3): 262-266. DOI: 10.13203/j.whugis20120005
[4]	ZHANG Zhibin, WANG Guangli, LIU Xiang, TANG Zhenghong. Analysis of EOP Determination via Chinese VLBI Network[J]. Geomatics and Information Science of Wuhan University, 2013, 38(8): 911-915.
[5]	WEI Erhu, ZHANG Qi. On Length of Day with 1985-2010 VLBI Observations[J]. Geomatics and Information Science of Wuhan University, 2012, 37(9): 1020-1023.
[6]	LIN Hui, LIANG Liang, DU Peijun, SUN Huasheng. Image Registration Based on Fourier-Mellin Transform[J]. Geomatics and Information Science of Wuhan University, 2012, 37(6): 649-652.
[7]	WEI Erhu, LI Xuechuan, YI Hui, LIU Jingnan. On EOP Parameters Based on 2008 VLBI Observation Data[J]. Geomatics and Information Science of Wuhan University, 2010, 35(8): 988-990.
[8]	WEI Erhu, LIU Jingnan, PAN Peijing. On Data Processing with Last Three Years of VLBI Observation[J]. Geomatics and Information Science of Wuhan University, 2008, 33(12): 1275-1278.
[9]	LI Yingbing, XU Shaoquan, ZHANG Yongjun, ZHANG Xiaohong. The Application of Spectrum Analysis in GPS Auto-monitoring System[J]. Geomatics and Information Science of Wuhan University, 2001, 26(4): 343-348.
[10]	Zhang Genshou, Zhu Guorui. Analysis and Study of the Areal Shape on Map[J]. Geomatics and Information Science of Wuhan University, 1994, 19(1): 29-36.

Cited By

Cited by

Periodical cited type(7)

1.	牟希农. 基于小波域马尔可夫随机场的医学影像图像提取实现研究. 贵州大学学报(自然科学版). 2020(01): 74-77 .
2.	陈志坤，江俊君，姜鑫维，白露，蔡之华. 一种基于改进双边滤波的鲁棒高光谱遥感图像特征提取方法. 武汉大学学报(信息科学版). 2020(04): 504-510 .
3.	郭利强，孟庆超. 基于多标签共享子空间学习和内核脊回归的空谱分类算法. 光子学报. 2020(05): 121-133 .
4.	李玉，甄畅，石雪，赵泉华. 基于熵加权K-means全局信息聚类的高光谱图像分类. 中国图象图形学报. 2019(04): 630-638 .
5.	曲海成，郭月，王媛媛. 基于优势集聚类和马尔科夫随机场的高光谱图像分类算法. 国土资源遥感. 2019(02): 24-31 .
6.	职露，余旭初，邹滨，刘冰. 多层级二值模式的高光谱影像空-谱分类. 武汉大学学报(信息科学版). 2019(11): 1659-1666 .
7.	韦春桃，赵平，肖博林，白风，李小勇，杨晚芸. 结合双树复小波纹理特征和MRF模型的遥感图像分割. 测绘通报. 2019(10): 40-45 .

Other cited types(8)

Get Citation

PDF

XML

Article views (1715) PDF downloads (135) Cited by(15)

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

Abstract

References

Related Articles

Cited by

Periodical cited type(7)

Other cited types(8)

Catalog

Related

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

Abstract

References

Related Articles

Cited by

Periodical cited type(7)

Other cited types(8)

Catalog

Related

Export File

Citation

Format

Content