Flexible and Fast Similarity Search for Enriched Trajectories

Hideaki OHASHI  Toshiyuki SHIMIZU  Masatoshi YOSHIKAWA  

IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.9   pp.2081-2091
Publication Date: 2017/09/01
Publicized: 2017/05/30
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016EDP7482
Type of Manuscript: PAPER
Category: Data Engineering, Web Information Systems
trajectories,  similarity search,  dynamic time warping,  

Full Text: PDF(670.3KB)>>
Buy this Article

In this study, we focus on a method to search for similar trajectories. In the majority of previous works on searching for similar trajectories, only raw trajectory data were used. However, to obtain deeper insights, additional time-dependent trajectory features should be utilized depending on the search intent. For instance, to identify similar combination plays in soccer games, such additional features include the movements of the team players. In this paper, we develop a framework to flexibly search for similar trajectories associated with time-dependent features, which we call enriched trajectories. In this framework, weights, which represent the relative importance of each feature, can be flexibly given by users. Moreover, to facilitate fast searching, we first propose a lower bounding measure of the DTW distance between enriched trajectories, and then we propose algorithms based on this lower bounding measure. We evaluate the effectiveness of the lower bounding measure and compare the performances of the algorithms under various conditions using soccer data and synthetic data. Our experimental results suggest that the proposed lower bounding measure is superior to the existing measure, and one of the proposed algorithms, which is based on the threshold algorithm, is suitable for practical use.