Finding Constrained Frequent Episodes Using Minimal Occurrences

• Main Authors: MA, Xi, PANG, Hwee Hwa, TAN, Kian-Lee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2004
• Subjects: constrained frequent episode; episode mining; episode prefix tree; minimal occurrences; position pairs set; prefix-growth approach; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/1140; https://ink.library.smu.edu.sg/context/sis_research/article/2139/viewcontent/findingConstrainedFrequent_edited_.pdf
• Institution: Singapore Management University

Recurrent combinations of events within an event sequence, known as episodes, often reveal useful information. Most of the proposed episode mining algorithms adopt an apriori-like approach that generates candidates and then calculates their support levels. Obviously, such an approach is computationally expensive. Moreover, those algorithms are capable of handling only a limited range of constraints. In this paper, we introduce two mining algorithms - episode prefix tree (EPT) and position pairs set (PPS) - based on a prefix-growth approach to overcome the above limitations. Both algorithms push constraints systematically into the mining process. Performance study shows that the proposed algorithms run considerably faster than MINEPI (Mannila and Toivonen, 1996).