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

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

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

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