基于trie merging机制数据流滑动窗口模型的频繁树模式挖掘  

Trie merging approach for mining frequent tree pattern over data stream sliding window

作　　者：吉小洪 徐爱萍[1] Ji Xiaohong;Xu Aiping(School of Computer,Wuhan University,Wuhan 430072,China)

机构地区：[1]武汉大学计算机学院,武汉430072

出　　处：《计算机应用研究》2020年第7期1993-1998,共6页Application Research of Computers

基　　金：国家重点研发计划重点专项资助项目(2017YFC0803700)。

摘　　要：因树型结构的良好表达能力,在互联网中传输的信息流越来越多以树型结构形式存储。但由于流式数据的时效性,隐含在数据流中的知识会随着时间的推移发生改变。针对数据流场景下挖掘最近时间段内的频繁子树模式的问题,提出了一种滑动窗口模型下挖掘频繁子树模式算法——SWMiner算法,用于挖掘数据流下任意时刻窗口所有的频繁子树模式。SWMiner算法使用基于前缀树的结构来压缩存储生成的树模式,并且使用trie merging机制有效地更新子树模式的支持度。实验结果表明,SWMiner算法在滑动窗口模型中的性能优于目前现有的常用算法,能有效地挖掘最近时间段内的频繁树模式。Due to the good expressing power of the tree-structured data format,the data stream transmitted on the Internet is preferred stored in a tree structure.However,knowledge embedded in a data stream is more likely to be changed over time,considering the problem of finding recent frequent tree patterns over a data stream sliding window,this paper proposed a method SWMiner which used to mine recent frequent tree patterns over sliding window,it used to mined the recent frequent tree pattern at any time step.SWMiner used a trie-based structure to compactly store the tree patterns and trie merging approach to support updating support of pattern efficiently.It conducted extensive experiments on several synthetic and real datasets.The results of experiment show that SWMiner performs much better than the well-known existing algorithm and can find the recent frequent tree pattern efficiently.

关 键 词：TRIE树 数据流 滑动窗口 频繁树模式 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]