Abnormal Trajectory-Gap Detection: A Summary

Arun Sharma, Jayant Gupta, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given trajectories with gaps (i.e., missing data), we investigate algorithms to identify abnormal gaps for testing possible hypotheses of anomalous regions. Here, an abnormal gap within a trajectory is defined as an area where a given moving object did not report its location, but other moving objects did periodically. 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 transfer, and trans-shipments. The problem is challenging due to the difficulty of interpreting missing data within a trajectory gap, and the high computational cost of detecting gaps in such a large volume of location data proves computationally very expensive. The current literature 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. To overcome this limitation, we propose an abnormal gap detection (AGD) algorithm that leverages the concepts of a space-time prism model where we assume space-time interpolation. We then propose a refined memoized abnormal gap detection (Memo-AGD) algorithm that reduces comparison operations. We validated both algorithms using synthetic and real-world data. The results show that abnormal gaps detected by our algorithms give better estimates of abnormality than linear interpolation and can be used for further investigation from the human analysts.

Original languageEnglish (US)
Title of host publication15th International Conference on Spatial Information Theory, COSIT 2022
EditorsToru Ishikawa, Sara Irina Fabrikant, Stephan Winter
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772570
StatePublished - Sep 1 2022
Event15th International Conference on Spatial Information Theory, COSIT 2022 - Kobe, Japan
Duration: Sep 5 2022Sep 9 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference15th International Conference on Spatial Information Theory, COSIT 2022

Bibliographical note

Funding Information:
Funding This research is funded by an academic grant from the National Geospatial-Intelligence Agency (Award No. HM0476-20-1-0009, Project Title: Abnormal Trajectory Gap Detection). Approved for public release, 22-379.

Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.


  • Spatial Data Mining
  • Time Geography
  • Trajectory Mining


Dive into the research topics of 'Abnormal Trajectory-Gap Detection: A Summary'. Together they form a unique fingerprint.

Cite this