A New Signature-Based Indexing Scheme for Efficient Trajectory Retrieval in Spatial Networks

Jae-Woo CHANG  Jung-Ho UM 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E92-D  No.6  pp.1240-1249
Publication Date: 2009/06/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Database
Keyword: 
signature-based indexing scheme,  similar trajectory retrieval,  spatial network, 

Full Text: PDF(2.8MB)

Summary: 
Even though it is very important to retrieve similar trajectories with a given query trajectory, there has been a little research on trajectory retrieval in spatial networks, like road networks. In this paper, we propose an efficient indexing scheme for retrieving moving object trajectories in spatial networks. For this, we design a signature-based indexing scheme for efficiently dealing with the trajectories of current moving objects as well as for maintaining those of past moving objects. In addition, we provide an insertion algorithm for storing the segment information of a moving object trajectory as well as a retrieval algorithm to find a set of moving objects whose trajectories match the segments of a query trajectory. Finally, we show that our signature-based indexing scheme achieves at least twice better performance on trajectory retrieval than the leading trajectory indexing schemes, such as TB-tree, FNR-tree, and MON-tree.