界标窗口下数据流最大规范模式挖掘算法研究

The Maximal Regular Patterns Mining Algorithm Based on Landmark Window over Data Stream

首次对界标窗口下数据流最大规范模式挖掘问题进行了研究.为了克服na6ve算法在处理该问题时不具有增量计算的缺点,提出了一种基于边界界标窗口技术的数据流最大规范模式挖掘(data stream maximal regular patterns mining based on boundary landmark window,DSMRM-BLW)算法.该算法将数据流上的第1个待处理窗口定义为边界界标窗口,使用na6ve算法对其进行处理;之后每个窗口上的最大规范模式都可以基于前一个窗口上的最大规范模式集合增量获得,可以克服na6ve算法的缺点.实验结果表明:DSMRM-BLW算法是处理界标窗口下数据流最大规范模式挖掘的有效方法,与na6ve算法相比,具有相同的执行结果,但时间与空间效率得到了很大的提高.

Mining regular pattern is an emerging area.To the best of our knowledge,no method has been proposed to mine the maximal regular patterns about data stream.In this paper,the problem of mining maximal regular patterns based on the landmark window over data stream is focused at the first time.In order to resolve the issue that the na6 ve algorithm which is used to handle the maximal regular patterns mining based on the landmark window over data stream does not have the characteristic of incremental computation,the DSMRM-BLW（data stream maximal regular patterns mining based on boundary landmark window）algorithm is proposed.It takes the first window as the boundary landmark window,and handles it with the na6 ve algorithm.For all other windows,it can obtain the maximal regular patterns over them based on the ones over the adjacent last window incrementally,and can overcome the drawback of the na6 ve algorithm.It is revealed by the extensive experiments that the DSMRM-BLW algorithm is effective in dealing with the maximal regular patterns mining based on the landmark window over data stream,and outperforms the na6 ve algorithm in execution time and space consumption.