近年來,隨著圖數(shù)據(jù)規(guī)模在各個應(yīng)用領(lǐng)域的飛速增長,圖模式查詢引起了越來越廣泛的關(guān)注。常見的圖數(shù)據(jù)分為兩種,第一種是大規(guī)模圖數(shù)據(jù),例如社交網(wǎng)絡(luò);第二種是海量圖數(shù)據(jù)庫,往往由大量規(guī)模較小的數(shù)據(jù)圖組成,例如化學(xué)分子庫。在本論文中,我們主要探索這兩種不同數(shù)據(jù)庫類型上的基礎(chǔ)的圖模式查詢問題。在查閱了大量的已有研究工作之后,我們總結(jié)了幾個基礎(chǔ)且廣泛應(yīng)用的圖查詢問題,并且提出了相應(yīng)的有效解法,提高了圖模式查詢的效率和可擴(kuò)展性。本文的主要貢獻(xiàn)總結(jié)如下:1.大規(guī)模圖上的最大完全二分圖模式查詢。最大完全二分圖問題,簡稱為MEB問題,在大規(guī)模圖數(shù)據(jù)庫中有著廣泛的應(yīng)用場景,例如,風(fēng)險控制、機(jī)器學(xué)習(xí)、計算生物學(xué)等。給定一個二分圖G,G由兩個不相交的點集U和V組成,完全二分圖C=(L∪R)是G中的一個子圖,其中L?U,R?V,且滿足L中所有的點和R中所有的點之間都有邊。最大(邊)完全二分圖即G上邊數(shù)量最多的完全二分圖。MEB問題是一個NP完全問題,在大規(guī)模二分圖上,現(xiàn)有的方法缺乏高效性和可擴(kuò)展性。因此,我們提出了一種分層模型,將MEB問題分成多個子問題,并且通過在子問題中不斷更新最大完全二分圖的方式得到最后結(jié)果。在子問題中,我們設(shè)定了嚴(yán)格的完全二分圖點集大小條件,以此來保證生成的完全二分圖規(guī)模比當(dāng)前已有的最大完全二分圖規(guī)模更大,從而避免了不必要的計算。我們引進(jìn)了兩種高效的剪枝策略,根據(jù)點集大小條件壓縮原數(shù)據(jù)圖,從而極大的減少了搜索空間。我們進(jìn)一步提出了貪心的完全二分圖初始化算法,在初始化階段盡可能找到大規(guī)模的完全二分圖,為后續(xù)的計算和子問題中的點集大小條件提供更嚴(yán)格的范圍界限,以提高搜索效率。我們在大規(guī)模真實數(shù)據(jù)圖中做了大量的實驗,實驗結(jié)果顯示,我們提出的分層算法比現(xiàn)有最好方法快幾個數(shù)量級,同時,據(jù)我們所知,該分層算法也是當(dāng)前唯一可以在十億級別邊的大規(guī)模圖上計算最大完全二分圖的方法。2.海量圖數(shù)據(jù)庫中的超圖模式查詢。超圖模式查詢是海量圖數(shù)據(jù)庫中的基礎(chǔ)問題,在現(xiàn)實中有眾多的應(yīng)用場景。給定圖數(shù)據(jù)庫和查詢圖,超圖查詢在圖數(shù)據(jù)庫中查找所有包含在查詢圖中的結(jié)果�，F(xiàn)有的方法大多遵循剪枝-驗證的框架,但是在較大規(guī)模的數(shù)據(jù)圖和查詢圖中,現(xiàn)有方法可擴(kuò)展性較差。因此,我們提出了新的索引和查詢方法,來處理超圖模式查詢問題。在索引階段,我們直接根據(jù)數(shù)據(jù)圖結(jié)構(gòu)得到特征圖,而不依賴于開銷昂貴的頻繁子圖挖掘方法。在選擇特征圖的過程中,我們充分考慮了特征圖的剪枝能力和計算共享能力,得到了各種規(guī)模的特征圖組成的特征樹索引。在超圖模式查詢過程中,我們根據(jù)查詢圖來衡量不同特征圖的剪枝能力和計算共享能力,動態(tài)的選擇最優(yōu)特征圖優(yōu)先進(jìn)行對比。我們還探索了兩種優(yōu)化策略,包括輕量的圖壓縮策略以及基于優(yōu)先包含結(jié)果的策略,來進(jìn)一步提高算法效率。最后,我們在兩個真實數(shù)據(jù)集中進(jìn)行了大量實驗,實驗結(jié)果表明,我們的方法具有高可擴(kuò)展性。3.動態(tài)圖數(shù)據(jù)庫中的近似超圖模式查詢。海量圖數(shù)據(jù)庫由許多的數(shù)據(jù)圖組成,為了在海量圖數(shù)據(jù)庫中高效的進(jìn)行超圖模式查詢,現(xiàn)有方法往往是基于索引技術(shù)。然而,其中大部分索引算法都不適用于動態(tài)圖數(shù)據(jù)庫。在動態(tài)圖數(shù)據(jù)庫中,往往有頻繁的圖插入、刪除以及修改操作。用戶可以在更新后的圖數(shù)據(jù)庫上重建索引,但這樣的方法非常耗費時間。另一方面,在動態(tài)圖數(shù)據(jù)庫中,隨著時間推移,數(shù)據(jù)規(guī)模越來越大,精確的超圖模式查詢方法將面臨效率問題。因此,基于這兩方面的觀察,我們提出了動態(tài)圖數(shù)據(jù)庫中的近似超圖模式查詢算法。在索引階段,我們提出了在動態(tài)圖數(shù)據(jù)庫中增量更新圖索引的方法。在圖索引更新過程中,我們充分考慮了特征圖的剪枝能力和計算共享能力。在查詢階段,我們提出了超圖模式查詢的近似算法,在大規(guī)模的數(shù)據(jù)圖和查詢圖上極大的降低了計算開銷,并且保證了高質(zhì)量的查詢結(jié)果。最后,我們在兩個真實數(shù)據(jù)集中進(jìn)行了大量實驗,實驗結(jié)果顯示,我們的方法具有高效性和高可擴(kuò)展性。
【學(xué)位單位】：華東師范大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2018
【中圖分類】：TP311.13
【部分圖文】：

圖 3.3: LMEB算法的 (2,2)-MEB 求解例如，給定一個二分圖 G（如圖3.1(a)），以及 (2,2) 的點集限制條件，圖3.3中示例了 LMEB算法求解 (2,2)-MEB 的過程。首先，假設(shè)我們初始化了一個完全二分圖 Cmax= (L ∪ R)，其中 L = {u2, u3, u4, u5, u6}，R = {v2, v3, v5}，40

表 4.3: 參數(shù)設(shè)置參數(shù) 范圍 默認(rèn)值graph database size [3000,80000] 3000avg. node # of data-graph [10,90] 50avg. node # of query-graph [60,240] 100data-graph density group DG1, DG2, DG3, DG4, DG5–query-graph density group DQ1, DQ2, DQ3, DQ4, DQ5–組查詢圖分別記作 DQ1, DQ2, DQ3, DQ4和 DQ5。4.5.1分 數(shù)和優(yōu)化策略性首先，我們測試了我們在索引和查詢階段提出的對特征圖的打分函數(shù)的有效性。同時，我們也對比了基礎(chǔ)的算法版本和有優(yōu)化的算法版本，來查看圖壓縮策略和自適應(yīng)節(jié)點分割策略的有效性。實驗結(jié)果展示在4.4中。
【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 孫勤紅;;支持增量圖數(shù)據(jù)的超圖查詢算法研究[J];四川理工學(xué)院學(xué)報(自然科學(xué)版);2015年03期

本文編號：2867667