Title | ||
---|---|---|
A Polynomial-Delay Polynomial-Space Algorithm for Extracting Frequent Diamond Episodes from Event Sequences |
Abstract | ||
---|---|---|
In this paper, we study the problem of mining frequent diamond episodes efficiently from an input event sequence with sliding a window. Here, a diamond episode is of the form a ***E ***b , 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 (|Σ |2 n ) time per an episode and in O (|Σ | + n ) space, where Σ and n are an alphabet and the length the event sequence, respectively. Finally, we give experimental results on artificial event sequences with varying several mining parameters to evaluate the efficiency of the algorithm. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-642-01307-2_18 | PAKDD |
Keywords | Field | DocType |
frequent diamond episode,polynomial-delay polynomial-space algorithm,event sequences,input event sequence,frequent diamond episodes,mining parameter,artificial event sequence,polynomial-space algorithm polyfreqdmd,diamond episode,event sequence | Diamond,Data mining,Of the form,Polynomial,Computer science,Algorithm,PSPACE,Event sequence,Alphabet | Conference |
Volume | ISSN | Citations |
5476 | 0302-9743 | 3 |
PageRank | References | Authors |
0.40 | 9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Takashi Katoh | 1 | 39 | 11.29 |
Hiroki Arimura | 2 | 1130 | 92.90 |
Kouichi Hirata | 3 | 130 | 32.04 |