基于网格索引的时空轨迹伴随模式挖掘算法

计算机科学 ›› 2016, Vol. 43 ›› Issue (1): 107-110.doi: 10.11896/j.issn.1002-137X.2016.01.025

• 第五届全国智能信息处理学术会议 • 上一篇下一篇

基于网格索引的时空轨迹伴随模式挖掘算法

杨阳,吉根林,鲍培明

南京师范大学计算机科学与技术学院南京210023,南京师范大学计算机科学与技术学院南京210023,南京师范大学计算机科学与技术学院南京210023

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受国家自然科学基金项目(41471371)资助

Algorithm for Mining Adjoint Pattern of Spatial-Temporal Trajectory Based on Grid Index

YANG Yang, JI Gen-lin and BAO Pei-ming

Online:2018-12-01 Published:2018-12-01

摘要/Abstract

摘要： 时空轨迹伴随模式是数据挖掘领域的一项重要研究内容。CMC(Coherent Moving Cluster)算法是一种经典的时空轨迹伴随模式挖掘算法,该算法引入了DBSCAN算法以挖掘出任意形状的簇。但是,DBSCAN聚类算法极耗时,导致CMC算法的时间效率较低。因此提出了一种基于网格索引的时空轨迹伴随模式挖掘算法MAP-G(Mining Adjoint Pattern of spatial-temporal trajectory based on the Grid index)。实验表明,MAP-G算法不仅比CMC算法具有更高的时间效率,而且能够过滤掉部分不正确的结果,因此结果也更加准确。

关键词: 伴随模式,时空轨迹挖掘,网格索引

Abstract: In the field of data mining,adjoint pattern of spatial-temporal trajectory is an important research direction.CMC(Coherent Moving Cluster) algorithm is a classical algorithm for mining adjoint pattern,and it is applied to mine clusters of arbitrary shape.However,it reduces the efficiency of the algorithm.We presented an algorithm for mining adjoint pattern of spatial-temporal trajectory called MAP-G(Mining Adjoint Pattern of spatial-temporal trajectory based on the Grid index).The experimental results demonstrate that the proposed algorithm is more efficient compared to the CMC algorithm,and the accuracy is higher as our algorithm can filter some wrong results.

Key words: Adjoint pattern,Mining of spatial-temporal trajectory,Grid index

杨阳,吉根林,鲍培明. 基于网格索引的时空轨迹伴随模式挖掘算法[J]. 计算机科学, 2016, 43(1): 107-110. https://doi.org/10.11896/j.issn.1002-137X.2016.01.025

YANG Yang, JI Gen-lin and BAO Pei-ming. Algorithm for Mining Adjoint Pattern of Spatial-Temporal Trajectory Based on Grid Index[J]. Computer Science, 2016, 43(1): 107-110. https://doi.org/10.11896/j.issn.1002-137X.2016.01.025

参考文献

[1] Benkert M,Gudmundsson J,Hübner F,et al.Reporting flock patterns[J].Computational Geometry,2008,41(3):111-125
[2] Jeung H,Shen H T,Zhou X.Convoy queries in spatio-temporal databases[C]∥24th International Conference on Data Enginee-ring(ICDE).IEEE,2008:1457-1459
[3] Jeung H,Yiu M L,Zhou X,et al.Discovery of convoys in trajectory databases[J].Proceedings of the VLDB Endowment,2008,1(1):1068-1080
[4] Giannotti F,Nanni M,Pinelli F,et al.Trajectory pattern mining[C]∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2007:330-339
[5] Li Z,Ding B,Han J,et al.Swarm:Mining relaxed temporal moving object clusters[J].Proceedings of the VLDB Endowment,2010,3(1/2):723-734
[6] Laube P,Imfeld S.Analyzing relative motion within groups oftrackable moving point objects[M]∥Geographic Information Science.Springer Berlin Heidelberg.2002:132-144
[7] Kalnis P,Mamoulis N,Bakiras S.On discovering moving clus-ters in spatio-temporal data[M]∥Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg.2005:364-381
[8] Jeung H,Yiu M L,Zhou X,et al.Discovery of convoys in trajectory databases[J].Proceedings of the VLDB Endowment,2008,1(1):1068-1080
[9] Tang L A,Zheng Y,Yuan J,et al.On discovery of travelingcompanions from streaming trajectories[C]∥28th International Conference on Data Engineering (ICDE).IEEE,2012:186-197
[10] Tang L A,Zheng Y,Yuan J,et al.A framework of travelingcompanion discovery on trajectory data streams[J].ACM Transactions on Intelligent Systems and Technology (TIST),2013,5(1):992-999
[11] Laube P,van Kreveld M,Imfeld S.Finding REMO—detecting relative motion patterns in geospatial lifelines[M]∥Developments in Spatial Data Handling.Springer Berlin Heidelberg.2005:201-215
[12] Laube P,Imfeld S,Weibel R.Discovering relative motion patterns in groups of moving point objects[J].International Journal of Geographical Information Science,2005,19(6):639-668

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed