Abstract
Building a rich and informative model from raw data is a hard but valuable process with many applications. Ship routing and scheduling are two essential operations in the maritime industry that can save a lot of resources if they are optimally designed, but still, need a lot of information to be successful. Past and recent works in the field assume the availability of information such as the birth time-windows, cargo volumes, and container handling productivity at ports and cruising speed. They employ navigation maps that contain information about the major sailing paths and have knowledge about bigger or smaller ports and offshore platforms. In this work, we present a methodology for extracting information about the navigation network for an area, using data from the trajectories of multiple vessels, which are collected using the Automatic Identification System (AIS). We introduce a method for identifying the points of major interest to the trajectory of a vessel and two clustering techniques for identifying: i) key areas in the monitored region such as ports, platforms or areas where vessels change their course (e.g., capes); and ii) the speed and course patterns of ships of a particular type when they follow a typical route. The resulting information is modeled using a network abstraction where nodes correspond to the areas identified by the first clustering technique. After, edges are enriched with information about the groups extracted using the second clustering technique. The first analysis on a real dataset in the area of the eastern Mediterranean sea demonstrates the capabilities of the proposed model and the information it can provide. The use of the model in an outlier behavior detection task also shows interesting results.
Similar content being viewed by others
References
Andrienko N, Andrienko G (2011) Spatial generalization and aggregation of massive movement data. IEEE Trans Vis Comput Graph 17:205–19. https://doi.org/10.1109/TVCG.2010.44
Andrienko N, Andrienko G (2013) Visual analytics of movement: an overview of methods, tools, and procedures. Information Visualization https://doi.org/10.1177/1473871612457601
Andrienko N, Andrienko G, Rinzivillo S (2015) Exploiting spatial abstraction in predictive analytics of vehicle traffic. ISPRS Int J Geo-Inf 4(2):591–606
Arguedas VF, Pallotta G, Vespe M (2018) Maritime traffic networks: From historical positioning data to unsupervised maritime traffic monitoring. IEEE Trans ITS 19(3):722–732
Carlini E, de Lira VM, Soares A, Etemad M, Machado BB, Matwin S (2020) Uncovering vessel movement patterns from ais data with graph evolution analysis. In: Proceedings of the Workshops of the EDBT/ICDT 2020 Joint Conference, vol 2578. CEUR Workshop Proceedings, Copenhagen. http://ceur-ws.org/Vol-2578/BMDA5.pdf
Chandola V (2009) Anomaly detection for symbolic sequences and time series data. PhD Thesis, University of Minnesota
Chandola V, Banerjee A, Kumar V (2009) Anomaly detection: a survey. ACM Computi Surv (CSUR) 41(3):15
Coscia P, Braca P, Millefiori L M, Palmieri FA, Willett P (2018) Multiple ornstein-uhlenbeck processes for maritime traffic graph representation. IEEE Transactions on Aerospace and Electronic Systems
Dividino R, Soares A, Matwin S, Isenor AW, Webb S, Brousseau M (2018) Semantic integration of real-time heterogeneous data streams for ocean-related decision making. In: Big Data and Artificial Intelligence for Military Decision Making, STO. https://doi.org/10.14339/STO-MP-IST-160-S1-3-PDF
Douglas DH, Peucker TK (1973) Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: Int J Geograph Inf Geovis 10(2):112–122
Ester M, Kriegel HP, Sander J, Xu X (1996) A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise. In: SIGKDD’96. AAAI Press, pp 226–231. http://dl.acm.org/citation.cfm?id=3001460.3001507
Etemad M (2018) Transportation modes classification using feature engineering. PhD Thesis, Dalhousie University. CA arXiv preprint arXiv:180710876
Etemad M, Soares Júnior A, Matwin S (2018) Predicting transportation modes of gps trajectories using feature engineering and noise removal. In: 31st Canadian Conference on Artificial Intelligence. Springer, pp 259–264
Etemad M, Júnior AS, Hoseyni A, Rose J, Matwin S (2019) A trajectory segmentation algorithm based on interpolation-based change detection strategies. In: Proceedings of the Workshops of the EDBT/ICDT 2019 Joint Conference, EDBT/ICDT 2019, Lisbon. http://ceur-ws.org/Vol-2322/BMDA_4.pdf
Fu Z, Hu W, Tan T (2005) Similarity based vehicle trajectory clustering and anomaly detection. In: IEEE International Conference on Image Processing 2005, vol 2. IEEE, pp II–602
Hexeberg S, Flåten AL, Brekke EF et al (2017) Ais-based vessel trajectory prediction. In: 2017 20Th international conference on information fusion (Fusion). IEEE, pp 1–8
Holst A, Bjurling B, Ekman J, Rudström Å, Wallenius K, Björkman M, Fooladvandi F, Laxhammar R, Trönninger J (2012) A joint statistical and symbolic anomaly detection system: Increasing performance in maritime surveillance. In: 15th International Conf. on Information Fusion. IEEE, pp 1919–1926
Junior AS, Times VC, Renso C, Matwin S, Cabral LA (2018) A semi-supervised approach for the semantic segmentation of trajectories. In: 2018 19Th IEEE international conference on mobile data management (MDM). IEEE, pp 145–154
Kontopoulos I, Spiliopoulos G, Zissis D, Chatzikokolakis K, Artikis A (2018) Countering Real-time stream poisoning: An architecture for detecting vessel spoofing in streams of ais data. In: 4Th IEEE international conference on big data intelligence and computing (datacom 2018)
Laxhammar R, Falkman G, Sviestins E (2009) Anomaly detection in sea traffic - A comparison of the Gaussian Mixture Model and the Kernel Density Estimator. In: 2009 12th International Conference on Information Fusion, pp 756–763
Le Guillarme N, Lerouvreur X (2013) Unsupervised extraction of knowledge from s-ais data for maritime situational awareness. In: Proceedings of the 16th International Conference on Information Fusion. IEEE, pp 2025–2032
Lee JG, Han J, Whang KY (2007) Trajectory clustering: a partition-and-group framework. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of data. ACM, pp 593–604
Li Y, Han J, Yang J (2004) Clustering moving objects. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, KDD ’04, New York, p 617–622. https://doi.org/10.1145/1014052.1014129
Liu LX, Song JT, Guan B, Wu ZX, He KJ (2012) Tra-dbscan: a algorithm of clustering trajectories. In: Applied mechanics and materials, vol 121
Mao J, Jin C, Zhang Z, Zhou A (2017) Anomaly detection for trajectory big data: Advancements and framework. Ruan Jian Xue Bao/J Softw 28(1):17–34
Mao J, Sun P, Jin C, Zhou A (2018) Outlier detection over distributed trajectory streams. In: Proceedings of the 2018 SIAM International Conference on Data Mining. SIAM, pp 64–72
Meratnia N, Rolf A (2004) Spatiotemporal compression techniques for moving point objects. In: International Conference on Extending Database Technology. Springer, pp 765–782
Nanni M, Pedreschi D (2006) Time-focused clustering of trajectories of moving objects. J Intell Inf Syst 27(3):267–289
Pallotta G, Vespe M, Bryan K (2013) Vessel pattern knowledge discovery from ais data: a framework for anomaly detection and route prediction. Entropy 15(6):2218–2245
Patroumpas K, Alevizos E, Artikis A, Vodas M, Pelekis N, Theodoridis Y (2017) Online event recognition from moving vessel trajectories. GeoInformatica 21(2):389–427
Rhodes BJ, Bomberger NA, Seibert M, Waxman AM (2005) Maritime situation monitoring and awareness using learning mechanisms. In: MILCOM 2005. IEEE, pp 646–652
Sánchez-Heres LF (2018) Simplification and event identification for ais trajectories: the equivalent passage plan method. J Navigat:1–14
Soares A, Dividino R, Abreu F, Brousseau M, Isenor AW, Webb S, Matwin S (2019) Crisis: Integrating ais and ocean data streams using semantic web standards for event detection. In: International Conference on Military Communications and Information Systems
Soares Júnior A, Moreno BN, Times VC, Matwin S, Cabral LdAF (2015) Grasp-uts: an algorithm for unsupervised trajectory segmentation. Int J Geogr Inf Sci 29(1):46–68
Soares Júnior A, Renso C, Matwin S (2017) Analytic: an active learning system for trajectory classification. IEEE Comput Graph Appl 37(5):28–39
Speičys L, Jensen CS (2008) Enabling location-based services—multi-graph representation of transportation networks. GeoInformatica 12(2):219–253
Stefanakis E (2016) mr-v: Line simplification through mnemonic rasterization. Geomatica 70(4):269–282
Tampakis P, Pelekis N, Andrienko N, Andrienko G, Fuchs G, Theodoridis Y (2018) Time-aware sub-trajectory clustering in hermes@ postgresql. In: 2018 IEEE 34Th international conference on data engineering (ICDE). IEEE, pp 1581–1584
Tienaah T, Stefanakis E, Coleman D (2015) Contextual douglas-peucker simplification. Geomatica 69(3):327–338
Valsamis A, Tserpes K, Zissis D, Anagnostopoulos D, Varvarigou T (2017) Employing traditional machine learning algorithms for big data streams analysis: The case of object trajectory prediction. J Syst Softw 127:249–257
Varlamis I, Tserpes K, Sardianos C (2018) Detecting search and rescue missions from ais data. In: 2018 IEEE 34Th international conference on data engineering workshops (ICDEW). IEEE, pp 60–65
Varlamis I, Tserpes K, Etemad M, Júnior A S, Matwin S (2019) A network abstraction of multi-vessel trajectory data for detecting anomalies. In: EDBT/ICDT Workshops
Yap P (2002) Grid-based path-finding. In: Conference of the Canadian Society for Computational Studies of Intelligence. Springer, pp 44–55
Yuan G, Sun P, Zhao J, Li D, Wang C (2017) A review of moving object trajectory clustering algorithms. Artif Intell Rev 47(1):123–144
Zhao L, Shi G (2018) A method for simplifying ship trajectory based on improved douglas–peucker algorithm. Ocean Eng 166:37–46
Zhao L, Shi G, Yang J (2018) Ship trajectories pre-processing based on ais data. J Navigat:1–21
Zhu L, Chiu YC, Chen Y (2017) Road network abstraction approach for traffic analysis: framework and numerical analysis. IET Intell Transp Syst 11(7):424–430
Acknowledgments
This work has been developed in the frame of the MASTER project, which has received funding from the European Union’ s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 777695.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Varlamis, I., Kontopoulos, I., Tserpes, K. et al. Building navigation networks from multi-vessel trajectory data. Geoinformatica 25, 69–97 (2021). https://doi.org/10.1007/s10707-020-00421-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10707-020-00421-y