|本期目录/Table of Contents|

[1]杨 宇,吉根林*,赵 斌,等. 一种新的基于时空轨迹的汇合模式挖掘算法[J].南京大学学报(自然科学),2018,54(1):97.[doi:10.13232/j.cnki.jnju.2018.01.011]
 Yang Yu,Ji Genlin*,Zhao Bin,et al. A new algorithm for mining gathering pattern from spatio-temporal trajectories[J].Journal of Nanjing University(Natural Sciences),2018,54(1):97.[doi:10.13232/j.cnki.jnju.2018.01.011]
点击复制

 一种新的基于时空轨迹的汇合模式挖掘算法()
     

《南京大学学报(自然科学)》[ISSN:0469-5097/CN:32-1169/N]

卷:
54
期数:
2018年第1期
页码:
97
栏目:
出版日期:
2018-02-01

文章信息/Info

Title:
 A new algorithm for mining gathering pattern from spatio-temporal trajectories
作者:
 杨 宇1吉根林1*赵 斌1黄潇婷2
1.南京师范大学计算机科学与技术学院,南京,210023;
2.山东大学旅游管理系,济南,250100
Author(s):
 Yang Yu1Ji Genlin1*Zhao Bin1Huang Xiaoting2
1.School of Computer Science and Technology,Nanjing Normal University,Nanjing,210023,China;
2.Department of Tourism Management,Shandong University,Ji’nan,250100
关键词:
 轨迹数据挖掘聚集模式聚集运动汇合模式
Keywords:
 trajectory data mininggathering patterngathering movementconverging pattern
分类号:
TP181
DOI:
10.13232/j.cnki.jnju.2018.01.011
文献标志码:
A
摘要:
 现有移动对象聚集模式因为模式定义的不足,无法全面地反映移动对象群体聚集运动.提出一种新的移动对象聚集模式,称为汇合模式,该模式从移动对象群体运动形态出发设计,准确反映群体的变化趋势,有效识别群体聚集运动.汇合模式挖掘过程中使用簇包含关系保证群体之间的关联性,识别群体变化趋势.通过相邻时刻的簇集合进行条件为簇包含的连接操作,实现汇合模式的挖掘.利用移动对象簇之间的空间关系对连接操作进行剪枝,提升汇合模式挖掘的效率.针对汇合模式挖掘中移动对象聚类效率较低的问题,使用四叉树改进DBSCAN(Density-Based Spatial Clustering of Applications with Noise)聚类算法,进一步提升了汇合模式挖掘算法的性能.利用真实的GPS轨迹数据进行实验,结果表明汇合模式挖掘方法是有效的.
Abstract:
 Existing gathering patterns cannot reflect the group gathering movement of moving objects groups in a comprehensive way because of the lack of their definitions.This paper puts forward a new gathering pattern which is called converging pattern.This pattern,designed for modelling for moving objects group,can not only accurately reflect the variation trend but also recognize the gathering movement of the groups.In mining process of the converging pattern,cluster inclusion relationship is applied to ensure the association between clusters which represent the moving objects groups and to reflect the variation trend of these groups.The converging patterns are mined by join operation under the condition of cluster inclusion relationship.In order to improve the efficiency of the mining process,join operation is pruned using spatial relationship between clusters.For improving the efficiency of mobile objects clustering in converging patterns mining,we improve algorithm DBSCAN(Density-Based Spatial Clustering of Applications with Noise) by using the quad tree.Finally,experiment results based on the real-life trajectory data of GPS show that the algorithm for mining converging patterns is effective and efficient.

参考文献/References:

 [1] Laube P,Imfeld S.Analyzing relative motion within groups of trackable moving point objects ∥ The 2nd International Conference on Geographic Information Science.Boulder,CO,USA:Springer,2002:132-144.
[2] 吉根林,孙鸿艳,赵 斌.时空轨迹群体运动模式挖掘研究进展.南京航空航天大学学报,2016,48(5):615-624.(Ji G L,Sun H Y,Zhao B.Research progress in group moving patterns mining of spatio-temporal trajectories.Journal of Nanjing University of Aeronautics & Astronautics,2016,48(5):615-624.)
[3] Benkert M,Gudmundsson J,Hübner F,et al.Reporting flock patterns ∥ The 14th Annual European Symposium on Algorithms.Zurich,Switzerland:Springer,2006:660-671.
[4] Vieira M R,Bakalov P,Tsotras V J.On-line discovery of flock patterns in spatio-temporal data ∥ The 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Seattle,WA,USA:ACM,2009:286-295.
[5] Kalnis P,Mamoulis N,Bakiras S.On discovering moving clusters in spatio-temporal data ∥ The 9th International Symposium on Spatial and Temporal Databases.Angra dos Reis,Brazil:Springer,2005:364-381.
[6] Jeung H,Yiu M L,Zhou X F,et al.Discovery of convoys in trajectory databases.Proceedings of the VLDB Endowment,2008,1(1):1068-1080.
[7] Li Z H,Ding B L,Han J W,et al.Swarm:Mining relaxed temporal moving object clusters.Proceedings of the VLDB Endowment,2010,3(1-2):723-734.
[8] Tang L A,Zheng Y,Yuan J,et al.On discovery of traveling companions from streaming trajectories ∥ The 28th International Conference on Data Engineering.Washington D C,USA:IEEE,2012:186-197.
[9] Zheng K,Zheng Y,Yuan N J,et al.On discovery of gathering patterns from trajectories ∥ The 29th International Conference on Data Engineering.Brisbane,Australia:IEEE,2013:242-253.
[10] Zheng K,Zheng Y,Yuan N J,et al.Online discovery of Gathering patterns over trajectories.IEEE Transactions on Knowledge and Data Engineering,2014,26(8):1974-1988.
[11] Guo L M,Huang G Y,Ding Z M.Efficient detection of emergency event from moving object data streams ∥ The 19th International Conference on Database Systems for Advanced Applications.Bali,Indonesia:Springer,2014:422-437.
[12] Jacox E H,Samet H.Spatial join techniques.ACM Transactions on Database Systems,2007,32(1):7.
[13] Bouros P,Mamoulis N,Ge S,et al.Set containment join revisited.Knowledge and Information Systems,2016,49(1):375-402.
[14] Ester M,Kriegel H P,Sander J,et al.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise ∥ The 2nd International Conference on Knowledge Discovery and Data Mining.Portland,OR,USA:AAAI,1996:226-231.
[15] Broder A,Mitzenmacher M.Network applications of bloom filters:A survey.Internet Mathematics,2004,1(4):485-509.
[16] Cudre-Mauroux P,Wu E,Madden S.TrajStore:An adaptive storage system for very large trajectory data sets ∥ The 26th International Conference on Data Engineering.Long Beach,CA,USA:IEEE,2010:109-120.

相似文献/References:

备注/Memo

备注/Memo:
 基金项目:国家自然科学基金(41471371,41301142)
收稿日期:2017-12-08
*通讯联系人,E-mail:glji@njnu.edu.cn
更新日期/Last Update: 2018-01-31