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

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

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

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