We propose an indexing technique for fast retrieval of similar subsequences using time warping distances. A time warping distance is a more suitable similarity measure than the Euclidean distance in many applications, where sequences may be of different lengths or different sampling rates. Our indexing technique uses a disk-based suffix tree as an index structure and employs lower-bound distance functions to filter out dissimilar subsequences without false dismissals. To make the index structure compact and thus accelerate the query processing, we convert sequences of continuous values to sequences of discrete values via a categorization method and store only a subset of suffixes whose first values are different from their preceding values. The experimental results reveal that our proposed technique can be a few orders of magnitude faster than sequential scanning.
|Number of pages||10|
|State||Published - 2000|
|Event||2000 IEEE 16th International Conference on Data Engineering (ICDE'00) - San Diego, CA, USA|
Duration: 29 Feb 2000 → 3 Mar 2000
|Conference||2000 IEEE 16th International Conference on Data Engineering (ICDE'00)|
|City||San Diego, CA, USA|
|Period||29/02/00 → 3/03/00|