Trajectory data generalization based on local multi-hierarchy grid

doi:10.3724/SP.J.1087.2013.01604

Journal of Computer Applications ›› 2013, Vol. 33 ›› Issue (06): 1604-1607.DOI: 10.3724/SP.J.1087.2013.01604

• Artificial intelligence • Previous Articles Next Articles

Trajectory data generalization based on local multi-hierarchy grid

YANG Guang,ZHANG Lei,LI Fan

School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221116, China

Received:2012-12-25 Revised:2013-02-18 Online:2013-06-05 Published:2013-06-01
Contact: YANG Guang
Supported by:
;the youth foundation of China University of Mining and Technology;the China University of Mining and Technology Special Funds for the Graduate Practice and Research Innovation

局部多层网格划分下的轨迹数据概化方法

杨光,张磊,李帆

中国矿业大学计算机科学与技术学院，江苏徐州 221116

通讯作者: 杨光
作者简介:杨光(1988-)，女，山东济宁人，硕士研究生，主要研究方向：移动对象轨迹数据挖掘；张磊(1977-)，男，江苏沛县人，副教授，博士，主要研究方向：移动对象轨迹数据挖掘；李帆(1986-)，男，四川南充人，硕士，主要研究方向：移动对象轨迹数据挖掘。
基金资助:
江苏省博士后基金资助项目(0802023C);中国矿业大学青年科技基金资助项目(2008A040);中国矿业大学研究生实践与科研创新课题专项基金资助项目(GSF122111);教育部博士点基金资助项目(20110095110010)

Abstract

Abstract: For current trajectory data generalization methods, the scope of the generalized regions cannot be controlled effectively, and the parameters of the grids can hardly be selected logically. This paper proposed the method of Local Multi-hierarchy Grid (LMG), so that the region with dense trajectory points would be divided iteratively. And then a method for trajectory data generalization named TRAGenLMG was proposed, which was based on LMG, and time-constraint was used to merge some adjoining grids, and finally the generalized trajectory was got. The experiments with real open dataset show that the generalized trajectories generated by TRAGenLMG can well maintain the temporal feature of the trajectory data and can be efficiently applied into further data analysis.

Key words: trajectory generalization, Local Multi-hierarchy Grid (LMG), time-constraint, trajectory data

摘要： 针对轨迹数据概化中空间划分的区域范围不能有效控制以及覆盖网格尺度难以合理选择的问题，提出局部多层网格划分方法，对样本密集的区域进行迭代划分。在此基础上提出一种轨迹数据概化方法，在局部多层网格划分的基础上，考虑时间约束合并轨迹连续往复通过的邻接区域，生成概化轨迹。真实数据的实验表明该算法得到的概化轨迹较同类算法保持了更多轨迹特性，更加适合后续数据挖掘，如聚类处理。

关键词: 轨迹概化, 局部多层网格, 时间约束, 轨迹数据

CLC Number:

TP311

YANG Guang ZHANG Lei LI Fan. Trajectory data generalization based on local multi-hierarchy grid[J]. Journal of Computer Applications, 2013, 33(06): 1604-1607.

杨光张磊李帆. 局部多层网格划分下的轨迹数据概化方法[J]. 计算机应用, 2013, 33(06): 1604-1607.

References

[1] ANDRIENKO N, ANDRIENKO G. Spatial generalization and aggregation of massive movement data［J］. Visualization and Computer Graphics, 2011, 17(2): 205-219.

[2] ZHANG L, YANG G, WANG Z C. Trajectory clustering based on spatial generalization［J］. Journal of Information & Computational Science, 2012, 9(2): 315-32.

[3] GIANNOTTI F, NANNI M, PEDRESCHI D, et al. Trajectory pattern mining［C］// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 330-339.

[4] 唐良, 唐常杰, 姜页希,等. TRAODGrid：基于Grid 空间划分的高效离群轨迹检测方法［J］. 计算机研究与发展,2008, 45(10):185-190.

[5] SHERKAT R, LI J, MAMOULIS N. Efficient time stamped event sequence anonymization［EB/OL］. ［2012-08-20］. http://www.cs.hku.hk/research/techreps/document/TR-2011-02.pdf.

[6] ASSAM R, SEIDL T. Preserving privacy of moving objects via temporal clustering of spatio-temporal data streams［C］// Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS. New York: ACM, 2011:9-16.

[7] Unisys Weather ［DB/OL］. ［2012-05-23］. http://weather.unisys.com/hurricane/atlantic/.

[8] STEFANAKIS E. Trajectory generalization under space constraints［EB/OL］. ［2012-08-20］. http://www.giscience.org/proceedings/abstracts/giscience2012_paper_74.pdf.

[9] MASCIARI E. A framework for trajectory clustering［C］// Proceedings of the 3rd International Conference on GeoSensor Networks. Berlin:Springer-Verlag, 2009: 102-111.

[10] 孙吉贵,刘杰,赵连宇.聚类算法研究［J］.软件学报， 2008,19(1):48-61.

[11] 袁冠,夏士雄,张磊,等. 基于结构相似度的轨迹聚类算法［J］. 通信学报， 2011, 32(9):103-110.

[12] MARTINEZ-BEA S. Trajectory anonymization from a time series perspective［C］// 2011 IEEE International Conference on Fuzzy Systems.Piscataway:IEEE, 2011: 401-408.

[13] ANDRIENKO G, ANDRIENKO N, GIANNOTTI F, et al. Movement data anonymity through generalization［J］. Journal of Transactions on Data Privacy, 2010, 3(2): 91-121.

[1]	Wenxuan LI, Hao WU, Changsong LI. Survey of semantics-based location privacy protection [J]. Journal of Computer Applications, 2023, 43(11): 3472-3483.
[2]	Haiyang LIU, Linghang MENG, Zhonghang LIN, Yuantao GU. Route discovery method based on trajectory point clustering [J]. Journal of Computer Applications, 2022, 42(3): 890-894.
[3]	KANG Jun, HUANG Shan, DUAN Zongtao, LI Yixiu. Review of spatio-temporal trajectory sequence pattern mining methods [J]. Journal of Computer Applications, 2021, 41(8): 2379-2385.
[4]	Fumin ZOU, Sijie LUO, Zhihui CHEN, Lyuchao LIAO. Time-space distribution identification method of taxi shift based on trajectory data [J]. Journal of Computer Applications, 2021, 41(11): 3376-3384.
[5]	SUN Heli, ZHANG Youyou, YANG Zhou, HE Liang, JIA Xiaolin. Urban reachable region search based on time segment tree [J]. Journal of Computer Applications, 2020, 40(10): 2936-2941.
[6]	XU Yao, LI Zhuoran, MENG Jinlong, ZHAO Lipo, WEN Jianxin, WANG Guiling. Extraction method of marine lane boundary from exploiting trajectory big data [J]. Journal of Computer Applications, 2019, 39(1): 105-112.
[7]	ZHENG Zhentao, ZHAO Zhuofeng, WANG Guiling, XU Yao. Ship trajectory extraction method for port parking area identification [J]. Journal of Computer Applications, 2019, 39(1): 113-117.
[8]	CHEN Hui, JIANG Guifeng, JIANG Guiyuan, WU Jigang. Map matching algorithm based on massive bus trajectory data mining [J]. Journal of Computer Applications, 2018, 38(7): 1923-1928.
[9]	ZHANG Haitao, ZHOU Huan, ZHANG Guonan. Mining method of trajectory interval pattern based on spatial proximity searching [J]. Journal of Computer Applications, 2018, 38(11): 3326-3331.
[10]	HUO Zheng, CUI Honglei, HE Ping. k-CS algorithm: trajectory data privacy-preserving based on semantic location protection [J]. Journal of Computer Applications, 2018, 38(1): 182-187.
[11]	HUO Zheng, WANG Weihong, CAO Yuhui. PTDC:privacy-aware trajectory data collection technology under road network constraint [J]. Journal of Computer Applications, 2017, 37(9): 2567-2571.
[12]	SHI Lukui, ZHANG Yanru, ZHANG Xin. Trajectory data clustering algorithm based on spatio-temporal pattern [J]. Journal of Computer Applications, 2017, 37(3): 854-859.
[13]	DENG Jingsong, LUO Yonglong, YU Qingying, CHEN Fulong. Privacy-preserving trajectory data publishing based on non-sensitive information analysis [J]. Journal of Computer Applications, 2017, 37(2): 488-493.
[14]	WANG Baoquan, JIANG Tonghai, ZHOU Xi, MA Bo, ZHAO Fan. Mining of accompanying vehicle group from trajectory data based on analogous automatic number plate recognition [J]. Journal of Computer Applications, 2017, 37(11): 3064-3068.
[15]	LYU Shaoqian, MENG Fanrong, YUAN Guan. Trajectory structure-based moving object hotspots discovery [J]. Journal of Computer Applications, 2017, 37(1): 54-59.

Trajectory data generalization based on local multi-hierarchy grid

局部多层网格划分下的轨迹数据概化方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics