施煒杰 董一鴻 王雄 潘劍飛

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

關鍵詞：子圖同構;索引;子圖查詢;頻繁模式

中圖分類號： TP391

文獻標志碼：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 引言

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

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

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

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

1 基本概念

2 基于索引的圖查詢技術

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

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

2.1 查詢算法的基本結構

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

2.1.1 索引構建

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

2.1.2 查詢

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

2.1.3 答案驗證

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

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

2.2 基于枚舉的索引構建方法

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

2.2.1 gCode

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

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

2.2.2 GraphGrepSX

GraphGrepSX[14]適用于無向圖，使用深度優(yōu)先遍歷（Depth-First-Search， DFS）算法枚舉所有長度為k的路徑，并存儲在后綴樹中。樹中每個節(jié)點存儲圖的id列表以及出現(xiàn)在每個圖中對應路徑的次數(shù)。對查詢圖進行類似的分解與索引特征比較，剪枝掉與查詢圖不匹配的分支，根據(jù)節(jié)點中標簽的出現(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é)點巧妙地分配給線程完成，以便每個線程在不需要與其他線程同步信息同步的情況下完成計算任務。在查詢過程中，查詢圖也經(jīng)歷了相同并行化的路徑枚舉和樹結構處理，然后比較查詢樹與索引樹，刪除不匹配部分，通過保留的位置信息進一步過濾不必要的子圖，最后進行子圖同構測試得出答案集。此類索引適用于小量數(shù)據(jù)集。

2.2.3 Gstring

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

2.2.4 CT-index

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

2.2.5 小結

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

2.3 基于頻繁模式挖掘的索引構建方法

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

2.3.1 gIndex

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

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

2.3.2 FG-index

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

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

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

2.3.3 tree+Δ

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

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

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

2.3.4 Lindex

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

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

其中gain（p，P0）為索引特征集P0添加特征p之后的索引剪枝力的增益。

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

2.3.5 小結

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

2.4 基于索引的子圖查詢算法總結

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

3 分布式下的子圖查詢

當面對海量數(shù)據(jù)集時，往往將數(shù)據(jù)圖存儲在分布式平臺中。分布式查詢已經(jīng)在關系數(shù)據(jù)和XML（EXtensible Markup Language）等方面有了廣泛的研究。針對分布式平臺下對圖模型作挖掘分析面臨這如下幾個問題：1）數(shù)據(jù)圖的存儲;2）高效分布式算法的設計;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ù)傳輸量為主的評估標準。算法整體可以分為調(diào)度節(jié)點的調(diào)度算法和工作節(jié)點的匹配算法兩個部分。調(diào)度算法主要為匹配后對所有結果進行join操作時提供調(diào)度策略;匹配算法則是直接通過DFS遍歷枚舉工作節(jié)點中與查詢圖匹配的數(shù)據(jù)圖，其中主要考慮部分匹配和完全匹配兩種情況。算法在查詢過程中，首先通過調(diào)度節(jié)點將查詢圖廣播至各個工作節(jié)點上，各節(jié)點中通過單機下的HHK（Henzinger Henzinger KopkeHHK有英文全稱嗎？）匹配算法枚舉出數(shù)據(jù)圖中與查詢圖匹配的映射集，然后將結果回傳至調(diào)度節(jié)點;調(diào)度節(jié)點通過基于貪心的調(diào)度策略分配各匹配結果至最優(yōu)的工作節(jié)點進行join操作，最后輸出查詢圖的查詢結果。disHHK算法主要適用于有向圖，由于其在單機下的匹配策略是通過DFS遍歷來枚舉查詢圖的匹配集，所以當節(jié)點間數(shù)據(jù)分布不均衡時，木桶效應就比較明顯。

3.2 Stwig算法

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

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

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

3.3 分布式下子圖查詢算法總結

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

4 結語

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

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

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

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

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

3）動態(tài)圖的索引維護。圖數(shù)據(jù)的頻繁更新，傳統(tǒng)的方法很難將索引覆蓋率維持在容忍范圍內(nèi)。動態(tài)圖的索引維護是一個較新的領域?，F(xiàn)有的方法主要是通過增量監(jiān)控的算法計算查詢返回的答案集的偏移量，并設置閾值進行索引更新，更新方法都是通過直接重構實現(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].計算機應用與軟件，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].電子學報，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.