Volume 18 Issue 3
. 
Turn off MathJax
Article Contents
Article Navigation >  Journal of Traffic and Transportation Engineering  > 2018  >  18(3): 218-227
Next Previous
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]
    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]
    REN Ya-lei. Study on ship encounters using AIS data[D]. Wuhan: Wuhan University of Technology, 2013. (in Chinese).
    [3]
    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]
    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]
    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]
    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]
    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]
    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]
    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]
    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]
    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]
    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]
    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]
    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]
    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]
    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

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (969) PDF downloads(895) Cited by()
    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