基于划分的自适应轨迹拐点提取压缩算法
作者:
基金项目:

国家自然科学基金(42201500, 41471333); 福建省科技计划引导项目(2021H0036)


Adaptive Trajectory Inflexion Extraction and Compression Algorithm Based on Partition
Author:
  • ZHENG Han-Jie

    ZHENG Han-Jie

    Key Lab of Spatial Data Mining & Information Sharing of Ministry of Education (Fuzhou University), Fuzhou 350108, China;The Academy of Digital China (Fujian), Fuzhou 350003, China;National & Local Joint Engineering Research Center of Satellite Geospatial Information Technology, Fuzhou 350108, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • WU Qun-Yong

    WU Qun-Yong

    Key Lab of Spatial Data Mining & Information Sharing of Ministry of Education (Fuzhou University), Fuzhou 350108, China;The Academy of Digital China (Fujian), Fuzhou 350003, China;National & Local Joint Engineering Research Center of Satellite Geospatial Information Technology, Fuzhou 350108, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • YIN Yan-Zhong

    YIN Yan-Zhong

    Key Lab of Spatial Data Mining & Information Sharing of Ministry of Education (Fuzhou University), Fuzhou 350108, China;The Academy of Digital China (Fujian), Fuzhou 350003, China;National & Local Joint Engineering Research Center of Satellite Geospatial Information Technology, Fuzhou 350108, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • WANG Han-Jing

    WANG Han-Jing

    Key Lab of Spatial Data Mining & Information Sharing of Ministry of Education (Fuzhou University), Fuzhou 350108, China;The Academy of Digital China (Fujian), Fuzhou 350003, China;National & Local Joint Engineering Research Center of Satellite Geospatial Information Technology, Fuzhou 350108, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • ZHANG Chen

    ZHANG Chen

    Key Lab of Spatial Data Mining & Information Sharing of Ministry of Education (Fuzhou University), Fuzhou 350108, China;The Academy of Digital China (Fujian), Fuzhou 350003, China;National & Local Joint Engineering Research Center of Satellite Geospatial Information Technology, Fuzhou 350108, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [27]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    海量的轨迹数据为管理分析和数据挖掘工作带来了巨大的挑战, 轨迹压缩技术成为解决这一问题的一种有效方案. 针对目前多数轨迹压缩算法需要人为干预设定阈值的问题, 融合特征聚类与轨迹划分的思想提出了一种自适应的轨迹拐点提取压缩算法. 算法从轨迹的全局方向特征与局部方向特征出发考虑, 依次进行了轨迹粗划分、子轨迹合并以及轨迹细划分的工作. 实验结果显示, 随着轨迹规模的增大, 与其他算法相比, 该算法基本能够在保持更高压缩率的同时产生更低的方向误差. 提出的算法具有自适应和高精度拐点识别的优势, 在其他轨迹压缩场景之下仍有着较高的参考价值.

    Abstract:

    Massive trajectory data pose challenges to management analysis and data mining, and trajectory compression technology has become an effective solution to this problem. Aiming at the problem that most current trajectory compression algorithms need human intervention to set thresholds, this study proposes an adaptive trajectory inflection point extraction and compression algorithm which combines the idea of feature clustering and trajectory partition. Based on the global and local direction characteristics of the trajectory, the algorithm carries out the rough trajectory division, sub-trajectory merging, and fine trajectory division. The experimental results show that with the increasing trajectory size, the proposed algorithm can produce lower direction error and maintain a higher compression rate than other algorithms. The algorithm features adaptive and high-precision inflection point recognition and still has a high reference value under other trajectory compression scenarios.

    参考文献
    [1] 梁明, 陈文静, 段平, 等. 轨迹压缩的典型方法评价. 测绘通报, 2019, (4): 60-64, 70
    [2] Chen AB, Liu LF. An online trajectory compression based on retrace point detection. Proceedings of the 20th IEEE International Conference on Communication Technology. Nanning: IEEE, 2020. 1478-1482.
    [3] He XR, Kempe D. Stability of influence maximization. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2014. 1256-1265.
    [4] Sun PH, Xia SX, Yuan G, et al. An overview of moving object trajectory compression algorithms. Mathematical Problems in Engineering, 2016, 2016: 6587309
    [5] Chen C, Ding Y, Xie XF, et al. TrajCompressor: An online map-matching-based trajectory compression framework leveraging vehicle heading direction and change. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(5): 2012-2028. [doi: 10.1109/TITS.2019.2910591
    [6] 苏建花, 赵旭俊, 蔡江辉. 采用轨迹压缩和路网划分的车辆异常轨迹检测. 小型微型计算机系统, 2022, 43(7): 1438-1444
    [7] Makris A, da Silva CL, Bogorny V, et al. Evaluating the effect of compressing algorithms for trajectory similarity and classification problems. Geoinformatica, 2021, 25(4): 679-711. [doi: 10.1007/s10707-021-00434-1
    [8] 周燕. 基于Spark的语义轨迹频繁模式提取方法及其应用[硕士学位论文]. 武汉: 湖北工业大学, 2020.
    [9] Tang J, Liu LF, Wu JG. A trajectory partition method based on combined movement features. Wireless Communications and Mobile Computing, 2019, 2019: 7803293
    [10] Douglas DH, Peucker TK. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122. [doi: 10.3138/FM57-6770-U75U-7727
    [11] Meratnia N, de By RA. Spatiotemporal compression techniques for moving point objects. Proceedings of the 9th International Conference on Extending Database Technology. Heraklion: Springer, 2004. 765-782.
    [12] Cheng L, Wong RCW, Jagadish HV. Direction-preserving trajectory simplification. Proceedings of the VLDB Endowment, 2013, 6(10): 949-960. [doi: 10.14778/2536206.2536221
    [13] Cheng L, Wong RCW, Jagadish HV. Trajectory simplification: On minimizing the direction-based error. Proceedings of the VLDB Endowment, 2014, 8(1): 49-60. [doi: 10.14778/2735461.2735466
    [14] 李升宏, 耿生玲, 田立勤, 等. 矢量轨迹有损压缩余弦垂距判别法. 西安邮电大学学报, 2021, 26(6): 72-81
    [15] 邬群勇, 王祥健. 出租车轨迹数据的频繁轨迹识别. 测绘通报, 2021, (11): 70-75
    [16] Yuan G, Xia SX, Zhang L, et al. An efficient trajectory-clustering algorithm based on an index tree. Transactions of the Institute of Measurement and Control, 2012, 34(7): 850-861. [doi: 10.1177/0142331211423284
    [17] 田智慧, 马占宇, 魏海涛. 基于密度核心的出租车载客轨迹聚类算法. 计算机工程, 2021, 47(2): 133-138
    [18] Potamias M, Patroumpas K, Sellis T. Sampling trajectory streams with spatiotemporal criteria. Proceedings of the 18th International Conference on Scientific and Statistical Database Management. Vienna: IEEE, 2006. 275-284.
    [19] Lin CY, Hung CC, Lei PR. A velocity-preserving trajectory simplification approach. Proceedings of the 2016 Conference on Technologies and Applications of Artificial Intelligence. Hsinchu: IEEE, 2016. 58-65.
    [20] 张甜, 杨智应. 基于分段的移动对象轨迹简化算法. 计算机应用研究, 2019, 36(7): 2044-2048
    [21] Rousseeuw PJ. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 1987, 20: 53-65. [doi: 10.1016/0377-0427(87)90125-7
    [22] 杨家轩, 马令琪. 基于信息熵的船舶轨迹自适应分段压缩算法. 上海海事大学学报, 2022, 43(2): 7-13, 73
    [23] Leiva LA, Vidal E. Warped K-means: An algorithm to cluster sequentially-distributed data. Information Sciences, 2013, 237: 196-210. [doi: 10.1016/j.ins.2013.02.042
    [24] 郭炜强, 赵卓峰, 李征宇, 等. REGRASP: 一种反应式GRASP的无监督轨迹分段方法. 西北师范大学学报(自然科学版), 2020, 56(6): 44-52, 62
    [25] Zheng Y, Zhang LZ, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories. Proceedings of the 18th International Conference on World Wide Web. Madrid: ACM Press, 2009. 791-800.
    [26] Zheng Y, Li QN, Chen YK, et al. Understanding mobility based on GPS data. Proceedings of the 10th International Conference on Ubiquitous Computing. Seoul: ACM Press, 2008. 312-321.
    [27] Zheng Y, Xie X, Ma WY. GeoLife: A collaborative social networking service among user, location and trajectory. IEEE Data Engineering Bulletin, 2010, 33(2): 32-39
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

郑汉捷,邬群勇,尹延中,王涵菁,张晨.基于划分的自适应轨迹拐点提取压缩算法.计算机系统应用,2023,32(11):212-221

复制
分享
文章指标
  • 点击次数:581
  • 下载次数: 1607
  • HTML阅读次数: 1101
  • 引用次数: 0
历史
  • 收稿日期:2023-04-13
  • 最后修改日期:2023-05-17
  • 在线发布日期: 2023-09-21
文章二维码
您是第11208045位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号