Discovering and Matching Elastic Rules from Sequence Databases

Issue title: Intelligent Systems

Article type: Research Article

Authors: Sang Hyun, Park | Wesley W., Chu

Affiliations: Department of Computer Science, University of California, Los Angeles, Los Angeles, CA 90095, USA (e-mail: shpark@cs.ucla.edu) | Department of Computer Science, University of California, Los Angeles, Los Angeles, CA 90095, USA (e-mail wwc@cs.ucla.edu)

Abstract: This paper presents techniques for discovering and matching rules with {\em elastic patterns}. Elastic patterns are ordered lists of elements that can be stretched along the time axis. Elastic patterns are useful for discovering rules from data sequences with different sampling rates. For fast discovery of rules whose heads (left-hand sides) and bodies (right-hand sides) are elastic patterns, we construct a trimmed suffix tree from succinct forms of data sequences and keep the tree as a compact representation of rules. The trimmed suffix tree is also used as an index structure for finding rules matched to a target head sequence. When matched rules cannot be found, the concept of {\em rule relaxation} is introduced. Using a cluster hierarchy and relaxation error as a new distance function, we find the least relaxed rules that provide the most specific information on a target head sequence. Experiments on synthetic data sequences reveal the effectiveness of our proposed approach.

Keywords: Knowledge Discovery , Data Mining,, Elastic Patterns, Sequence Databases

Journal: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 75-90, 2001