Enhanced Indexing and Querying of Trajectories in Road Networks via String Algorithms

摘要

In this article, we propose a novel indexing and querying method for trajectories constrained in a road network. We aim to provide efficient algorithms for various types of spatiotemporal queries that involve routing in road networks, such as (1) finding moving objects that have traveled along a given path during a given time interval, (2) extracting all paths traveled after a given spatiotemporal context, and (3) enumerating all paths between two locations traveled during a certain time interval. Unlike the existing methods in spatial database research, we employ indexing techniques and algorithms from string processing. This idea is based on the fact that we can represent spatial paths as strings, because trajectories in a network are represented as sequences of road segment IDs. The proposed SNT-index (suffix-array-based network-constrained trajectory index) introduces two novel concepts to trajectory indexing. The first is FM-index, which is a compact in-memory data structure for pattern matching. The second is an inverse suffix array, which allows the FM-index to be integrated with the temporal information stored in a forest of B~+-trees. Thanks to these concepts, we can reduce the number of B~+-tree accesses required by the query processing algorithms to a constant number, something that cannot be achieved with existing methods. Although an FM-index is essentially a static index, we also propose a practical method of appending new data to the index. Finally, experiments show that our method can process the target queries for more than 1 million trajectories in a few tens of milliseconds, which is significantly faster than what the baseline algorithms can achieve without string algorithms.