skip to main content
research-article

Physics-Based Abnormal Trajectory Gap Detection

Published: 12 October 2024 Publication History

Abstract

Given trajectories with gaps (i.e., missing data), we investigate algorithms to identify abnormal gaps in trajectories which occur when a given moving object did not report its location, but other moving objects in the same geographic region periodically did. The problem is important due to its societal applications, such as improving maritime safety and regulatory enforcement for global security concerns, such as illegal fishing, illegal oil transfers, and trans-shipments. The problem is challenging due to the difficulty of bounding the possible locations of the moving object during a trajectory gap, and the very high computational cost of detecting gaps in such a large volume of location data. The current literature on anomalous trajectory detection assumes linear interpolation within gaps, which may not be able to detect abnormal gaps since objects within a given region may have traveled away from their shortest path. In preliminary work, we introduced an abnormal gap measure that uses a classical space-time prism model to bound an object's possible movement during the trajectory gap and provided a scalable memoized gap detection algorithm (Memo-AGD). In this article, we propose a space time-aware gap detection (STAGD) approach to leverage space-time indexing and merging of trajectory gaps. We also incorporate a dynamic region merge-based (DRM) approach to efficiently compute gap abnormality scores. We provide theoretical proofs that both algorithms are correct and complete and also provide analysis of asymptotic time complexity. Experimental results on synthetic and real-world maritime trajectory data show that the proposed approach substantially improves computation time over the baseline technique.

References

[1]
2020. MarineTraffic. Retrieved from https://www.marinetraffic.com/en/ais/
[2]
Petko Bakalov, Marios Hadjieleftheriou, Eamonn Keogh, and Vassilis J. Tsotras. 2005. Efficient trajectory joins using symbolic representations. In Proceedings of the 6th International Conference on Mobile Data Management, 86–93.
[3]
Petko Bakalov and Vassilis J. Tsotras. 2006. Continuous spatiotemporal trajectory joins. In Proceedings of the International Conference on GeoSensor Networks. Springer, 109–128.
[4]
BOEM and NOAA. 2020. MarineCadastre. Retrieved from https://marinecadastre.gov/ais/
[5]
V. Chandola, A. Banerjee, and V. Kumar. 2009. Anomaly detection: A survey. ACM Computing Surveys (CSUR) 41, 3 (2009), 1–58.
[6]
C. Chen, D. Zhang, P. S. Castro, N. Li, L. Sun, S. Li, and Z. Wang. 2013. iBOAT: Isolation-based online anomalous trajectory detection. IEEE Transactions on Intelligent Transportation Systems 14, 2 (2013), 806–818.
[7]
Jiahua Chen and Jun Shao. 2001. Jackknife variance estimation for nearest-neighbor imputation. Journal of the American Statistical Association 96, 453 (2001), 260–269.
[8]
L. Chen, M. Tamer Özsu, and V. Oria. 2005. Robust and fast similarity search for moving object trajectories. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, 491–502.
[9]
Yun Chen and Jignesh M. Patel. 2009. Design and evaluation of trajectory join algorithms. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 266–275.
[10]
Reynold Cheng, Jinchuan Chen, Mohamed Mokbel, and Chi-Yin Chow . 2008. Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. IEEE, 973–982.
[11]
Hui Ding, Goce Trajcevski, and Peter Scheuermann. 2008. Efficient similarity join of large sets of moving object trajectories. In Proceedings of the 2008 15th International Symposium on Temporal Representation and Reasoning. IEEE, 79–87.
[12]
S. Dodge, R. Weibel, and A. Lautenschütz. 2008. Towards a taxonomy of movement patterns. Information Visualization 7, 3–4 (2008), 240–252.
[13]
Majid Farhadloo, Arun Sharma, Jayant Gupta, Alexey Leontovich, Svetomir N. Markovic, and Shashi Shekhar. 2024. Towards spatially-lucid AI classification in non-euclidean space: An application for MxIF oncology data. In Proceedings of the 2024 SIAM International Conference on Data Mining (SDM). SIAM, 616–624.
[14]
John Fox. 2015. Applied Regression Analysis and Generalized Linear Models. Sage Publications.
[15]
Subhankar Ghosh, Jayant Gupta, Arun Sharma, Shuai An, and Shashi Shekhar. 2022. Towards geographically robust statistically significant regional colocation pattern detection. In Proceedings of the 5th ACM SIGSPATIAL International Workshop on GeoSpatial Simulation, 11–20.
[16]
Subhankar Ghosh, Jayant Gupta, Arun Sharma, Shuai An, and Shashi Shekhar. 2023. Reducing false discoveries in statistically-significant regional-colocation mining: A summary of results. In Proceedings of the 12th International Conference on Geographic Information Science (GIScience ’23). Schloss-Dagstuhl-Leibniz Zentrum für Informatik.
[17]
S. Gibbens. 2018. How illegal fishing is being tracked from space. National Geographic.
[18]
Jayant Gupta and Arun Sharma. 2022. Mining taxonomy-aware colocations: A summary of results. In Proceedings of the 30th International Conference on Advances in Geographic Information Systems, 1–11.
[19]
Estevam R. Hruschka, Eduardo R. Hruschka, and Nelson F. F. Ebecken. 2007. Bayesian networks for imputation in classification problems. Journal of Intelligent Information Systems 29 (2007), 231–252.
[20]
Chih-Chieh Hung, Wen-Chih Peng, and Wang-Chien Lee. 2015. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. The VLDB Journal 24, 2 (2015), 169–192.
[21]
Bart Kuijpers and Walied Othman. 2009. Modeling uncertainty of moving objects on road networks via space–time prisms. International Journal of Geographical Information Science 23, 9 (2009), 1095–1117.
[22]
K. Vimal Kumar, Divakar Yadav, and Arun Sharma. 2015. Graph based technique for Hindi text summarization. In Information Systems Design and Intelligent Applications: Proceedings of 2nd International Conference INDIA 2015, Vol. 1. Springer, 301–310.
[23]
Po-Ruey Lei. 2016. A framework for anomaly detection in maritime trajectory behavior. Knowledge and Information Systems 47, 1 (2016), 189–214.
[24]
Milton Lim. 2021. Gauss, Least Squares, and the Missing Planet. Retrieved from https://www.actuaries.digital/2021/03/31/gauss-least-squares-and-the-missing-planet/
[25]
Rake& Agrawal King-lp Lin and Harpreet S.Sawhney Kyuseok Shim. 1995. Fast similarity search in the presence of noise, scaling, and translation in time-series databases. In Proceeding of the 21th International Conference on Very Large Data Bases. Citeseer, 490–501.
[26]
Fabio Mazzarella, Michele Vespe, Alfredo Alessandrini, Dario Tarchi, Giuseppe Aulicino, and Antonio Vollero. 2017. A novel anomaly detection approach to identify intentional AIS on-off switching. Expert Systems with Applications 78 (2017), 110–123.
[27]
H. J. Miller. 1991. Modelling accessibility using space-time prism concepts within geographical information systems. International Journal of Geographical Information System 5, 3 (1991), 287–301.
[28]
G. Pallotta, M. Vespe, and K. Bryan. 2013. Vessel pattern knowledge discovery from AIS data: A framework for anomaly detection and route prediction. Entropy 15, 6 (2013), 2218–2245.
[29]
D. Pfoser and C. S. Jensen. 1999. Capturing the uncertainty of moving-object representations. In Proceedings of the International Symposium on Spatial Databases. Springer, 111–131.
[30]
Dieter Pfoser, Christian S. Jensen, and Yannis Theodoridis. 2000. Novel approaches to the indexing of moving object trajectories. In Proceedings of the Very Large Data Base (VLDB), 395–406.
[31]
E. Rancourt. 1999. Estimation with nearest neighbour imputation at statistics Canada. In Proceedings of the Section on Survey Research Methods, American Statistical Association, 131–138.
[32]
M. Riveiro, G. Pallotta, and M. Vespe. 2018. Maritime anomaly detection: A review. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 8, 5 (2018), e1266.
[33]
Shuo Shang, Lisi Chen, Zhewei Wei, Christian S. Jensen, Kai Zheng, and Panos Kalnis. 2017. Trajectory similarity join in spatial networks. In Proceedings of the VLDB Endowment, 1178–1189.
[34]
Arun Sharma, Majid Farhadloo, Yan Li, Jayant Gupta, Aditya Kulkarni, and Shashi Shekhar. 2022. Understanding Covid-19 effects on mobility: A community-engaged approach. AGILE: GIScience Series 3 (2022), 14.
[35]
Arun Sharma, Jayant Gupta, and Subhankar Ghosh. 2022. Towards a tighter bound on possible-rendezvous areas: preliminary results. In Proceedings of the 30th International Conference on Advances in Geographic Information Systems, 1–11.
[36]
Arun Sharma, Jayant Gupta, and Shashi Shekhar. 2022. Abnormal trajectory-gap detection: A summary (short paper). In Proceedings of the 15th International Conference on Spatial Information Theory (COSIT ’22) Leibniz International Proceedings in Informatics, Vol. 240, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 26:1–26:10. DOI:
[37]
Arun Sharma, Zhe Jiang, and Shashi Shekhar. 2022. Spatiotemporal data mining: A survey. arXiv:2206.12753 . Retrieved from https://doi.org/10.48550/arXiv.2206.12753
[38]
Arun Sharma and Shashi Shekhar. 2022. Analyzing trajectory gaps to find possible rendezvous region. ACM Transactions on Intelligent Systems and Technology (TIST) 13, 3 (2022), 1–23.
[39]
Arun Sharma, Xun Tang, Jayant Gupta, Majid Farhadloo, and Shashi Shekhar. 2020. Analyzing trajectory gaps for possible rendezvous: A summary of results. In Proceedings of the 11th International Conference on Geographic Information Science (GIScience ’21)-Part I. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 1–16.
[40]
Na Ta, Guoliang Li, Yongqing Xie, Changqi Li, Shuang Hao, and Jianhua Feng. 2017. Signature-based trajectory similarity join. IEEE Transactions on Knowledge and Data Engineering 29, 4 (2017), 870–883.
[41]
Goce Trajcevski, Alok Choudhary, Ouri Wolfson, Li Ye, and Gang Li. 2010. Uncertain range queries for necklaces. In Proceedings of the 2010 11th International Conference on Mobile Data Management. IEEE, 199–208.
[42]
Wikipedia. 2021. Space Shuttle Columbia Disaster. Retrieved from https://en.wikipedia.org/wiki/Space_Shuttle_Columbia_disaster
[43]
Stephan Winter and Zhang-Cai Yin. 2010. Directed movements in probabilistic time geography. International Journal of Geographical Information Science 24, 9 (2010), 1349–1365.
[44]
Byoung-Kee Yi, Hosagrahar V. Jagadish, and Christos Faloutsos. 1998. Efficient retrieval of similar time sequences under time warping. In Proceedings 14th International Conference on Data Engineering. IEEE, 201–208.
[45]
Pengxiang Zhao, David Jonietz, and Martin Raubal. 2021. Applying frequent-pattern mining and time geography to impute gaps in smartphone-based human-movement data. International Journal of Geographical Information Science 35, 11 (2021), 2187–2215.
[46]
Yu Zheng. 2015. Trajectory data mining: An overview. ACM Transactions on Intelligent Systems and Technology (TIST) 6, 3 (2015), 1–41.

Cited By

View all
  • (2025)Climate smart computing: A perspectivePervasive and Mobile Computing10.1016/j.pmcj.2025.102019108(102019)Online publication date: Mar-2025
  • (2024)Spatial Computing Opportunities in Biomedical Decision Support: The Atlas-EHR VisionACM Transactions on Spatial Algorithms and Systems10.1145/367920110:3(1-36)Online publication date: 25-Sep-2024

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Intelligent Systems and Technology
ACM Transactions on Intelligent Systems and Technology  Volume 15, Issue 5
October 2024
719 pages
EISSN:2157-6912
DOI:10.1145/3613688
  • Editor:
  • Huan Liu
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2024
Online AM: 15 June 2024
Accepted: 03 June 2024
Revised: 19 May 2024
Received: 27 September 2023
Published in TIST Volume 15, Issue 5

Check for updates

Author Tags

  1. Trajectory gaps
  2. space time prism
  3. time geography
  4. anomaly gaps
  5. trajectory mining

Qualifiers

  • Research-article

Funding Sources

  • National Geospatial-Intelligence Agency

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)306
  • Downloads (Last 6 weeks)28
Reflects downloads up to 12 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Climate smart computing: A perspectivePervasive and Mobile Computing10.1016/j.pmcj.2025.102019108(102019)Online publication date: Mar-2025
  • (2024)Spatial Computing Opportunities in Biomedical Decision Support: The Atlas-EHR VisionACM Transactions on Spatial Algorithms and Systems10.1145/367920110:3(1-36)Online publication date: 25-Sep-2024

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Full Text

View this article in Full Text.

Full Text

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media