Efficient Coverage Query Over Transition Trajectories

With the widespread adoption of GPS-enabled vehicles, an unprecedented volume of transition trajectory data has become available from various applications. For example, Uber, DiDi ride-sharing and Public Transport Authorities. In this paper, we study two novel classes of coverage queries for transition trajectories: tight coverage query (TCQ) and loose coverage query (LCQ). To address these queries efficiently, we propose the AT-tree, an adaptive index structure that incrementally builds an index by leveraging prior query results. We also develop two variants, the LAT-tree and TAT-tree, which are optimized for LCQ and TCQ respectively, by merging specific tree nodes to enhance performance. Additionally, we propose several enhancement strategies to further improve the efficiency of our index structures. Experimental study with real datasets confirms the efficiency and practicality of our index and algorithms.