Abstract | ||
---|---|---|
In this paper, we introduce the class of k-partite episodes, which are time-series patterns of the form 〈A1,..., Ak〉 for sets Ai (1 ≤ i ≤ k) of events meaning that, in an input event sequence, every event of Ai is followed by every event of Ai+1 for every 1 ≤ i k. Then, we present a backtracking algorithm KPAR and its modification KPAR2 that find all of the frequent k-partite episodes from an input event sequence without duplication. By theoretical analysis, we show that these two algorithms run in polynomial delay and polynomial space in total input size. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-642-14888-0_26 | JSAI-isAI Workshops |
Keywords | Field | DocType |
backtracking algorithm,polynomial delay,total input size,input event sequence,i k,polynomial space,sets ai,k-partite episode,frequent k-partite episode,modification kpar2,time series | Combinatorics,Polynomial,Of the form,Window Width,Algorithm,PSPACE,Event sequence,Backtracking,Mathematics | Conference |
Volume | ISSN | ISBN |
6284 | 0302-9743 | 3-642-14887-5 |
Citations | PageRank | References |
3 | 0.40 | 15 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Takashi Katoh | 1 | 39 | 11.29 |
Hiroki Arimura | 2 | 1130 | 92.90 |
Kouichi Hirata | 3 | 130 | 32.04 |