基于索引的子圖查詢技術(shù)研究進(jìn)展

施煒杰 董一鴻 王雄 潘劍飛

摘 要：圖作為表示實(shí)體間的數(shù)據(jù)結(jié)構(gòu)，在社區(qū)發(fā)現(xiàn)、生物化學(xué)分析、社會(huì)安全分析等數(shù)據(jù)關(guān)聯(lián)性要求較高的領(lǐng)域有著廣泛的應(yīng)用。對(duì)于大規(guī)模數(shù)據(jù)下進(jìn)行實(shí)時(shí)的圖查詢問(wèn)題，通過(guò)構(gòu)建合適的索引可以有效降低查詢響應(yīng)時(shí)間，提高查詢精確度。首先介紹基于索引的子圖查詢算法的基本結(jié)構(gòu);然后按索引的構(gòu)建方式將主流算法分為基于枚舉的方法和基于頻繁模式挖掘的方法兩大類，分別從索引特征、索引結(jié)構(gòu)、應(yīng)用數(shù)據(jù)集等方面進(jìn)行介紹和分析;最后對(duì)基于索引的子圖查詢算法面臨的主要問(wèn)題進(jìn)行總結(jié)和分析，闡述了最新的分布式系統(tǒng)下圖查詢技術(shù)，并對(duì)未來(lái)趨勢(shì)進(jìn)行展望。

關(guān)鍵詞：子圖同構(gòu);索引;子圖查詢;頻繁模式

中圖分類號(hào)： TP391

文獻(xiàn)標(biāo)志碼：A

Abstract： As a type of data structure representing entities， graphs are widely used in fields that have high requirements on data relevance， such as community data discovery， biochemical analysis and social security analysis. Focusing on the issue of real-time graph query operation under large-scale data， building a suitable index can effectively reduce query response time and improve query accuracy. The basic structure of index-based subgraph query algorithm was firstly introduced and then state-of-the-art algorithms were divided into two categories by construction method of index： enumeration construction and frequent pattern mining construction. Then these algorithms were introduced and analyzed from three aspects： index features， index structures and application datasets. Finally， main problems toward index-based subgraph query algorithm were summarized and analyzed， the latest query technology based on the distributed system was briefly described， and the future trend was forecasted.

Key words： subgraph isomorphism; index; subgraph query; frequent pattern

0 引言

隨著信息技術(shù)的飛速發(fā)展，圖結(jié)構(gòu)用于展示實(shí)體與實(shí)體之間的關(guān)系，在生物工程領(lǐng)域[1-2]、社交網(wǎng)絡(luò)[3]等領(lǐng)域具有廣泛的應(yīng)用。圖查詢作為圖數(shù)據(jù)處理的基本操作存在于各類應(yīng)用：在社會(huì)安全分析[4]中，將犯罪團(tuán)伙的作案關(guān)系模擬成使用圖結(jié)構(gòu)表示的關(guān)系模型，應(yīng)用社區(qū)網(wǎng)絡(luò)分析，通過(guò)子圖查詢可以有效識(shí)別出高危團(tuán)伙;人才推薦系統(tǒng)[5]中，依托于社交網(wǎng)絡(luò)通過(guò)將團(tuán)隊(duì)間的協(xié)作關(guān)系構(gòu)建成圖模型，通過(guò)與需求相應(yīng)的子圖結(jié)構(gòu)進(jìn)行查詢匹配為招聘公司提供個(gè)性化的人才推薦方案;生物化學(xué)領(lǐng)域的分析研究[6]中，將各類蛋白質(zhì)或有機(jī)高分子構(gòu)建為圖模型，能為專業(yè)人員提供更高效、精確的分析工具。

圖查詢過(guò)程主要以模式匹配為主，面臨著子圖同構(gòu)問(wèn)題，該問(wèn)題已被證明是NP-hard（Non-deterministic Polynomial-time hard）問(wèn)題[7]，存在大量的計(jì)算;其次當(dāng)圖數(shù)據(jù)過(guò)大時(shí)，如果每次查詢都對(duì)數(shù)據(jù)集作一次遍歷開(kāi)銷過(guò)大。通過(guò)構(gòu)建索引能有效降低查詢過(guò)程中的計(jì)算量。

索引查詢主要可以分為過(guò)濾和驗(yàn)證兩部分[8]：過(guò)濾是通過(guò)索引特征對(duì)數(shù)據(jù)集進(jìn)行剪枝操作，并返回與查詢圖相似的候選集;驗(yàn)證是通過(guò)子圖同構(gòu)來(lái)對(duì)候選集進(jìn)行驗(yàn)證最終返回查詢的答案集。

因此圖索引面臨的主要有以下幾個(gè)問(wèn)題：1）構(gòu)建索引的整體時(shí)間;2）查詢返回答案集所需時(shí)間，其中包括過(guò)濾操作的計(jì)算時(shí)間和驗(yàn)證答案集的計(jì)算時(shí)間;3）索引大小，尤其在大圖下索引能否放入內(nèi)存;4）索引表的擴(kuò)展性等。

1 基本概念

2 基于索引的圖查詢技術(shù)

傳統(tǒng)的圖查詢操作，通過(guò)遍歷數(shù)據(jù)集依次與查詢圖進(jìn)行子圖同構(gòu)測(cè)試。由于子圖同構(gòu)本身就是NP-hard問(wèn)題，加上龐大的數(shù)據(jù)量，其時(shí)空開(kāi)銷過(guò)大，不能滿足實(shí)際的生產(chǎn)要求;而通過(guò)構(gòu)建索引表能有效過(guò)濾與查詢圖不相關(guān)的圖，減少子圖同構(gòu)的測(cè)試次數(shù)，大幅度降低查詢時(shí)間。索引查詢的整體時(shí)間復(fù)雜度[9]可以用式（1）來(lái)表示：

其中：Tresponse為一次查詢返回答案集的時(shí)間，Tsearch為索引時(shí)間，TisSubG為子圖同構(gòu)時(shí)間，TI/O為算法在硬盤中對(duì)候選集Cq作I/O操作的時(shí)間。子圖同構(gòu)是NP-hard問(wèn)題，計(jì)算時(shí)間復(fù)雜度較高，所以Cq·TisSubG占據(jù)Tresponse中很大一部分時(shí)間，因此索引設(shè)計(jì)需求主要集中在優(yōu)化候選集的大小，減少驗(yàn)證階段子圖同構(gòu)的計(jì)算次數(shù)，提高查詢性能。

2.1 查詢算法的基本結(jié)構(gòu)

近年來(lái)面對(duì)圖查詢中的各類問(wèn)題，相關(guān)學(xué)者提出了各種解決方案?；诼窂教卣鞯乃饕樵兯惴?，適用于快速建表，索引大小的可控性強(qiáng)，適用于分布式環(huán)境下的索引搭建，但查詢結(jié)果的精確度較低，結(jié)果存在大量的假陽(yáng)（False Positive， FP）例;基于圖或者樹(shù)特征的索引查詢算法，特征具有良好的剪枝效果，查詢響應(yīng)快，適用于需要快速查詢，且結(jié)果精確度較高，主要通過(guò)頻繁模式挖掘，但索引構(gòu)件開(kāi)銷大，并且空間消耗不可控，因此也有通過(guò)迭代挖掘[10]的方式取代一次建表的，在一定的容錯(cuò)情況下，使目標(biāo)函數(shù)不斷逼近實(shí)際值，來(lái)降低索引構(gòu)建過(guò)程中的時(shí)空消耗。通常圖索引算法分為三個(gè)步驟[11]：1）索引構(gòu)建;2）查詢;3）答案驗(yàn)證。

2.1.1 索引構(gòu)建

在索引構(gòu)建階段，算法主要從數(shù)據(jù)集中提取特征，并通過(guò)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)構(gòu)建索引表，主要面臨兩個(gè)問(wèn)題[12]：1）索引特征的挖掘速度;2）索引特征是否具有良好的剪枝性。兩者之間的關(guān)系成反比。常用的索引特征主要有：1）路徑[13-18];2）樹(shù)[19-21];3）圖[22-24];4）多特征的混合結(jié)構(gòu)[25-29]。特征的獲取方式有：1）枚舉獲取數(shù)據(jù)中的所用特征;2）頻繁模式挖掘獲取數(shù)據(jù)集中的索引特征。

2.1.2 查詢

查詢階段也稱之為過(guò)濾階段。首先將查詢圖序列化與索引表中特征進(jìn)行匹配：如果完全匹配，則返回相應(yīng)特征的ID;否則，將查詢圖分解成小片段系列化后再與索引表中特征進(jìn)行匹配，產(chǎn)生一組可能包含查詢圖的候選集。在大多數(shù)算法中，候選集為查詢圖包含的各個(gè)片段的映射集的交集。對(duì)于存儲(chǔ)位置信息的索引算法，可以迅速定位片段在索引表中的位置，實(shí)現(xiàn)快速查詢。

2.1.3 答案驗(yàn)證

在查詢階段返回的候選集中可能存在與查詢圖不完全匹配的圖，因此對(duì)候選集作驗(yàn)證操作以提高查詢結(jié)果的質(zhì)量是十分必要的。該過(guò)程主要是將候選集中的圖與查詢圖進(jìn)行子圖同構(gòu)測(cè)試，相應(yīng)的匹配算法有Ullmanm[29]、VF2[30]等，現(xiàn)今的索引算法中主要使用VF2算法進(jìn)行子圖同構(gòu)檢測(cè)，也有部分算法使用自定的算法進(jìn)行檢測(cè)。

針對(duì)上述三個(gè)步驟中，各類算法間的差異主要區(qū)別于索引構(gòu)建過(guò)程的構(gòu)建方式，查詢過(guò)程都遵循過(guò)濾+驗(yàn)證原則，因此下文從索引的構(gòu)建方式出發(fā)，將現(xiàn)今主流的圖索引算法分為基于枚舉和頻繁模式挖掘兩類，作基本的闡述。

2.2 基于枚舉的索引構(gòu)建方法

基于枚舉的索引構(gòu)建沒(méi)有針對(duì)某種特定標(biāo)準(zhǔn)篩選索引特征，而是索引了圖集的所有結(jié)構(gòu)。索引整體可控性強(qiáng)，構(gòu)建快捷。索引特征主要以定長(zhǎng)路徑為主，也有部分算法針對(duì)圖中的簡(jiǎn)單環(huán)和樹(shù)結(jié)構(gòu)進(jìn)行枚舉。算法遵循過(guò)濾+驗(yàn)證原則，優(yōu)化主要集中在驗(yàn)證階段。

2.2.1 gCode

gCode[13]基于譜圖理論提出了針對(duì)頂點(diǎn)的編碼方式，通過(guò)組合所有頂點(diǎn)編碼來(lái)為每個(gè)圖生成一個(gè)圖編碼。首先通過(guò)一個(gè)三元組〈L，N，top（S）〉作為頂點(diǎn)的辨識(shí)標(biāo)簽，其中L為頂點(diǎn)v自身的編碼，N為頂點(diǎn)v的鄰居節(jié)點(diǎn)的編碼，top（S）是根據(jù)對(duì)以頂點(diǎn)v為根節(jié)點(diǎn)構(gòu)建的路徑樹(shù)所有轉(zhuǎn)換的矩陣取的前S個(gè)特征值，然后將頂點(diǎn)編碼組合形成圖編碼，如圖2為圖1中圖f13的gCode編碼示意圖。

在查詢過(guò)程中，gCode首先將查詢圖按照上述的方式編碼化，然后根據(jù)匹配頂點(diǎn)的辨識(shí)標(biāo)簽來(lái)對(duì)結(jié)果作剪枝處理，最后使用VF2算法對(duì)返回的候選集答案作剪枝操作。

2.2.2 GraphGrepSX

GraphGrepSX[14]適用于無(wú)向圖，使用深度優(yōu)先遍歷（Depth-First-Search， DFS）算法枚舉所有長(zhǎng)度為k的路徑，并存儲(chǔ)在后綴樹(shù)中。樹(shù)中每個(gè)節(jié)點(diǎn)存儲(chǔ)圖的id列表以及出現(xiàn)在每個(gè)圖中對(duì)應(yīng)路徑的次數(shù)。對(duì)查詢圖進(jìn)行類似的分解與索引特征比較，剪枝掉與查詢圖不匹配的分支，根據(jù)節(jié)點(diǎn)中標(biāo)簽的出現(xiàn)頻率進(jìn)一步過(guò)濾，產(chǎn)生候選集，然后使用VF2進(jìn)行驗(yàn)證得到答案集。圖3為GraphGrepSX[14]對(duì)圖1中f11深度遍歷后形成的后綴樹(shù)。

與GraphGrepSX[14]類似，Grapes[15]也是通過(guò)DFS形式枚舉所有長(zhǎng)度為k的路徑，不同的是Grapes[15]是通過(guò)每個(gè)路徑的起始節(jié)點(diǎn)id以及該路徑在各個(gè)圖中的計(jì)數(shù)信息維護(hù)位置信息;同時(shí)，Grapes[15]支持索引和查詢處理過(guò)程的并行執(zhí)行。索引中通過(guò)將節(jié)點(diǎn)巧妙地分配給線程完成，以便每個(gè)線程在不需要與其他線程同步信息同步的情況下完成計(jì)算任務(wù)。在查詢過(guò)程中，查詢圖也經(jīng)歷了相同并行化的路徑枚舉和樹(shù)結(jié)構(gòu)處理，然后比較查詢樹(shù)與索引樹(shù)，刪除不匹配部分，通過(guò)保留的位置信息進(jìn)一步過(guò)濾不必要的子圖，最后進(jìn)行子圖同構(gòu)測(cè)試得出答案集。此類索引適用于小量數(shù)據(jù)集。

2.2.3 Gstring

GString[16]算法主要針對(duì)生物化學(xué)類數(shù)據(jù)進(jìn)行建模分析。不同于上述幾個(gè)算法，GString更加注重于將圖的結(jié)構(gòu)語(yǔ)意嵌入至對(duì)圖的簡(jiǎn)約表達(dá)中。該算法面向化學(xué)數(shù)據(jù)庫(kù)的應(yīng)用，提出了基于線型路徑、星型以及環(huán)型結(jié)構(gòu)的特征提取方法。給定一個(gè)圖，依次提取所有的環(huán)結(jié)構(gòu)、線型路徑特征和星型特征，得到圖的簡(jiǎn)約表示，最后通過(guò)DFS獲取簡(jiǎn)約圖的后綴樹(shù)表示，作為查詢索引。以類似的方式對(duì)查詢圖編碼，通過(guò)后綴樹(shù)得到查詢候選集，最后使用VF2同構(gòu)算法返回答案集。GString適用于小數(shù)據(jù)集的情況，當(dāng)圖集或查詢圖較大時(shí)，查詢效率不高，主要用于生物高分子中化合物的分解分析。

2.2.4 CT-index

CT-index（index based on Cycle and Tree）[25]考慮到環(huán)結(jié)構(gòu)對(duì)圖結(jié)構(gòu)的表達(dá)能力，將路徑、樹(shù)和環(huán)圖作為索引構(gòu)建的索引特征，依次枚舉出數(shù)據(jù)圖中所有的路徑特征、樹(shù)特征和環(huán)特征，并將這些特征組合規(guī)范化之后進(jìn)行哈希編碼，對(duì)每個(gè)圖產(chǎn)生一個(gè)固定長(zhǎng)度的fingerprint，針對(duì)樹(shù)特征的規(guī)范化將樹(shù)的重心節(jié)點(diǎn)確定為樹(shù)的根節(jié)點(diǎn)。在查詢階段，同樣將查詢圖規(guī)范化之后進(jìn)行哈希編碼的到一個(gè)固定長(zhǎng)度的fingerprint;然后通過(guò)按位與操作將其與數(shù)據(jù)集中所有圖的fingerprint進(jìn)行比較，產(chǎn)生候選集;再利用改進(jìn)的VF2算法對(duì)候選集作子圖同構(gòu)測(cè)試，得出答案集。

2.2.5 小結(jié)

基于枚舉方式構(gòu)建的索引如gCode、GraphGrepSX等結(jié)構(gòu)簡(jiǎn)單，構(gòu)建快捷，因此對(duì)索引結(jié)構(gòu)的維護(hù)有著明顯的優(yōu)勢(shì)，能適應(yīng)數(shù)據(jù)頻繁更新的情況，但是由于特征結(jié)構(gòu)簡(jiǎn)單，過(guò)濾性能較差。在圖1中，進(jìn)行簡(jiǎn)單的查詢操作，f14為查詢圖唯一的返回答案，但f8和f15不能通過(guò)路徑特征的剪枝能力直接在索引階段被過(guò)濾掉，因此查詢返回的候選集較大。驗(yàn)證階段是算法主要的瓶頸，類似的有GString、CT-index在枚舉階段通過(guò)對(duì)特定的樹(shù)結(jié)構(gòu)和環(huán)結(jié)構(gòu)進(jìn)行遍歷，這也相應(yīng)地增加了索引的構(gòu)建時(shí)間。綜上此類算法構(gòu)建快捷，維護(hù)便捷，但查詢的整體耗時(shí)與數(shù)據(jù)量不成線性關(guān)系，可擴(kuò)展性較差，不適用于密度較高、結(jié)構(gòu)復(fù)雜的圖數(shù)據(jù)。

2.3 基于頻繁模式挖掘的索引構(gòu)建方法

針對(duì)基于枚舉構(gòu)建的圖索引算法中過(guò)濾性能差、驗(yàn)證計(jì)算量大等缺點(diǎn)，基于頻繁模式挖掘方式構(gòu)建的圖索引算法從索引特征的結(jié)構(gòu)出發(fā)很好地解決了上述查詢過(guò)程中的幾個(gè)問(wèn)題。算法主要思想是在頻繁模式挖掘的基礎(chǔ)上通過(guò)判別函數(shù)對(duì)頻繁模型進(jìn)行特征選擇，將符合判別條件的模型作為索引特征保存在給定的索引結(jié)構(gòu)中。在頻繁模式挖掘中，特征的支持度是其映射集在整個(gè)數(shù)據(jù)集中的占比。如果特征的支持度高于閾值，該特征被認(rèn)為是頻繁的。特征的區(qū)分比是特征與其子特征之間修剪能力的度量。所有基于頻繁模式挖掘的索引構(gòu)建算法，基本思想都是為特征的區(qū)分比提供不同的度量方式。在索引構(gòu)建中對(duì)每個(gè)特征進(jìn)行序列化操作，將其映射集存入索引表中。部分索引構(gòu)建算法保留特征位置信息，如路徑特征的第一節(jié)點(diǎn)的IDid此處的ID，是否應(yīng)該改為小寫id，以便與2.2.2中的id書寫保持一致？或者全部改為大寫ID？請(qǐng)明確（用于定位路徑的開(kāi)始節(jié)點(diǎn)）、樹(shù)特征的重心節(jié)點(diǎn)的IDid（用于標(biāo)準(zhǔn)化樹(shù)型特征）等，最后將所有特征存儲(chǔ)在算法給定的數(shù)據(jù)結(jié)構(gòu)，如哈希表、前綴樹(shù)或者圖點(diǎn)陣中。

2.3.1 gIndex

gIndex[9]針對(duì)頻繁模式挖掘中支持度的選擇提出了根據(jù)子圖大小計(jì)算支持度的遞增函數(shù)，主要思想是采取增量函數(shù)計(jì)算子圖的支持度，并設(shè)定判別率來(lái)判斷一個(gè)特征是否冗余，索引非冗余特征。具體計(jì)算公式如下：

其中： fψix， fψiF，F(xiàn)為圖集D的頻繁子圖集，ψ（l）為圖size-支持度遞增函數(shù)，γmin為用戶給定的最小冗余度，Dfψi為子圖x下所有的頻繁子圖集。當(dāng)子圖x同時(shí)滿足式（2）、（3）時(shí)，子圖x則為非冗余的頻繁子圖，并將這些挖掘得到的索引特征使用前綴樹(shù)的形式通過(guò)哈希表存儲(chǔ)。存儲(chǔ)時(shí)不保留位置信息，只存儲(chǔ)每個(gè)特征的對(duì)應(yīng)的映射集。在查詢處理期間，枚舉查詢圖的所有圖結(jié)構(gòu)片段，直到最大片段，確保較小片段在較大片段之前被枚舉。如果一個(gè)片段沒(méi)有出現(xiàn)在索引中，則不會(huì)產(chǎn)生該片段的超圖。通過(guò)每個(gè)擴(kuò)展路徑的最大片段的圖ID列表的交集，得到查詢的候選集。最后使用VF2算法比較查詢圖與所有候選圖進(jìn)行驗(yàn)證。

2.3.2 FG-index

FG-index（index based on Frequent subGraph）[22]提出δ-TCFG（δ-Tolerance Closed Frequent subGraph）特征標(biāo)準(zhǔn)用于衡量一個(gè)頻繁子圖是否冗余，提高索引對(duì)內(nèi)存的利用率。δ-TCFG特征具體判定條件如下：

其中δ∈[0，1]，g為頻繁子圖，g為g′為子圖，當(dāng)且僅當(dāng)g和g′滿足式（4），且g′不為頻繁子圖時(shí)g為δ-TCFG特征。針對(duì)δ-TCFG特征建立倒排索引，如圖4所示。

圖4的索引結(jié)構(gòu)保留索引特征位置信息實(shí)現(xiàn)快速查詢，使用IDA（m，n，e）三元組結(jié)構(gòu)定位GraphArray中的fi在EdgeArray中的位置，其中n=size（g），m=count（e，g），GraphArray為存儲(chǔ)δ-TCFG特征的哈希表，EdgeArray存儲(chǔ)δ-TCFG特征各邊的哈希表;同時(shí)索引將δ-TCFG特征存儲(chǔ)于內(nèi)存，其余頻繁模式存儲(chǔ)在硬盤中以提高索引表的覆蓋率。FG-index通過(guò)對(duì)δ-TCFG對(duì)頻繁子圖進(jìn)行了細(xì)致的篩選，能直接返回精確的答案集，省卻了索引驗(yàn)證的計(jì)算。

2.3.3 tree+Δ

tree+Δ（tree & delta）[21]以頻繁樹(shù)作為基本索引特征，再根據(jù)樹(shù)特征按需選擇少量的判別圖Δ以提升索引的剪枝能力，將挖掘得到的索引特征存儲(chǔ)于哈希表，不存儲(chǔ)位置信息。針對(duì)判別圖Δ的選擇，tree+Δ[21]提出了通過(guò)樹(shù)特征剪枝力的上下邊界近似評(píng)估相應(yīng)圖特征冗余與否的計(jì)算函數(shù)，具體判定函數(shù)如下：

其中：g為g′的子圖，Γ（g）、Γ（g′）分別為g、g′的頻繁子樹(shù)集，ε0為冗余系數(shù)，σ為頻繁模式支持度，σx為模式x的支持度，當(dāng)σΓ（g′）和σΓ（g）同時(shí)滿足式（5）～（8）時(shí)，算法認(rèn)為g′為非冗余特征圖。

在查詢階段，tree+Δ[21]首先枚舉出查詢圖q中所有滿足最大長(zhǎng)度的子集T（q），通過(guò)哈希表求的所有t的映射圖集取交集得到候選集Cq，其中t∈T（q），最后使用VF2算法驗(yàn)證得到答案集。

2.3.4 Lindex

Lindex[23]由Dayu Yuan團(tuán)隊(duì)提出，相比之前的工作如何挖掘出合適的特征，該算法首次將工作重心放在索引表的數(shù)據(jù)結(jié)構(gòu)上。該方法的索引特征是在頻繁子圖集的基礎(chǔ)上挖掘得到，提出了基于倒排構(gòu)建的點(diǎn)陣結(jié)構(gòu)索引，每個(gè)節(jié)點(diǎn)都與一個(gè)〈key，value〉相關(guān)聯(lián)，key代表一個(gè)索引特征，value代表該key映射下圖集中的圖。根據(jù)節(jié)點(diǎn)間的包含關(guān)系構(gòu)建索引表，兩個(gè)節(jié)點(diǎn)之間的邊表示父節(jié)點(diǎn)中的key是子節(jié)點(diǎn)中key的子圖，如圖5所示。

圖5為L(zhǎng)index[23]索引結(jié)構(gòu)示意圖，根節(jié)點(diǎn)sg0為空?qǐng)D（沒(méi)有節(jié)點(diǎn)或邊的圖）。節(jié)點(diǎn)sg0有兩個(gè)孩子節(jié)點(diǎn)，分別是sg1和sg2。父節(jié)點(diǎn)是其子節(jié)點(diǎn)的頻繁度最小的最大子圖。在查詢中通過(guò)索引特征間的包含邏輯進(jìn)行快速查詢，通過(guò)頻繁度最小的最大子圖構(gòu)建整個(gè)索引，提高返回答案集的精度，大幅度降低了整體的查詢時(shí)間;但是由于Lindex[23]要在頻繁模式的基礎(chǔ)上重新構(gòu)建圖見(jiàn)證，所以索引表整體的構(gòu)建時(shí)間遠(yuǎn)遠(yuǎn)大于其他索引，但是當(dāng)面對(duì)海量數(shù)據(jù)集時(shí)，基于頻繁模式挖掘的索引構(gòu)建時(shí)間比較長(zhǎng)，在數(shù)據(jù)集動(dòng)態(tài)更新的情況下，很難保證索引性能的實(shí)時(shí)性。Dayu Yuan團(tuán)隊(duì)首次提出基于迭代挖掘的索引構(gòu)建方法[24]。算法首先通過(guò)較大的支持度完成首次特征挖掘，之后根據(jù)目標(biāo)函數(shù)（見(jiàn)式（9）），迭代更新索引表中的索引特征，并且首次引入對(duì)查詢?nèi)罩镜臄?shù)據(jù)挖掘，通過(guò)將查詢?nèi)罩拘畔⒂谒饕卣飨嘟Y(jié)合，使索引特征更能符合用戶的查詢習(xí)慣。

其中g(shù)ain（p，P0）為索引特征集P0添加特征p之后的索引剪枝力的增益。

針對(duì)索引構(gòu)件該算法采用與Lindex[23]中相同的構(gòu)建方法進(jìn)行索引構(gòu)建。

2.3.5 小結(jié)

本節(jié)主要介紹了現(xiàn)主流的部分算法。gIndex主要針對(duì)頻繁度的選擇問(wèn)題，通過(guò)使用動(dòng)態(tài)增量函數(shù)對(duì)不同size的子圖采取不同的支持度在保持索引覆蓋率的同時(shí)降低內(nèi)存消耗，但當(dāng)面對(duì)萬(wàn)級(jí)的圖集時(shí)算法的空間消耗還是過(guò)大。相應(yīng)FG-index通過(guò)各個(gè)子圖的映射集的大小進(jìn)一步過(guò)濾冗余特征來(lái)減少索引的內(nèi)存消耗。Lindex不同于上述算法設(shè)計(jì)思路，通過(guò)優(yōu)化索引結(jié)構(gòu)，避免算法在驗(yàn)證階段的子圖同構(gòu)計(jì)算，但頻繁模式挖掘本身時(shí)空消耗就很大，因此該類算法不適用于大數(shù)據(jù)量的情況，相應(yīng)的有文獻(xiàn)[24]通過(guò)迭代挖掘的方式和tree+Δ使用樹(shù)特征代替圖特征來(lái)提高前期挖掘的速度，但當(dāng)面對(duì)千萬(wàn)級(jí)圖數(shù)據(jù)時(shí)，此類算法都未能完成索引構(gòu)建。綜上，基于頻繁模式挖掘的索引構(gòu)建算法，索引剪枝力強(qiáng)，查詢結(jié)果精確，支持快速查詢;但索引前期構(gòu)建時(shí)空消耗大，索引結(jié)構(gòu)復(fù)雜，維護(hù)困難，不適用于當(dāng)下大數(shù)據(jù)時(shí)代的數(shù)據(jù)環(huán)境。

2.4 基于索引的子圖查詢算法總結(jié)

本節(jié)主要針對(duì)上述幾類算法進(jìn)行匯總，由于篇幅有限故不再對(duì)算法進(jìn)行一一羅列，表1為部分基于索引的圖查詢算法匯總?；诿杜e構(gòu)建的索引算法中，由于考慮到特征結(jié)構(gòu)對(duì)于枚舉計(jì)算的影響，一般使用路徑特征來(lái)構(gòu)建索引表，但是路徑特征忽略了圖的結(jié)構(gòu)信息，查詢過(guò)程中返回的候選集較大，大幅度增加了驗(yàn)證階段的時(shí)空消耗，相應(yīng)的有CT-index使用路徑、樹(shù)和圖作為索引特征，以提高索引表的過(guò)濾能力，但是也增加索引構(gòu)建的時(shí)空消耗。基于頻繁模式挖掘的索引構(gòu)建方法，主要可以分為圖特征和樹(shù)特征兩類，相比于基于枚舉的索引構(gòu)建算法，基于頻繁模式挖掘的索引構(gòu)建算法在索引構(gòu)建階段的耗時(shí)較大，動(dòng)態(tài)維護(hù)難，但是由于算法基于頻繁模式選擇，所以其索引的內(nèi)存占用和剪枝力要遠(yuǎn)遠(yuǎn)小于前者。

3 分布式下的子圖查詢

當(dāng)面對(duì)海量數(shù)據(jù)集時(shí)，往往將數(shù)據(jù)圖存儲(chǔ)在分布式平臺(tái)中。分布式查詢已經(jīng)在關(guān)系數(shù)據(jù)和XML（EXtensible Markup Language）等方面有了廣泛的研究。針對(duì)分布式平臺(tái)下對(duì)圖模型作挖掘分析面臨這如下幾個(gè)問(wèn)題：1）數(shù)據(jù)圖的存儲(chǔ);2）高效分布式算法的設(shè)計(jì);3）節(jié)點(diǎn)間高效的通信。針對(duì)圖的存儲(chǔ)問(wèn)題，主要有點(diǎn)分割和邊分割兩種策略：前者能降低節(jié)點(diǎn)間的通信開(kāi)銷，但是動(dòng)態(tài)的維護(hù)難度較大;后者的維護(hù)難度較低，但是增加了節(jié)點(diǎn)間的通信開(kāi)銷?，F(xiàn)有的分布式圖數(shù)據(jù)處理系統(tǒng)主要有Pregel和InfiniteGraph等[31]。

3.1 disHHK算法

disHHK（distirbuted Henzinger Henzinger KopkedisHHK有英文全稱嗎？）[32]是由Shuai Ma在2012提出的首個(gè)分布式圖模式匹配算法，同時(shí)提出了針對(duì)分布式算法以相對(duì)計(jì)算時(shí)間、完成時(shí)間以及數(shù)據(jù)傳輸量為主的評(píng)估標(biāo)準(zhǔn)。算法整體可以分為調(diào)度節(jié)點(diǎn)的調(diào)度算法和工作節(jié)點(diǎn)的匹配算法兩個(gè)部分。調(diào)度算法主要為匹配后對(duì)所有結(jié)果進(jìn)行join操作時(shí)提供調(diào)度策略;匹配算法則是直接通過(guò)DFS遍歷枚舉工作節(jié)點(diǎn)中與查詢圖匹配的數(shù)據(jù)圖，其中主要考慮部分匹配和完全匹配兩種情況。算法在查詢過(guò)程中，首先通過(guò)調(diào)度節(jié)點(diǎn)將查詢圖廣播至各個(gè)工作節(jié)點(diǎn)上，各節(jié)點(diǎn)中通過(guò)單機(jī)下的HHK（Henzinger Henzinger KopkeHHK有英文全稱嗎？）匹配算法枚舉出數(shù)據(jù)圖中與查詢圖匹配的映射集，然后將結(jié)果回傳至調(diào)度節(jié)點(diǎn);調(diào)度節(jié)點(diǎn)通過(guò)基于貪心的調(diào)度策略分配各匹配結(jié)果至最優(yōu)的工作節(jié)點(diǎn)進(jìn)行join操作，最后輸出查詢圖的查詢結(jié)果。disHHK算法主要適用于有向圖，由于其在單機(jī)下的匹配策略是通過(guò)DFS遍歷來(lái)枚舉查詢圖的匹配集，所以當(dāng)節(jié)點(diǎn)間數(shù)據(jù)分布不均衡時(shí)，木桶效應(yīng)就比較明顯。

3.2 Stwig算法

Stwig（Sub twig）[33]認(rèn)為由于索引的漸進(jìn)復(fù)雜性，基于索引的查詢算法不能提供穩(wěn)定的性能，因此算法不建立索引，主要依靠?jī)?nèi)存云和大規(guī)模并行計(jì)算完成能在大的單圖（十億節(jié)點(diǎn)）下的子圖查詢。匹配過(guò)程通過(guò)圖的拓?fù)浣Y(jié)構(gòu)的擴(kuò)展來(lái)取代子圖匹配中的join操作。其中算法主要通過(guò)基于采樣的鏈接成本估計(jì)和基于成本的計(jì)算估計(jì)兩個(gè)優(yōu)化策略來(lái)避免通過(guò)圖的拓?fù)浣Y(jié)構(gòu)的擴(kuò)展來(lái)進(jìn)行子圖匹配中間存在著大量的無(wú)用遍歷的問(wèn)題。其中算法主要通過(guò)基于采樣的鏈接成本估計(jì)和基于成本的計(jì)算估計(jì)兩個(gè)優(yōu)化策略來(lái)避免當(dāng)通過(guò)圖的拓?fù)浣Y(jié)構(gòu)擴(kuò)展來(lái)進(jìn)行子圖匹配時(shí)存在大量無(wú)用遍歷的現(xiàn)象。此句不通順，“進(jìn)行”是否應(yīng)該改為“解決”，請(qǐng)明確查詢過(guò)程中，首先算法先將查詢圖進(jìn)行分解成二級(jí)樹(shù)的集合得到Stwig序列，分解過(guò)程中算法主要通過(guò)式（10）來(lái)選擇計(jì)算結(jié)果最大的頂點(diǎn)，分解算法主要保障能每次分解得到查詢圖中最大的二級(jí)樹(shù)。

其中：deg（v）為頂點(diǎn)v的度， frep（v.label）為頂點(diǎn)v標(biāo)簽的頻繁度。

分解之后，將Stwig序列廣播至集群中的各個(gè)節(jié)點(diǎn)，然后根據(jù)圖的拓?fù)浣Y(jié)構(gòu)進(jìn)行擴(kuò)展，其中主要通過(guò)優(yōu)化Stwig序列的匹配順序以此來(lái)降低節(jié)點(diǎn)間的通通信代價(jià)，最后得到匹配結(jié)果。算法主要通過(guò)拓?fù)浣Y(jié)構(gòu)的擴(kuò)展來(lái)代替索引避免join操作產(chǎn)生大量的中間結(jié)果，降低計(jì)算成本，提升匹配的速度;但是Stwig并沒(méi)有與通過(guò)索引的查詢的相關(guān)算法作比較，同時(shí)實(shí)驗(yàn)對(duì)比算法較少。

3.3 分布式下子圖查詢算法總結(jié)

目前針對(duì)分布式下的子圖查詢算法，相關(guān)研究還處于起步階段，現(xiàn)有的查詢算法也都是未通過(guò)索引查詢完成的，因此針對(duì)查詢效率方面還有很大的提升空間，同時(shí)分布式下的子圖查詢算法相比單機(jī)下的查詢算法有著評(píng)價(jià)指標(biāo)不單一、算法結(jié)構(gòu)更加復(fù)雜等特點(diǎn)。

4 結(jié)語(yǔ)

本文闡述了基于索引的子圖查詢的相關(guān)工作，通過(guò)建立索引可以有效降低查詢中子圖同構(gòu)的計(jì)算時(shí)間。從索引的構(gòu)建方法出發(fā)對(duì)主流的構(gòu)建方法進(jìn)行分類探討，分別對(duì)基于不同構(gòu)建方法的索引從索引特征的類型、索引特征獲取方法、索引數(shù)據(jù)結(jié)構(gòu)、索引是否存儲(chǔ)位置信息這四個(gè)方面進(jìn)行了對(duì)比分析，最后對(duì)最新的分布式環(huán)境下的子圖查詢算法作了簡(jiǎn)單歸總。

隨著子圖查詢的廣泛應(yīng)用以及數(shù)據(jù)量的不斷增加。針對(duì)大數(shù)據(jù)環(huán)境，以往圖查詢技術(shù)很難適應(yīng)與相應(yīng)的工作環(huán)境。與傳統(tǒng)的精確查詢不同，大數(shù)據(jù)環(huán)境下的查詢主要以模糊匹配為主，相應(yīng)現(xiàn)圖查詢技術(shù)面臨著以下幾方面的挑戰(zhàn)：1）索引的構(gòu)建本身就存在大量的時(shí)空開(kāi)銷，與數(shù)據(jù)量的增加不成線性關(guān)系，并且存在一定的局部性;2）針對(duì)千萬(wàn)級(jí)頂點(diǎn)以上的數(shù)據(jù)圖很難有合適的圖索引算法能構(gòu)建索引，完成快速查詢操作;3）面對(duì)動(dòng)態(tài)圖下的索引維護(hù)容易喪失部分索引信息，通過(guò)針對(duì)索引性能的檢測(cè)很難做到實(shí)時(shí)反饋的程度。

針對(duì)上述問(wèn)題，圖索引今后的發(fā)展趨勢(shì)主要可以有：如下。

1）設(shè)計(jì)構(gòu)建多級(jí)索引結(jié)構(gòu)。針對(duì)目前索引構(gòu)建的主要問(wèn)題來(lái)看，主要體現(xiàn)在兩個(gè)方面：a）從算法自身角度看，索引構(gòu)建過(guò)程的時(shí)空損耗本來(lái)就十分巨大，尤其是基于頻繁模式挖掘的索引構(gòu)建算法。b）從數(shù)據(jù)角度看，由于數(shù)據(jù)量的不斷增加，其計(jì)算量也增大，同時(shí)數(shù)據(jù)的存儲(chǔ)就成了主要問(wèn)題，而通過(guò)將圖壓縮技術(shù)和多級(jí)索引技術(shù)相結(jié)合，能有效提高索引表的覆蓋率以及在可接受的時(shí)間內(nèi)返回精確的答案集，因此，從索引構(gòu)建的角度出發(fā)，如何結(jié)合先主流的圖壓縮技術(shù)設(shè)計(jì)出精簡(jiǎn)高效的多級(jí)索引，將會(huì)是未來(lái)研究的一大趨勢(shì)。

2）分布式環(huán)境下的索引構(gòu)建方法。傳統(tǒng)的基于索引的查詢算法難以適用于分布式下的子圖查詢操作。圖數(shù)據(jù)內(nèi)部具有強(qiáng)關(guān)聯(lián)性的特征，針對(duì)分布式下的子圖查詢算法有著數(shù)據(jù)通信量大、冗余計(jì)算嚴(yán)重等問(wèn)題，通過(guò)構(gòu)建索引能有效地減少子圖查詢過(guò)程中的冗余計(jì)算量，設(shè)計(jì)合理的任務(wù)調(diào)度算法也能大幅度地降低系統(tǒng)的信息吞吐量，但目前針對(duì)此類的研究尚未起步。針對(duì)分布式下的索引構(gòu)建出發(fā)，如何設(shè)計(jì)合理的索引結(jié)構(gòu)以適用于分布式環(huán)境下的子圖查詢算法，在未來(lái)也將會(huì)是研究的一大熱點(diǎn)。

3）動(dòng)態(tài)圖的索引維護(hù)。圖數(shù)據(jù)的頻繁更新，傳統(tǒng)的方法很難將索引覆蓋率維持在容忍范圍內(nèi)。動(dòng)態(tài)圖的索引維護(hù)是一個(gè)較新的領(lǐng)域?，F(xiàn)有的方法主要是通過(guò)增量監(jiān)控的算法計(jì)算查詢返回的答案集的偏移量，并設(shè)置閾值進(jìn)行索引更新，更新方法都是通過(guò)直接重構(gòu)實(shí)現(xiàn)。由于涉及到主觀因素，其更新速度未能滿足實(shí)時(shí)性的要求，同時(shí)由于引入了偏移量的計(jì)算，索引更新存在一定誤差，存在大量的資源浪費(fèi)現(xiàn)象。這也將是未來(lái)研究的一大趨勢(shì)。

參考文獻(xiàn) （References）

[1] BERMAN H M， WESTBROOK J， FENG Z， et al. The protein data bank [J]. Genetica， 2000， 106（1/2）： 149-158.

[2] DESHPANDE M， KURAMOCHI M， WALE N， et al. Frequent substructure-based approaches for classifying chemical compounds [C]// ICDM 2003： Proceedings of the 2003 International Conference on IEEE International Conference on Data Mining. Washington， DC： IEEE Computer Society， 2003： 35.

[3] LIANG R， HAI Z， JIANG X， et al. Scaling hop-based reachability indexing for fast graph pattern query processing [J]. IEEE Transactions on Knowledge & Data Engineering， 2014， 26（11）： 2803-2817.

[4] YUAN Y， WANG G， XU J Y， et al. Efficient distributed subgraph similarity matching [J]. VLDB Journal， 2015， 24（3）： 369-394.

[5] LAPPAS T， LIU K， TERZI E. Finding a team of experts in social networks[C]// KDD 2009： Proceedings of the 2009 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 467-476.

[6] 王超琿，黃一夫.基于增量信息索引的子圖查詢算法[J].計(jì)算機(jī)應(yīng)用與軟件，2016，33（10）：37-40.（WANG C H， HUANG Y F. A subgraph query algorithm based on incremental information index [J]. Computer Applications & Software， 2016， 33（10）： 37-40.）

[7] DINARI H. A survey on graph queries processing： techniques and methods [J]. International Journal of Computer Network & Information Security， 2017， 9（4）： 48-56.

[8] KATSAROU F， NTARMOS N， TRIANTAFILLOU P. Performance and scalability of indexed subgraph query processing methods [J]. Proceedings of the VLDB Endowment， 2015， 8（12）： 1566-1577.

[9] YAN X， YU P S， HAN J. Graph indexing： a frequent structure-based approach [C]// ICMD 2004： Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2004： 335-346.

[10] 陸慧琳，黃博.基于雙索引的子圖查詢算法[J].計(jì)算機(jī)工程，2015， 41（1）：44-48.（LU H L， HUANG B. Subgraph query algorithm based on dual index [J]. Computer Engineering， 2015， 41（1）：44-48.）

[11] 黃云，洪佳明，覃遵躍，等.ERSearch：一種高效的子圖查詢算法[J].電子學(xué)報(bào)，2017，45（2）：368-375（HUANG Y， HONG J M， TAN Z Y， et al. ERSearch： an efficient subgraph query algorithm [J]. Acta Electronica Sinica， 2017， 45（2）： 368-375.）

[12] SOMKUNWAR M R， VAZE V M. Subgraph isomorphism algorithms for matching graphs： a survey [EB/OL]. （2017-07-01）[2017-12-10]. http：//ijett.in/index.php/IJETT/article/view/279/173.

[13] ZOU L， CHEN L， YU J X， et al. A novel spectral coding in a large graph database [C]// EDBT 2008： Proceedings of the 2008 International Conference on Extending Database Technology. New York： ACM， 2008： 181-192.

[14] BONNICI V， FERRO A， GIUGNO R， et al. Enhancing graph database indexing by suffix tree structure [C]// PRIB 2010： Proceedings of the 2010 International Conference on Pattern Recognition in Bioinformatics. Berlin： Springer， 2010： 195-203.

[15] GIUGNO R， BONNICI V， BOMBIERI N， et al. GRAPES： a software for parallel searching on biological graphs targeting multi-core architectures [J]. PLoS One， 2013， 8（10）： e76911.

[16] JIANG H， WANG H， YU P S， et al. GString： a novel approach for efficient search in graph databases [C]// ICDE2007： Proceedings of the 2007 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2007： 566-575.

[17] DI NATALE R， FERRO A， GIUGNO R， et al. SING： subgraph search in non-homogeneous graphs[J]. BMC Bioinformatics， 2010， 11（1）： 1-15.

[18] ZHAO P， HAN J. On graph query optimization in large networks [J]. Proceedings of the VLDB Endowment， 2010， 3（1/2）： 340-351.

[19] ZHANG S， YANG J， JIN W. SAPPER： subgraph indexing and approximate matching in large graphs [J]. Proceedings of the VLDB Endowment， 2010， 3（1）： 1185-1194.

[20] ZHANG S， HU M， YANG J. TreePi： a novel graph indexing method [C]// ICDE2007： Proceedings of the 2007 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2007： 966-975.

[21] ZHAO P， YU J X， YU P S. Graph indexing： tree+delta<=graph [C]// VLDB 2007： Proceedings of the 33rd International Conference on Very Large Data Bases. Trondheim： VLDB Endowment， 2007： 938-949.

[22] CHENG J， KE Y， NG W， et al. FG-index： towards verification-free query processing on graph databases [C]// SIGMOD 2017： Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2007： 857-872.

[23] YUAN D， MITRA P. Lindex： a lattice-based index for graph databases [J]. The VLDB Journal—The International Journal on Very Large Data Bases， 2013， 22（2）： 229-252.

[24] YUAN D， MITRA P， YU H， et al. Iterative graph feature mining for graph indexing [C]// ICDE2012： Proceedings of the 2012 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2012： 198-209.

[25] KLEIN K， KRIEGE N， MUTZEL P. CT-index： fingerprint-based graph indexing combining cycles and trees [C]// ICDE2011： Proceedings of the 2011 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2011： 1115-1126.

[26] LYU B， QIN L， LIN X， et al. Scalable supergraph search in large graph databases [C]// ICDE2016： Proceedings of the 2016 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2016： 157-168.

[27] YUAN D， MITRA P， GILES C L. Mining and indexing graphs for supergraph search [J]. Proceedings of the VLDB Endowment， 2013， 6（10）： 829-840.

[28] XIE Y， YU P S. CP-index： on the efficient indexing of large graphs [C]// CIKM： Proceedings of the 2011 ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 1795-1804.

[29] ULLMANN J R. An algorithm for subgraph isomorphism [J]. Journal of the ACM， 1976， 23（1）： 31-42.

[30] CORDELLA L P， FOGGIA P， SANSONE C， et al. A （sub）graph isomorphism algorithm for matching large graphs [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2004， 26（10）： 1367.

[31] HU H， WEN Y， CHUA T S， et al. Toward scalable systems for big data analytics： a technology tutorial [J]. IEEE Access， 2017， 2（1）： 652-687.

[32] MA S， CAO Y， HUAI J， et al. Distributed graph pattern matching [C]// WWW12： Proceedings of the 2013 Conference on World Wide Web. New York： ACM， 2012： 949-958.

[33] SUN Z， WANG H Z， WANG H X， et al. Efficient subgraph matching on billion node graphs [J]. Proceedings of the VLDB Endowment， 2012， 5（9）： 788-799.