SNT-index
Satoshi Koide, Yukihiro Tadokoro, Takayoshi Yoshimura · 2015
In the present study, we propose a novel spatio-temporal index structure for network-constrained trajectories, SNT-index --- Suffix-array-based Network-constrained Trajectory Index. The proposed method fast finds trajectories that follow a given route pattern within a certain time interval. The proposed method is based on two key concepts. The first is the introduction of the FM-index, which is often discussed in the field of compressed full-text substring matching. The FM-index enables fast pattern matching but does not support temporal filtering. The second concept is employing an inverse suffix array, which realizes the integration of the FM-index and the temporal information stored in a forest of B+trees.