Hybrid Lower-Dimensional Transformation for Similar Sequence Matching

Yang-Sae MOON  Jinho KIM 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E92-D  No.3  pp.541-544
Publication Date: 2009/03/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Data Mining
Keyword: 
databases,  data mining,  similar sequence matching,  time-series data,  lower-dimensional transformation, 

Full Text: PDF(190.3KB)

Summary: 
Lower-dimensional transformations in similar sequence matching show different performance characteristics depending on the type of time-series data. In this paper we propose a hybrid approach that exploits multiple transformations at a time in a single hybrid index. This hybrid approach has advantages of exploiting the similar effect of using multiple transformations and reducing the index maintenance overhead. For this, we first propose a new notion of hybrid lower-dimensional transformation that extracts various features using different transformations. We next define the hybrid distance to compute the distance between the hybrid transformed points. We then formally prove that the hybrid approach performs similar sequence matching correctly. We also present the index building and similar sequence matching algorithms based on the hybrid transformation and distance. Experimental results show that our hybrid approach outperforms the single transformation-based approach.