[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Information and Media Technologies
Online ISSN : 1881-0896
ISSN-L : 1881-0896
Computing
An Efficient Depth-first Search Algorithm for Extracting Frequent Diamond Episodes from Event Sequences
Takashi KatohHiroki ArimuraKouichi Hirata
Author information
JOURNAL FREE ACCESS

2010 Volume 5 Issue 2 Pages 459-470

Details
Abstract

In this paper, we study the problem of mining frequent diamond episodes efficientlyfrom an input event sequence with sliding a window. Here, a diamond episode is of the form aEb, which means that every event of E follows an event a and is followed by an event b. Then, we design a polynomial-delay and polynomial-space algorithm PolyFreqDmd that finds all of the frequent diamond episodes without duplicates from an event sequence in O(|Σ|2l) time per an episode and in O(|Σ|+l) space, where Σ and l are an alphabet and the length of the event sequence, respectively. Finally, we give experimental results on artificial and real-world event sequences with varying several mining parameters to evaluate the efficiency of the algorithm.

Content from these authors
© 2010 by Information Processing Society of Japan
Previous article Next article
feedback
Top