Contiguous item sequential pattern mining using UpDown Tree

Article type: Research Article

Authors: Chen, Jinlin

Affiliations: Computer Science Department, Queens College, City University of New York, 65-30 Kissena Blvd., Flushing, New York, NY 11367, USA. Tel.: +1 718 997 3497; Fax: +1 718 997 3513; E-mail: jchen@cs.qc.edu

Abstract: In this paper the problem of Contiguous Item Sequential Pattern (CISP) Mining is presented as a sequential pattern mining problem under two constraints. First, each element in a sequence consists of only one item. Second, items appearing in the sequences that contain a pattern must be adjacent with respect to the underlying order as they appear in the pattern. Even though the problem of CISP mining can be solved by using previous approaches on sequential pattern mining under a general constraint description framework, this may lead to poor performance due to the large searching space. To efficiently solve this problem, a new data structure, UpDown Tree, is proposed for CISP mining. UpDown Tree based approach can greatly improve the efficiency of CISP mining in terms of both time and memory comparing to previous approaches. An extensive experimental study has shown promising results with our approach.

Keywords: Data mining algorithm, sequential pattern, contiguous sequential pattern, transaction database, sequence database, performance analysis

DOI: 10.3233/IDA-2008-12103

Journal: Intelligent Data Analysis, vol. 12, no. 1, pp. 25-49, 2008