A filtering method for searching similar multidimensional sequences under the time-warping distance

Abstract

The filtering method is currently the most suitable approach for the fast retrieval of similar sequences under the time-warping distance. Several filtering methods under the time-warping distance have been proposed, but they are only for real number sequences. This paper presents an efficient filtering method for the retrieval of similar multidimensional sequences. First, we propose three basic filtering measures (the end-point distance, the min-region distance, and the interim time-warping distance) based on the ones appeared in the literature, and one of their direct combinations (the point-region distance). Next, we investigate their problems with a large number of multidimensional sequences. In order to alleviate those problems, we extend the end-point distance and the min-region distance into the extended end-point distance and the segmented min-region distance, respectively, and combine them into a novel measure, the extended point-region distance. A multi-step architecture is adopted to implement the retrieval process with the proposed measure. Experiments with synthetic sequences are conducted for the performance comparison. (C) 2002 Elsevier Science Ltd. All rights reserved.