一种单遍扫描频繁模式树结构  

Single-pass Frequent Pattern Tree Structure

作　　者：谭军[1,2] 卜英勇[2] 杨勃[2] 

机构地区：[1]中南林业科技大学计算机学院,长沙412006 [2]中南大学机电工程学院,长沙410083

出　　处：《计算机工程》2010年第14期32-33,共2页Computer Engineering

基　　金：国家自然科学基金资助项目"深海钴结壳微地形检测技术及最佳采集深度建模研究"(50474052)

摘　　要：针对频繁模式增长算法无法适应数据流的无限性和流动性的特点,提出一种新颖的FP-tree的变形结构-SP-tree,只需单遍扫描便能容纳全部数据库信息。为使SP-tree具有与FP-tree一样良好的压缩性能,给出一种有效的动态重构树的方法,称为宽度排序方法,该方法能够在挖掘过程中动态地逐条分支地重构树,最终产生一棵频繁递减的前缀树。实验结果表明,SP-tree的压缩性能优于其他单遍扫描的前缀树结构。Aiming at the problem that FP-growth algorithm requires two database scans,which are not consistent with efficient data stream processing,this paper presents a novel tree structure which is a variation of FP-tree,called SP-tree,which captures database information with one scan.For making SP-tree have the same compact performance,it presents an efficient dynamic tree restructuring method,called the breadth sorting method,which restructures a frequency-descending prefix-tree branch-by-branch.Experimental results show that compact performance of the SP-tree is better than other prefix-tree structure with one scan.

关 键 词：数据流 频繁模式增长算法 单遍扫描模式树 宽度排序方法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]