施煒杰 董一鴻 王雄 潘劍飛

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

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

中圖分類號： TP391

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

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

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

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

1 基本概念

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

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

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

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

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

2.1.1 索引構(gòu)建

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

2.1.2 查詢

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

2.1.3 答案驗證

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

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

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

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

2.2.1 gCode

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

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

2.2.2 GraphGrepSX

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

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

2.2.3 Gstring

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

2.2.4 CT-index

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

2.2.5 小結(jié)

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

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

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

2.3.1 gIndex

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

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

2.3.2 FG-index

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

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

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

2.3.3 tree+Δ

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

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

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

2.3.4 Lindex

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

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

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

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

2.3.5 小結(jié)

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

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

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

3 分布式下的子圖查詢

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

3.1 disHHK算法

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

3.2 Stwig算法

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

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

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

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

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

4 結(jié)語

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

隨著子圖查詢的廣泛應(yīng)用以及數(shù)據(jù)量的不斷增加。針對大數(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ù)據(jù)量的增加不成線性關(guān)系，并且存在一定的局部性;2）針對千萬級頂點以上的數(shù)據(jù)圖很難有合適的圖索引算法能構(gòu)建索引，完成快速查詢操作;3）面對動態(tài)圖下的索引維護容易喪失部分索引信息，通過針對索引性能的檢測很難做到實時反饋的程度。

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

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

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

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