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

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

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

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