面向事件流的频繁片断计数算法

Fast Algorithm for Frequent Episodes Counting in Event Stream

在事件流上挖掘频繁片断已经成为近来研究的热点,在很多应用中起到重要作用。以往的研究提出了一些挖掘算法,包括基于滑动窗口和基于非重叠出现的方法。然而,这些算法在处理基于片断互异出现的支持度计数时,效率很低甚至无效。为此,提出了一种包含状态计数的有限状态自动机模型,并使用该模型给出了一种高效挖掘算法。从理论上对算法的效率和有效性进行了分析;实验结果证明了算法是有效且高效的。

With occurrences of many related applications,recently frequent episodes mining in event stream has become a hot research topic in data mining field.There exists some algorithms for frequent episodes mining such as window-based and non-overlapped occurrences based methods.However,these algorithms are not efficient,or even incapable,when dealing with the distinct occurrences based frequency counting of an episode which is essentially more effective.To solve the problem,this paper introduces a finite state automaton with state counting,and consequently proposes an efficient algorithm based on this model.It also gives theoretical analysis about the cost and effectiveness of this algorithm.Experimental results also verify the efficiency and effectiveness of the proposed algorithm.