License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.COSIT.2022.26
URN: urn:nbn:de:0030-drops-169115
Go to the corresponding LIPIcs Volume Portal

Sharma, Arun ; Gupta, Jayant ; Shekhar, Shashi

Abnormal Trajectory-Gap Detection: A Summary (Short Paper)

LIPIcs-COSIT-2022-26.pdf (2 MB)


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.

BibTeX - Entry

  author =	{Sharma, Arun and Gupta, Jayant and Shekhar, Shashi},
  title =	{{Abnormal Trajectory-Gap Detection: A Summary}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{26:1--26:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-169115},
  doi =		{10.4230/LIPIcs.COSIT.2022.26},
  annote =	{Keywords: Spatial Data Mining, Trajectory Mining, Time Geography}

Keywords: Spatial Data Mining, Trajectory Mining, Time Geography
Collection: 15th International Conference on Spatial Information Theory (COSIT 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI