蒋廷耀，廖 强

(三峡大学计算机与信息学院，湖北 宜昌 443002)

在数据挖掘领域，图数据中频繁子图模式挖掘［1］已引起研究学者们极大的关注。图数据挖掘已成为数据挖掘和机器学习的研究新方向。图挖掘在许多实际应用中具有巨大的潜在价值，这些应用包括语义网络［2］、生物网络分析［3-4］和化学化合物分类［5］等。

近年来，从图结构数据流上发现子图频繁模式已成为一个具有挑战性的课题。FP-growth［6］是一种高效的经典算法，然而两遍数据库扫描不能适应数据流的无限性和流动性的特点。为了克服该局限性，需要设计一种有效的全局数据结构，通过一次扫描就能包含所有数据库信息。

笔者提出了一种新的一次扫描前缀树结构，称为局部重构OFP。该结构是一种类似于FP-tree［7］的树结构，主要思想是按频繁递减的项目顺序定期重构树，通过反复重构，使重构树具有尽可能多的前缀共享，提供更好的压缩性能。与此同时，笔者从唯一标号图的连通频繁子图的分析入手，对包含结构信息的数据进行初步分析，将原先对单个项的频繁模式［8］生成工作扩展到双项对的领域上。由于在建树时还临时保留生成只包含一个点的频繁图集的标号顶点表，笔者引入了一种基于Hash散列表［9］的数据结构，用于辅助存储频繁项集［10-11］和唯一标号图，以节省局部重构树构造的时间和提高算法执行效率。

1 SFP算法

文献［12］提出了一种基于 FP-Growth的SFP算法，算法的工作分为两步:构建SFP树和从SFP树中获取频繁连通图。……