《计算机应用研究》|Application Research of Computers

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

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

免费全文下载 (已被下载 次)  
获取PDF全文
作者 吉小洪,徐爱萍
机构 武汉大学 计算机学院,武汉 430072
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2020)07-015-1993-06
DOI 10.19734/j.issn.1001-3695.2019.01.0006
摘要 因树型结构的良好表达能力,在互联网中传输的信息流越来越多以树型结构形式存储。但由于流式数据的时效性,隐含在数据流中的知识会随着时间的推移发生改变。针对数据流场景下挖掘最近时间段内的频繁子树模式的问题,提出了一种滑动窗口模型下挖掘频繁子树模式算法——SWMiner算法,用于挖掘数据流下任意时刻窗口所有的频繁子树模式。SWMiner算法使用基于前缀树的结构来压缩存储生成的树模式,并且使用trie merging机制有效地更新子树模式的支持度。实验结果表明,SWMiner算法在滑动窗口模型中的性能优于目前现有的常用算法,能有效地挖掘最近时间段内的频繁树模式。
关键词 trie树; 数据流; 滑动窗口; 频繁树模式
基金项目 国家重点研发计划重点专项资助项目(2017YFC0803700)
本文URL http://www.arocmag.com/article/01-2020-07-015.html
英文标题 Trie merging approach for mining frequent tree pattern over data stream sliding window
作者英文名 Ji Xiaohong, Xu Aiping
机构英文名 School of Computer,Wuhan University,Wuhan 430072,China
英文摘要 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 me-thod 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 tree; data stream; sliding window; frequent tree pattern
参考文献 查看稿件参考文献
 
收稿日期 2019/1/6
修回日期 2019/3/18
页码 1993-1998
中图分类号 TP391
文献标志码 A