An Efficient Depth-first Search Algorithm for Extracting Frequent Diamond Episodes from Event Sequences

スポンサーリンク

概要

• 論文の詳細を見る

• 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(|Σ|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.

• 2009-12-24

著者

• Kouichi Hirata

  Department Of Artificial Intelligence Kyushu Institute Of Technology

• Takashi Katoh

  Graduate School Of Information Science And Technology Hokkaido University

• Hiroki Arimura

  Graduate School Of Information Science And Technology Hokkaido University

関連論文

• An Efficient Depth-first Search Algorithm for Extracting Frequent Diamond Episodes from Event Sequences

スポンサーリンク