基于集群環(huán)境的并行頻繁子圖挖掘算法PG-Miner研究.pdf

1、從大型數(shù)據(jù)庫中挖掘頻繁模式是數(shù)據(jù)挖掘研究的一類基本問題，也是該領域最具挑戰(zhàn)性的一個研究熱點。其中頻繁子圖挖掘旨在解決結構化模式挖掘問題，諸如化學，生物學，WWW應用等領域的關聯(lián)性問題。由于實際應用中具有數(shù)據(jù)規(guī)模大，抽象出的圖結構復雜等特性使得高性能的子圖挖掘算法一直是該領域研究中的一個難點。本文首先提出了并行頻繁項集挖掘算法HPFP-Miner，并以此為基礎，提出一個高效的并行頻繁子圖挖掘算法PG-Miner。論文主要內容包括：

2、　　 1、并行頻繁項集挖掘算法HPFP-Miner
　　 HPFP-Miner為了能夠在并行處理中生成完備且不冗余的結果集提出了兩個數(shù)據(jù)結構HPFP樹和HPFP-Forest來壓縮存儲頻繁項集信息，與FP樹的根為“null”不同的是，每一顆HPFP樹都獨立完整的表述了當前數(shù)據(jù)庫中以其根節(jié)點為前綴的模式，HPFP樹中反向表示父節(jié)點到子節(jié)點的指針。同時，所有HPFP樹通過指針鏈接形成HPFP-Forest，到執(zhí)行時再由主節(jié)點根據(jù)從

3、節(jié)點的多少向各處理節(jié)點分發(fā)HPFP樹，這使得算法具有更高的可擴展性，并且進一步也容易控制各處理節(jié)點的負載。
　　 2、并行頻繁子圖算法PG-Miner設計與實現(xiàn)
　　 在這部分，我們提出一種新的并行頻繁子圖挖掘算法PG-Miner。該算法以盡可能大的并行粒度將頻繁子圖挖掘算法中時間復雜度最高的子圖同構判斷過程分發(fā)到多臺處理器上并行處理，使得算法的執(zhí)行時間隨著處理節(jié)點的線性增加而線性減少。該算法的主要策略是，首先將整個挖掘