基于雙索引的Top-k子圖查詢算法研究.pdf

1、科學技術的飛速發(fā)展和互聯(lián)網(wǎng)的廣泛應用帶來了信息數(shù)據(jù)的爆炸式增長。為了在大量的數(shù)據(jù)中發(fā)現(xiàn)有用的信息和資源，數(shù)據(jù)挖掘技術應運而生。作為數(shù)據(jù)模式中重要數(shù)據(jù)結構——圖，被應用在方方面面來表達對象之間的復雜關系。圖查詢問題作為數(shù)據(jù)發(fā)現(xiàn)中的關鍵問題，被人們廣泛研究。Top-k子圖查詢問題是子圖查詢技術中應用較為廣泛問題之一。其被應用在知識圖譜、社交網(wǎng)絡等多個方向。
　　在本文中提出了一種基于雙索引的Top-k子圖查詢算法，該算法主要適用于帶標

2、簽的無向的異構網(wǎng)絡加權圖和異構無權查詢圖，即從異構網(wǎng)絡原數(shù)據(jù)大圖當中找出同時滿足查詢圖結構與標簽類別兩個條件的匹配結果。該Top-k子圖查詢算法在對大圖進行檢索中有明顯的速度優(yōu)勢。
　　首先，敘述了關于數(shù)據(jù)挖掘中圖查詢問題的一些相關概念，并對其研究現(xiàn)狀及發(fā)展和相關算法進行了簡要介紹，并分析了其中的優(yōu)缺點。
　　其次，在離線階段提出了對大圖構建雙索引的概念，即圖拓撲索引和最大元路徑權重(MMW)索引兩種。它們總結了網(wǎng)絡的拓撲結

3、構，并提供了最大元路徑權重的上限。同時，還建立了大圖的排序邊列表，由此可以在執(zhí)行子圖匹配算法的同時進行Top-k排序，以便于在有效解決大圖上最具興趣度的子圖查詢問題的同時對圖查詢階段的查詢結果進行排序比較。
　　再次，在線查詢階段，提出了以索引為基礎來計算更緊密的興趣度上界分數(shù)的方法。在查詢匹配的過程中，首先根據(jù)拓撲索引對查詢節(jié)點的候選匹配進行剪枝，然后按照從頂?shù)降椎捻樞騺肀闅v排序邊列表。在遍歷過程中，生成大小為1的候選匹配，采用