Volume 18 Issue 3
. 
Turn off MathJax
Article Contents
Article Navigation >  Journal of Traffic and Transportation Engineering  > 2018  >  18(3): 218-227
GAO Miao, SHI Guo-you, LI Wei-feng. Online compression algorithm of AIS trajectory data based on improved sliding window[J]. Journal of Traffic and Transportation Engineering, 2018, 18(3): 218-227. doi: 10.19818/j.cnki.1671-1637.2018.03.022
Citation: GAO Miao, SHI Guo-you, LI Wei-feng. Online compression algorithm of AIS trajectory data based on improved sliding window[J]. Journal of Traffic and Transportation Engineering, 2018, 18(3): 218-227. doi: 10.19818/j.cnki.1671-1637.2018.03.022
shu

Online compression algorithm of AIS trajectory data based on improved sliding window

doi: 10.19818/j.cnki.1671-1637.2018.03.022
  • 1.

    Navigation College, Dalian Maritime University, Dalian 116026, Liaoning, China

  • 2.

    Key Laboratory of Navigation Safety Guarantee of Liaoning Province, Dalian Maritime University, Dalian 116026, Liaoning, China

More Information
    Abstract
  • The time series characteristics of ship AIS data and ship maneuvering characteristics were analyzed. An improved sliding window online compression algorithm was proposed. The AIS trajectory data from 277 ships with a total of 1 026 408 coordinate points were calculated, and the appropriate compression thresholds were determined. The sensitivities of distance and angle thresholds to the compression rate of the algorithm were analyzed. According to the step points of the compression rate image, three distance thresholds of high, middle, and low levels, and one angle threshold were recommended. The compression rate and efficiency of the DouglasPeucker algorithm and improved sliding window algorithm were compared. Experimental result shows that with the improvement of the compression rate, the remaining points after compression and the useful information retained by the data become less. The compression rate is positively proportional to the distance threshold and angle threshold. The dimensionless compression distance thresholds of high, middle, and low levels are 43%, 38% and 33% of ship length, respectively. When the distance threshold is 130 mand the angle threshold is more than 9°, the compression rate becomes stable, so the recommend angle threshold is 9°, which is similar to 8°that is the pressure difference angle in Design Code of General Layout for Sea Ports (JTS 165—2013). With an increase in the distance threshold, the compression rates of the Douglas-Peucker and improved sliding window algorithms tend to be similar. When the distance threshold is 120 m, the compression rate of the Douglas-Peucker algorithm is only 1.74% higher than that of the improved sliding window algorithm. In the case of five distance thresholds, the average operating time of the Douglas-Peucker algorithm is 5.39 times that of the improved sliding window algorithm. With the increase of data volume, the compression efficiency difference between the two algorithms is more obvious. The improved sliding window algorithm can reduce the risk of data compression, simultaneously showing a substantial improvement in the efficiency of data compression, and the data can keep compression states under the continuously updated condition. Compared to the ordinary compression mode, the improved sliding window algorithm occupies less system resources, has higher processing efficiency, and can be applied to ship trajectory data processing, ECDIS display, and extraction of key behavioural features of ships.

     

    • FullText(HTML)
  • loading
    • References(28)
  • [1]
    魏照坤, 周康, 魏明, 等. 基于AIS数据的船舶运动模式识别与应用[J]. 上海海事大学学报, 2016, 37 (2): 17-22, 71. https://www.cnki.com.cn/Article/CJFDTOTAL-SHHY201602005.htm

    WEI Zhao-kun, ZHOU Kang, WEI Ming, et al. Ship motion pattern recognition and application based on AIS data[J]. Journal of Shanghai Maritime University, 2016, 37 (2): 17-22, 71. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SHHY201602005.htm
    [2]
    任亚磊. 基于AIS数据的船舶会遇特征研究[D]. 武汉: 武汉理工大学, 2013.

    REN Ya-lei. Study on ship encounters using AIS data[D]. Wuhan: Wuhan University of Technology, 2013. (in Chinese).
    [3]
    江俊文, 王晓玲. 轨迹数据压缩综述[J]. 华东师范大学学报: 自然科学版, 2015 (5): 61-76. doi: 10.3969/j.issn.1000-5641.2015.05.005

    JIANG Jun-wen, WANG Xiao-ling. Review on trajectory data compression[J]. Journal of East China Normal University: Natural Science, 2015 (5): 61-76. (in Chinese). doi: 10.3969/j.issn.1000-5641.2015.05.005
    [4]
    张树凯, 刘正江, 张显库, 等. 基于Douglas-Peucker算法的船舶AIS航迹数据压缩[J]. 哈尔滨工程大学学报, 2015, 36 (5): 595-599. https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201505002.htm

    ZHANG Shu-kai, LIU Zheng-jiang, ZHANG Xian-ku, et al. A method for AIS track data compression based on DouglasPeucker algorithm[J]. Journal of Harbin Engineering University, 2015, 36 (5): 595-599. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201505002.htm
    [5]
    徐凯, 邱家瑜, 李燕. 一种加入时间维的船舶轨迹高效离线压缩算法研究[J]. 计算机科学, 2017, 44 (11A): 498-502. doi: 10.11896/j.issn.1002-137X.2017.11A.106

    XU Kai, QIU Jia-yu, LI Yan. Offline efficient compression algorithm for AIS data retains time elapsing dimension[J]. Computer Science, 2017, 44 (11A): 498-502. (in Chinese). doi: 10.11896/j.issn.1002-137X.2017.11A.106
    [6]
    MERATNIA N, DE BY R A. Spatiotemporal compression techniques for moving point objects[J]. 2004, 2992: 765-782.
    [7]
    KELLARIS G, PELEKIS N, THEODORIDIS Y. Trajectory Compression under Network Constraints[J]. Lecture Notes in Computer Science, 2009, 5644: 392-398.
    [8]
    LU Cheng-jiao, CHEN Feng, XU Yong-zhi, et al. A trajectory compression algorithm based on non-uniform quantization[C]∥IEEE. 12th International Conference on Fuzzy Systems and Knowledge Discovery. New York: IEEE, 2015: 2469-2474.
    [9]
    DUTTA S, BHATTACHERJEE S, NARANG A. Towards"intelligent compression"in streams: a biased reservoir sampling based Bloom filter approach[C]∥ACM. 15th International Conference on Extending Database Technology, New York: ACM, 2012: 425-426.
    [10]
    张达夫, 张昕明. 基于时空特性的GPS轨迹数据压缩算法[J]. 交通信息与安全, 2013, 31 (3): 6-9. doi: 10.3963/j.issn.1674-4861.2013.03.002

    ZHANG Da-fu, ZHANG Xin-ming. A spatiotemporal compression algorithm for GPS trajectory data[J]. Journal of Transport Information and Safety, 2013, 31 (3): 6-9. (in Chinese). doi: 10.3963/j.issn.1674-4861.2013.03.002
    [11]
    JI Y, LIU H, LIU X, et al. A comparison of road-networkconstrained trajectory compression methods[C]∥IEEE. 22nd IEEE International Conference on Parallel and Distributed Systems. New York: IEEE, 2016: 256-263.
    [12]
    HAN Yun-heng, SUN Wei-wei, ZHENG Bai-hua. Compress: a comprehensive framework of trajectory compression in road networks[J]. ACM Transactions on Database Systems, 2017, 42 (2): 1-49.
    [13]
    朱猛, 孙剑. 基于MBR的GPS轨迹数据压缩算法[J]. 信阳农林学院学报, 2016, 26 (1): 117-120, 123. https://www.cnki.com.cn/Article/CJFDTOTAL-XYNG201601037.htm

    ZHU Meng, SUN Jian. GPS trajectory data compression algorithm based on MBR[J]. Journal of Xinyang College of Agriculture and Forestry, 2016, 26 (1): 117-120, 123. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XYNG201601037.htm
    [14]
    吴家皋, 夏轩, 刘林峰. 基于MapReduce的轨迹压缩并行化方法[J]. 计算机应用, 2017, 37 (5): 1282-1286, 1330. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201705011.htm

    WU Jia-gao, XIA Xuan, LIU Lin-feng. Parallel trajectory compression method based on MapReduce[J]. Journal of Computer Application, 2017, 37 (5): 1282-1286, 1330. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201705011.htm
    [15]
    MUCKELL J, PATIL V, PING Fan. SQUISH: an online approach for GPS trajectory compression[C]∥ACM. 2nd International Conference on Computing for Geospatial Research and Applications. New York: ACM, 2011: 13-20.
    [16]
    李浩, 黄艳, 马岩蔚. 基于三次多项式曲线的轨迹平滑压缩算法[J]. 组合机床与自动化加工技术, 2016 (6): 12-15. https://www.cnki.com.cn/Article/CJFDTOTAL-ZHJC201606004.htm

    LI Hao, HUANG Yan, MA Yan-wei. The smooth compression algorithm based on cubic polynomial curve[J]. Modular Machine Tooland Automatic Manufacturing Technique, 2016 (6): 12-15. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZHJC201606004.htm
    [17]
    樊庆富, 张磊, 刘磊军, 等. 基于偏移量计算的在线GPS轨迹数据压缩[J]. 计算机工程与应用, 2017, 53 (8): 254-259. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201708046.htm

    FAN Qing-fu, ZHANG Lei, LIU Lei-jun, et al. Online GPS trajectory data compression based on offset calculation[J]. Computer Engineering and Applications, 2017, 53 (8): 254-259. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201708046.htm
    [18]
    HERSHKOVITS Y, ZIV J. On sliding window universal data compression with limited memory[J]. IEEE Transactions on Information Theory, 1998, 44 (1): 66-78. doi: 10.1109/18.650988
    [19]
    CHEN Ye-hong, PARK P S, GAO Qian. An enhanced modelbased tracking algorithm with dynamic adjustment of learning parameters according to online performance evaluation[J]. Indian Journal of Science Technology, 2015, 8 (26): 1-6.
    [20]
    丁振国. 船舶AIS数据云存储系统研究[J]. 浙江交通职业技术学院学报, 2016, 17 (1): 37-42. https://www.cnki.com.cn/Article/CJFDTOTAL-ZJZJ201601009.htm

    DING Zhen-guo. A Study on the cloud storage system of ship's AIS data[J]. Journal of Zhejiang Institute of Communications, 2016, 17 (1): 37-42. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZJZJ201601009.htm
    [21]
    吴家皋, 刘敏, 韦光, 等. 一种改进的滑动窗口轨迹数据压缩算法[J]. 计算机技术与发展, 2015, 25 (12): 47-51. https://www.cnki.com.cn/Article/CJFDTOTAL-WJFZ201512011.htm

    WU Jia-gao, LIU Min, WEI Guang, et al. An improved trajectory data compression algorithm ofsliding window[J]. Computer Technology and Development, 2015, 25 (12): 47-51. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-WJFZ201512011.htm
    [22]
    赵友桥, 王坚, 路松峰, 等. 一种后缀数组与滑动窗口结合的压缩算法[J]. 计算机工程与应用, 2012, 48 (15): 59-62. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201215014.htm

    ZHAO You-qiao, WANG Jian, LU Song-feng, et al. A sliding window compression algorithm based on suffix array[J]. Computer Engineering and Applications, 2012, 48 (15): 59-62. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201215014.htm
    [23]
    KEOGH E, CHU S, HART D, et al. An online algorithm for segmenting time series[C]∥IEEE. 2001IEEE International Conference on Data Mining. New York: IEEE, 2001: 289-296.
    [24]
    INENAGA S, SHINOHARA A, TAKEDA M, et al. Compact directed acyclic word graphs for asliding window[J]. Lecture Notes in Computer Science, 2002, 2476: 310-324.
    [25]
    王栩, 李建中, 王伟平. 基于滑动窗口的数据流压缩技术及连续查询处理方法[J]. 计算机研究与发展, 2004, 41 (10): 1639-1644. https://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ200410005.htm

    WANG Xu, LI Jian-zhong, WANG Wei-ping. Processing compressedsliding window continuous queries over data streams[J]. Journal of computer research and development, 2004, 41 (10): 1639-1644. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ200410005.htm
    [26]
    BELYAEV E, FORCHHAMMER S, LIU Kai. An adaptive multialphabet arithmetic coding based on generalized virtual sliding window[J]. IEEE Signal Processing Letters, 2017, 24 (7): 1034-1038.
    [27]
    史国友, 朱公志, 王玉梅, 等. 恒向线主题直接正反解的高精度算法[J]. 大连海事大学学报, 2009, 35 (2): 5-9. https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS200902002.htm

    SHI Guo-you, ZHU Gong-zhi, WANG Yu-mei, et al. High accurate algorithm for forward and inverse solution of rhumb line's problem[J]. Journal of Dalian Maritime University, 2009, 35 (2): 5-9. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS200902002.htm
    [28]
    毕晓君, 樊松. 基于突变理论的图像边缘检测技术[J]. 应用科技, 2008, 35 (6): 1-6. https://www.cnki.com.cn/Article/CJFDTOTAL-YYKJ200806002.htm

    BI Xiao-jun, FAN Song. Edge detection based on catastrophic theory[J]. Applied Science and Technology, 2008, 35 (6): 1-6. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-YYKJ200806002.htm
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML

    Article Metrics

    Article views (880) PDF downloads(894) Cited by()
    Proportional views
    Related

    Copyright《Journal of Traffic and Transportation Engineering》编辑部陕ICP备05001904号-1

    Address ：Editorial Department of Journal of Traffic and Transportation Engineering, Chang 'an University, Middle Section of South Second Ring Road, Xi 'an, Shaanxi（710064） Tel：029-82334388 Email：jygc@chd.edu.cn

    All visit:Today's visit:

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return