轨迹压缩的典型方法评价
|
摘要
轨迹大数据的关键瓶颈之一是轨迹数据海量的数据规模对轨迹的分析、挖掘和应用的限制,因而各类针对轨迹数据的压缩方法是轨迹大数据研究的重点。现有轨迹压缩算法重视对轨迹数据的单一维度时空特征的保持,而缺乏压缩算法对多维度时空特征影响的研究。本文选取MBR面积误差、距离误差、方向误差、速度误差、压缩率和压缩速度等轨迹数据多维度时空特征,分别从轨迹的几何特征、运动特征和压缩效率3个层面对典型轨迹压缩方法进行评价。同时,为了系统观察轨迹压缩算法在不同压缩尺度上对轨迹时空特征的影响规律,本文采用多个尺度压缩结果的评价方法。研究结果表明,在整体效果上那些考虑了轨迹运动特征的压缩算法(如TD_TR算法)对轨迹的总体时空特征保持较好;并且不同的压缩算法对时空特征的影响总体上具有随着尺度变化的一致性,可见压缩尺度是决定压缩效果的核心因素。
One of the key bottlenecks in the big data of trajectories is the massive data size of the trajectory data. Therefore,the compression of trajectory data is the important field of the trajectory big data research. Existing trajectory compression algorithms emphasize the maintenance of the single dimensional space-time feature of the trajectory data,but lack the study of the impact of compression algorithm on the multi-dimensional space-time feature. In this paper,multi-dimensional space-time characteristics of trajectory data such as area error,distance error,direction error,speed error,compression rate and compression speed of MBR are selected for evaluation,and typical trajectory compression methods are evaluated from three levels of geometric features,motion features and compression efficiency of the trajectory. At the same time,in order to systematically observe the change of trajectory time and space characteristics of trajectory compression algorithm on different compression scales,this paper adopts the evaluation method of multiple scale compression results.Comprehensive research results show that the overall effect on considering the trajectory feature compression algorithms such as TD_TR algorithm to track the overall characteristics of time and space to keep the good,and the effect of different compression algorithms on the space-time characteristics of overall consistency with scale change.
One of the key bottlenecks in the big data of trajectories is the massive data size of the trajectory data. Therefore,the compression of trajectory data is the important field of the trajectory big data research. Existing trajectory compression algorithms emphasize the maintenance of the single dimensional space-time feature of the trajectory data,but lack the study of the impact of compression algorithm on the multi-dimensional space-time feature. In this paper,multi-dimensional space-time characteristics of trajectory data such as area error,distance error,direction error,speed error,compression rate and compression speed of MBR are selected for evaluation,and typical trajectory compression methods are evaluated from three levels of geometric features,motion features and compression efficiency of the trajectory. At the same time,in order to systematically observe the change of trajectory time and space characteristics of trajectory compression algorithm on different compression scales,this paper adopts the evaluation method of multiple scale compression results.Comprehensive research results show that the overall effect on considering the trajectory feature compression algorithms such as TD_TR algorithm to track the overall characteristics of time and space to keep the good,and the effect of different compression algorithms on the space-time characteristics of overall consistency with scale change.
引文
[1]ZHENG Y,CAPRA L,WOLFSON O,et al.Urban computing:concepts,methodologies,and applications[J].Acm Transactions on Intelligent Systems and Technology,2014,5(3):1-55.
[2]刘汇慧,阚子涵,吴华意,等.车辆GPS轨迹加油行为建模与时空分布分析[J].测绘通报,2016(9):29-34.
[3]SUN P,XIA S,YUAN G,et al.An overview of moving object trajectory compression algorithms[J].Mathematical Problems in Engineering,2016(3):1-13.
[4]高强,张凤荔,王瑞锦,等.轨迹大数据:数据处理关键技术研究综述[J].软件学报,2017,28(4):959-992.
[5]LONG C,WONG C W,JAGADISH H V.Trajectory simplification:on minimizing the direction-based error[M].[S.l.]:VLDB Endowment,2014:49-60.
[6]杨敏,陈媛媛,金澄,等.保持移动速度特征的轨迹线化简方法[J].测绘学报,2017,46(12):2016-2023.
[7]GOTSMAN R,KANZA Y.A Dilution-matching-encoding compaction of trajectories over road networks[J].Geoinformatica,2015,19(2):331-364.
[8]CAO X,CONG G,JENSEN C S.Mining significant semantic locations from GPS data[J].Proceedings of the Vldb Endowment,2010,3(1):1009-1020.
[9]MUCKELL J,HWANG J H,PATIL V,et al.SQUISH:an online approach for GPS trajectory compression[C]∥International Conference on Computing for Geospatial Research and Applications.[S.l.]:ACM,2011.
[10]MERATNIA N,BY R A D.Spatiotemporal compression techniques for moving point objects[C]∥International Conference on Advances in Databased Technology-edbt.[S.l.]:Springer,2004.
[11]吴家皋,钱科宇,刘敏,等.基于综合时空特性的混合式轨迹压缩算法[J].计算机应用,2015,35(5):1209-1212.
[12]HIMOTO K,TSUCHIHASHI T,TANAKA Y,et al.Modeling the trajectory of window flames with regard to flow attachment to the adjacent wall[J].Fire Safety Journal,2009,44(2):250-258.
[13]MUCKELL J,HWANG J H,LAWSON C T,et al.Algorithms for compressing GPS trajectory data:an empirical evaluation[C]∥Sigspatial International Conference on Adrances in Geographic Information Systems.[S.l.]:ACM,2010.
[14]江俊文.轨迹数据的压缩技术和系统实现[D].上海:华东师范大学,2016.
[15]樊庆富,张磊,刘磊军,等.基于偏移量计算的在线GPS轨迹数据压缩[J].计算机工程与应用,2017,53(8):254-259.
[2]刘汇慧,阚子涵,吴华意,等.车辆GPS轨迹加油行为建模与时空分布分析[J].测绘通报,2016(9):29-34.
[3]SUN P,XIA S,YUAN G,et al.An overview of moving object trajectory compression algorithms[J].Mathematical Problems in Engineering,2016(3):1-13.
[4]高强,张凤荔,王瑞锦,等.轨迹大数据:数据处理关键技术研究综述[J].软件学报,2017,28(4):959-992.
[5]LONG C,WONG C W,JAGADISH H V.Trajectory simplification:on minimizing the direction-based error[M].[S.l.]:VLDB Endowment,2014:49-60.
[6]杨敏,陈媛媛,金澄,等.保持移动速度特征的轨迹线化简方法[J].测绘学报,2017,46(12):2016-2023.
[7]GOTSMAN R,KANZA Y.A Dilution-matching-encoding compaction of trajectories over road networks[J].Geoinformatica,2015,19(2):331-364.
[8]CAO X,CONG G,JENSEN C S.Mining significant semantic locations from GPS data[J].Proceedings of the Vldb Endowment,2010,3(1):1009-1020.
[9]MUCKELL J,HWANG J H,PATIL V,et al.SQUISH:an online approach for GPS trajectory compression[C]∥International Conference on Computing for Geospatial Research and Applications.[S.l.]:ACM,2011.
[10]MERATNIA N,BY R A D.Spatiotemporal compression techniques for moving point objects[C]∥International Conference on Advances in Databased Technology-edbt.[S.l.]:Springer,2004.
[11]吴家皋,钱科宇,刘敏,等.基于综合时空特性的混合式轨迹压缩算法[J].计算机应用,2015,35(5):1209-1212.
[12]HIMOTO K,TSUCHIHASHI T,TANAKA Y,et al.Modeling the trajectory of window flames with regard to flow attachment to the adjacent wall[J].Fire Safety Journal,2009,44(2):250-258.
[13]MUCKELL J,HWANG J H,LAWSON C T,et al.Algorithms for compressing GPS trajectory data:an empirical evaluation[C]∥Sigspatial International Conference on Adrances in Geographic Information Systems.[S.l.]:ACM,2010.
[14]江俊文.轨迹数据的压缩技术和系统实现[D].上海:华东师范大学,2016.
[15]樊庆富,张磊,刘磊军,等.基于偏移量计算的在线GPS轨迹数据压缩[J].计算机工程与应用,2017,53(8):254-259.