Indexing network-constrained trajectories for connectivity-based queries

Recent advances in positioning and communication technologies have made it possible to collect trajectories of moving objects, and thus, corresponding applications that handle trajectories come into sight, e.g. applying vehicle trajectories to traffic studies, where various queries about trajectories are necessary. However, due to their special spatio-temporal query conditions, trajectory queries are different from existing GIS queries, and there is still a lack of efficient data-access methods to support queries about trajectories. In view of this, we develop a data-access method, named a Topology-based Mixed Index Structure (TMIS), to index network-constrained trajectories for connectivity-based queries. The TMIS indeed is not a novel index structure but a novel combination of simple and classical index structures linked by the topology of a network. The TMIS can support more query types through different combinations of simple and classical index structures and can be applied to a large network. Existing database management systems can be employed to implement the TMIS. In this paper, we first define network-constrained trajectories and connectivity-based queries, and then introduce the principles, architecture, algorithms, and query processing of the TMIS. Finally, we implement the TMIS and validate it through a series of analyses and experiments.