基于Top-k子圖模式匹配的海量數(shù)據(jù)挖掘算法的研究.pdf

1、分類號——UDC密級學校代碼劣海程歹大穿學位論文10497題目基壬墜p：墾壬圖模式匹配的漁量數(shù)握揎握箕法的研究英文ResearchonBigDataMiningAlgorithmBasedonTopk題目S迪g!箜hP煎星坐叢叢魚h也g研究生姓名何健指導教師姓名—』王jL職稱—j虹』受一學位—砸—士一430070申請學位級別砸士學科專業(yè)名稱通信皇信息丕統(tǒng)論文提交日期2Q!三笙三且論文答辯日期2Q!三生3且學位授予單位武這理王太堂學位授予

2、日期答辯委員會主席劉基教授評閱人劉基數(shù)授奎左斂教授2013年3月武漢理工大學碩士學位論文摘要在互聯(lián)網(wǎng)行業(yè)中隨著大數(shù)據(jù)時代的提前到來，一系列專門針對海量數(shù)據(jù)挖掘的新興且有效的信息提取技術開始引起科研人員的普遍關注與研究。但如今所產(chǎn)生的數(shù)據(jù)信息量逐年呈現(xiàn)出爆炸式增長的現(xiàn)象，數(shù)據(jù)在量變上除了呈現(xiàn)變大的趨勢之外，同時也伴隨著質的變化；然而傳統(tǒng)的數(shù)據(jù)挖掘方法在很大程度上都是基于關系型數(shù)據(jù)庫的基礎上開發(fā)的，因此在一定程度上難以勝任數(shù)據(jù)類型更加多樣化

3、且數(shù)據(jù)結構關系更加復雜化等情況，需結合圖查詢、圖遍歷、圖同構等圖論方法，將圖挖掘技術應用于海量數(shù)據(jù)的建模與挖掘操作過程當中，主要的應用領域包括圖書管理系統(tǒng)(如圖書資源檢索)、社交網(wǎng)絡(如人物關系匹配)、生物信息工程(如PPI、基因工程)等。本文提出的Topk子圖模式匹配(GPM)算法屬于圖數(shù)據(jù)挖掘當中一項典型的海量數(shù)據(jù)挖掘技術，基于圖論中的圖同構原理而提出的一種專門針對附帶標簽屬性的單原數(shù)據(jù)圖(有向或無向均適用)的圖挖掘算法，即從海量原

4、數(shù)據(jù)圖當中匹配出同時滿足查詢圖標簽條件與結構條件(基于路徑)的大量匹配結果來，適用的主要數(shù)據(jù)類型為RDF圖數(shù)據(jù)。作者的主要研究工作如下。(1)介紹了關于海量圖數(shù)據(jù)挖掘中圖模式匹配的一些基本概念與相關算法，其中重點介紹了比較具有參考對比價值的Topk子圖模式匹配連接算法。(2)在論文中本人提出了一種高效且通用的Topk子圖模式匹配方案，在適用性方面該方案對于各種帶環(huán)或不帶環(huán)復雜結構的連通查詢圖均能得到正確的Topk匹配結果；其中對于帶環(huán)結

5、構的查詢圖匹配方案是通過生成樹代價預估匹配方案來選取最優(yōu)生成樹，并將其作為查詢子樹來拓展得到匹配結果的。(3)在算法性能測試階段，采用的RDF圖數(shù)據(jù)來源于DBLP的真實實驗數(shù)據(jù)，本文提出的匹配方案基于該圖數(shù)據(jù)不僅準確地得到了Topk匹配結果，同時也驗證了通過生成樹代價預估匹配方案來選取最優(yōu)生成樹進行拓展匹配的可行性；其次通過與已有的Top—kGPM連接算法在時間與空間性能上進行綜合對比，測試結果表明在消耗一定內(nèi)存空間的基礎之上其時間性能