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 paper, 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.

通过空间时间索引和动态区域合并，提出了一种用于检测轨迹中异常间隙的方法，并在合成和真实世界海上轨迹数据上进行了实验验证。