基于增量信息索引的子圖查詢算法

王超琿　黃一夫

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院智能信息處理重點(diǎn)實(shí)驗(yàn)室　上海 200433)

?

基于增量信息索引的子圖查詢算法

王超琿黃一夫

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院智能信息處理重點(diǎn)實(shí)驗(yàn)室上海 200433)

當(dāng)前圖數(shù)據(jù)庫(kù)中的子圖同構(gòu)查詢算法主要是依賴倒排索引，然而處理那些具有龐大數(shù)據(jù)的數(shù)據(jù)庫(kù)和復(fù)雜的查詢愈發(fā)成為挑戰(zhàn)。研究目的是設(shè)計(jì)一個(gè)算法，使用新的索引作為查詢處理的核心，記錄查詢圖的每一個(gè)細(xì)小改變，并使用一種特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)。先是引出一個(gè)索引算法，然后逐漸分析整個(gè)索引、查詢過(guò)程，并利用該算法實(shí)現(xiàn)一個(gè)系統(tǒng)，最后在不同數(shù)據(jù)集和查詢上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)證明了該算法具有良好的時(shí)間、空間效率和擴(kuò)展性。新的索引算法能夠支持更大的查詢圖和更加靈活的查詢。通過(guò)實(shí)現(xiàn)的系統(tǒng)和其他系統(tǒng)的對(duì)比實(shí)驗(yàn)，驗(yàn)證了算法的有效性。

圖數(shù)據(jù)庫(kù)子圖同構(gòu)片段子圖查詢索引查詢算法

0　引　言

隨著互聯(lián)網(wǎng)步入2.0時(shí)代，圖數(shù)據(jù)庫(kù)越來(lái)越多地出現(xiàn)在我們的生活中，例如社交網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)、化學(xué)結(jié)構(gòu)等，對(duì)于它的檢索需求也與日俱增。你可以在Facebook查看你好友或者好友的好友發(fā)出的消息；你可以在生物信息數(shù)據(jù)庫(kù)中研究某種DNA、某種氨基酸、某種蛋白質(zhì)；你可以在化學(xué)數(shù)據(jù)庫(kù)中查詢某種化學(xué)結(jié)構(gòu)。支撐這些應(yīng)用的底層存儲(chǔ)數(shù)據(jù)庫(kù)不是普通的數(shù)據(jù)庫(kù)，而是圖數(shù)據(jù)庫(kù)。當(dāng)你使用這些應(yīng)用時(shí)會(huì)有圖數(shù)據(jù)庫(kù)查詢，即使你沒(méi)有意識(shí)到，這一切都在不知不覺(jué)中進(jìn)行著。

有的圖數(shù)據(jù)庫(kù)本身就是一張大圖[1]，有的圖數(shù)據(jù)庫(kù)中存儲(chǔ)了千千萬(wàn)萬(wàn)的小圖。傳統(tǒng)的數(shù)據(jù)庫(kù)只能將一個(gè)圖存為一個(gè)整體，不能利用其中的結(jié)構(gòu)信息。隨著技術(shù)的進(jìn)步和發(fā)展，圖數(shù)據(jù)庫(kù)的實(shí)用價(jià)值不斷增大，所以使用的比例也不斷加大。

圖數(shù)據(jù)庫(kù)需要檢索技術(shù)，本文研究的檢索是子圖同構(gòu)檢索。進(jìn)行這樣的檢索有幾個(gè)要求：檢索結(jié)果需要完全正確，不能漏掉數(shù)據(jù)庫(kù)中應(yīng)該檢索到的圖，或者檢索出不正確的圖；檢索處理的速度需要足夠快，同時(shí)使用的內(nèi)存要合理。

順序枚舉數(shù)據(jù)庫(kù)里的每個(gè)圖，并且查看查詢是不是它的子圖是效率比較低的做法。因?yàn)樽訄D同構(gòu)查詢是NP完全問(wèn)題[2]，在整個(gè)圖數(shù)據(jù)庫(kù)上進(jìn)行，花費(fèi)很大。因此，現(xiàn)在通行的做法是建立索引，之后在查詢時(shí)進(jìn)行兩階段的處理：過(guò)濾和驗(yàn)證。過(guò)濾是在圖數(shù)據(jù)庫(kù)中選出部分圖組成候選集集合，過(guò)濾掉一些不符合的圖，縮小需要運(yùn)行子圖同構(gòu)檢測(cè)的數(shù)據(jù)范圍大小。這時(shí)，候選集已經(jīng)大大減小了，需要運(yùn)行子圖同構(gòu)檢測(cè)的次數(shù)變少了，可以加快查詢的速度。驗(yàn)證部分運(yùn)行子圖同構(gòu)檢測(cè)，確定正確的結(jié)果。如果過(guò)濾步驟能夠顯著地降低候選集的大小，那么這個(gè)基于索引的兩階段算法就是有效并且實(shí)用的。候選集的大小可以作為不同算法性能直接比較的一個(gè)重要指標(biāo)。

GraphGrep[3]提出了子圖查詢問(wèn)題，Tree+Δ[4]使用了樹(shù)作為索引，gIndex[5]使用了圖作為索引，F(xiàn)G-Index[6]提出了避免過(guò)濾階段的方法。傳統(tǒng)的索引是建立頻繁子圖的倒排索引，沒(méi)有利用其中的結(jié)構(gòu)信息。本文在構(gòu)建索引時(shí)在子圖之間增加信息，構(gòu)建的索引是由子圖構(gòu)成的圖。

本文研究的主要目的是設(shè)計(jì)一個(gè)符合以上要求的支持子圖查詢的算法。

1　基本概念

1.1相關(guān)定義

定義2圖G1子圖同構(gòu)于圖G2(表示為G1?G2)，若存在一個(gè)單射函數(shù)f:V1→V2，使得?u∈V1都有φ1(u)=φ2(f(u))；?(u,v)∈E1都有(f(u),f(v))∈E2。

定義3一個(gè)圖G的正規(guī)表示Canon(G)是一個(gè)帶標(biāo)簽的圖，同構(gòu)于G，且任意同構(gòu)于G的圖都和G有相同的正規(guī)表示，正規(guī)表示是唯一的。找尋圖的正規(guī)表示的問(wèn)題叫作圖的正規(guī)化。因此，如果有一個(gè)圖的正規(guī)化的算法，這個(gè)算法同樣能夠解決圖的同構(gòu)問(wèn)題。對(duì)于兩個(gè)圖G和H，計(jì)算它們的正規(guī)表示Canon(G)和Canon(H)，然后檢測(cè)兩個(gè)正規(guī)表示是否相同。如果相同必定同構(gòu)，如果不同必定不同構(gòu)[7]。

定義5術(shù)語(yǔ)片段用于稱呼圖數(shù)據(jù)庫(kù)或者查詢圖中的一個(gè)小的子圖。

1.2問(wèn)題描述

本文研究的圖數(shù)據(jù)庫(kù)，是由許多的小圖組成的。每個(gè)小圖的規(guī)模都不大(點(diǎn)數(shù)、邊數(shù)<200)，但是小圖的數(shù)目非常多(10×103～200×103)。給定圖數(shù)據(jù)庫(kù)D={G1,G2,…,Gn}，查詢圖Q。子圖查詢問(wèn)題是找出所有的Gi，使得Q?Gi。

2　算　法

傳統(tǒng)的索引是建立頻繁子圖的倒排索引，沒(méi)有利用其中的結(jié)構(gòu)信息。并且傳統(tǒng)的索引沒(méi)有考慮到索引本身和查詢之間的聯(lián)系。本文在構(gòu)建索引時(shí)在子圖之間增加信息，構(gòu)建的索引是由子圖構(gòu)成的圖。這是為了查詢時(shí)使用的特性而特別優(yōu)化的。

圖1是整體系統(tǒng)的結(jié)構(gòu)，包含有索引構(gòu)建器、查詢處理機(jī)和驗(yàn)證器。索引構(gòu)建器能夠輸入圖數(shù)據(jù)庫(kù)并且為其構(gòu)建索引。查詢處理器用于處理查詢，輸入查詢后對(duì)查詢進(jìn)行分析，在讀取索引的同時(shí)維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)保存圖的特征信息。這些信息是同時(shí)和查詢圖和索引相關(guān)聯(lián)的，從這個(gè)數(shù)據(jù)結(jié)構(gòu)中可以提取候選集，傳遞給驗(yàn)證器。驗(yàn)證器用于驗(yàn)證候選集，輸出查詢結(jié)果。

圖1　系統(tǒng)結(jié)構(gòu)圖

2.1增量信息索引

本文提出的增量信息索引結(jié)構(gòu)本身是一個(gè)分層的有向無(wú)環(huán)圖，圖2是從本文使用的索引所進(jìn)行的可視化展示中截取的。

圖2　增量信息索引結(jié)構(gòu)圖

定義9若有圖數(shù)據(jù)庫(kù)D和其上的頻繁片段集合F，可以構(gòu)建增量信息索引I={I1,I2,…,In}。索引中的每一項(xiàng)Ii都對(duì)應(yīng)一個(gè)片段，由標(biāo)識(shí)符、正規(guī)編碼、類型、大小、轉(zhuǎn)移信息、父親和支持圖集合組成。

這里我們只將頻繁片段和顯著非頻繁片段放入增量信息索引中，這樣做的原因是所有片段的種類是非常多的，不可能全部放入索引中。已知使用頻繁片段是一種能大幅度降低片段數(shù)量的方法，可以通過(guò)調(diào)節(jié)最小支持度閾值α來(lái)控制數(shù)量，并且過(guò)濾效果很好。本文使用一種已有的圖數(shù)據(jù)庫(kù)挖掘算法gSpan生成頻繁片段[9]。

片段的轉(zhuǎn)移信息是一個(gè)數(shù)組，表示片段上所有可以進(jìn)行的操作和操作的結(jié)果。操作就是給片段增加一條邊，因?yàn)樵黾油赀吅笃稳耘f是連通的，所以操作有兩種：

(1) 增加邊的同時(shí)增加一個(gè)新的結(jié)點(diǎn)，新的邊將新的結(jié)點(diǎn)連接到片段中一個(gè)已有的結(jié)點(diǎn)上，我們記這種操作為Nx(y)。其中x為已有結(jié)點(diǎn)的編號(hào)，y為新結(jié)點(diǎn)的標(biāo)簽。如N0(C)表示將一個(gè)標(biāo)簽為C的新結(jié)點(diǎn)連接到已有的0號(hào)結(jié)點(diǎn)上。

(2) 在已有的兩個(gè)沒(méi)有邊連接的結(jié)點(diǎn)之間連接一條邊，我們記這種操作為Cx-y。其中x、y分別為已有兩個(gè)結(jié)點(diǎn)的編號(hào)，且x

定義10操作的結(jié)果叫作轉(zhuǎn)移(trans)，形如 (id,newIds)。若這個(gè)操作是對(duì)片段a做的，得到片段a′，a′的正規(guī)表示為b，那么id為b的標(biāo)識(shí)符，newIds表示的是a′到b的同構(gòu)映射函數(shù)f。

2.2增量信息索引的構(gòu)建

首先，將所有頻繁片段連同它們的信息(包括它們的支持圖集合)放入增量信息索引中。然后依次枚舉所有的頻繁片段，并對(duì)其嘗試前文所提到的兩種操作：增加邊的同時(shí)增加一個(gè)新的結(jié)點(diǎn)，在已有的兩個(gè)沒(méi)有邊連接的結(jié)點(diǎn)之間連接一條邊。若操作的結(jié)果從片段f得到新圖newGraph和轉(zhuǎn)移newIds，片段f在索引中對(duì)應(yīng)的項(xiàng)為If。根據(jù)newGraph的性質(zhì)進(jìn)行以下操作：

1) 若newGraph是頻繁片段，對(duì)應(yīng)索引中的項(xiàng)InewGraph，我們記錄三元組(op,InewGraph.id,newIds)到索引中If項(xiàng)的信息中。

3) 若newGraph是顯著非頻繁片段，對(duì)應(yīng)索引中的項(xiàng)InewGraph，我們記錄三元組(op,InewGraph.id,newIds)到索引中If項(xiàng)的信息中。

4) 若newGraph是非顯著非頻繁片段，我們不做任何事。

最后檢查所有的DIF，若其支持圖集合為空，則其支持圖集合的候選集C可由它所有父節(jié)點(diǎn)支持圖集合的交集得到。在C上運(yùn)行驗(yàn)證器可以得到其支持圖集合。

2.3簡(jiǎn)單紡錘形圖

在文獻(xiàn)[10]中，作者提出了紡錘形圖的概念。本文在此基礎(chǔ)上提出了簡(jiǎn)單紡錘形圖，作為查詢圖的特性信息。簡(jiǎn)單紡錘形圖改變了圖中每個(gè)結(jié)點(diǎn)所代表的意義和包含的信息，不過(guò)還是繼承了其紡錘形的特征和思想。文獻(xiàn)[10]中使用多個(gè)紡錘形圖，本文只使用一個(gè)簡(jiǎn)單紡錘形圖；原有紡錘形圖每個(gè)結(jié)點(diǎn)都是原有查詢中的一個(gè)片段，本文只是索引項(xiàng)的標(biāo)識(shí)符；原有紡錘形圖中結(jié)點(diǎn)的總個(gè)數(shù)一定是查詢圖所有連通子圖的個(gè)數(shù)，本文簡(jiǎn)單紡錘形圖中結(jié)點(diǎn)數(shù)量的增長(zhǎng)較為平緩。因此本文縮減了操作簡(jiǎn)單紡錘形圖的時(shí)間，使得添加邊、刪除邊的操作更加高效。

定義11簡(jiǎn)單紡錘形圖(SimpleSPIG)是一個(gè)圖，結(jié)點(diǎn)i帶有數(shù)據(jù){id,edgeSets}。i.id是增量信息索引中索引項(xiàng)的標(biāo)識(shí)符。若兩個(gè)簡(jiǎn)單紡錘形圖中的結(jié)點(diǎn)各自對(duì)應(yīng)的索引項(xiàng)在增量信息索引中有邊連接，那么在簡(jiǎn)單紡錘形圖中這兩個(gè)結(jié)點(diǎn)也有邊連接。i.edgeSets是邊集的集合且不為空。

圖3展示了簡(jiǎn)單紡錘形圖的結(jié)構(gòu)。當(dāng)用戶插入了一條邊后，簡(jiǎn)單紡錘形圖只會(huì)增加結(jié)點(diǎn)和結(jié)點(diǎn)中的邊集。當(dāng)用戶刪除邊后，簡(jiǎn)單紡錘形圖中的結(jié)點(diǎn)和結(jié)點(diǎn)中的邊集只會(huì)減少。我們需要實(shí)現(xiàn)增加邊和刪除邊的算法。

圖3　簡(jiǎn)單紡錘形圖

2.4增加查詢邊算法

每次加入新的邊時(shí)，會(huì)更新簡(jiǎn)單紡錘形圖。用廣度優(yōu)先搜索從小到大找出所有包含種子邊的查詢圖的連通子圖。廣度優(yōu)先搜索所使用的隊(duì)列里存儲(chǔ)的是用于表示片段的三元組(查詢結(jié)點(diǎn)標(biāo)識(shí)符數(shù)組,邊集,索引項(xiàng)的標(biāo)識(shí)符)。其中查詢結(jié)點(diǎn)標(biāo)識(shí)符數(shù)組和邊集可以定位片段在查詢圖中的位置，索引項(xiàng)的標(biāo)識(shí)符可以定位片段在索引中的位置。

每次從隊(duì)列中取出一個(gè)三元組后，我們嘗試所有給它加邊的方法，加上新的邊得到新的邊集。若還沒(méi)有被處理過(guò)，使用加邊操作在索引信息中查找。若能找到對(duì)應(yīng)的轉(zhuǎn)移，利用查詢結(jié)點(diǎn)標(biāo)識(shí)符數(shù)組和轉(zhuǎn)移中的newIds構(gòu)建新的查詢結(jié)點(diǎn)標(biāo)識(shí)符數(shù)組，并且將新的三元組加入到隊(duì)列中去。并且，同時(shí)將標(biāo)識(shí)符添加到簡(jiǎn)單紡錘形圖中，這里添加時(shí)需要使用父親信息。這是因?yàn)槿粲懈赣H已經(jīng)存在在簡(jiǎn)單紡錘形圖中，我們需要連一條到父親的邊。然后將邊集加入到簡(jiǎn)單紡錘形圖結(jié)點(diǎn)的邊集中。

等到隊(duì)列全部處理完成的時(shí)候，算法也就終止了，此時(shí)更新也完成了。

2.5刪除查詢邊算法

刪除一條邊的算法只需要對(duì)簡(jiǎn)單紡錘形圖進(jìn)行更新就可以了，不需要使用到索引的信息。其主要的思想是移除所有簡(jiǎn)單紡錘形圖中包含有需要?jiǎng)h除邊的邊集，若移除后簡(jiǎn)單紡錘形圖中結(jié)點(diǎn)的邊集集合為空，說(shuō)明此結(jié)點(diǎn)的限制不必再應(yīng)用于這個(gè)查詢，可以移除這個(gè)結(jié)點(diǎn)了。更新完成后就可以得到所需的新的簡(jiǎn)單紡錘形圖。

2.6得到查詢結(jié)果

這里需要根據(jù)簡(jiǎn)單紡錘形圖的層數(shù)分兩種情況：

1) 若層數(shù)存在和查詢大小相同的這一層，簡(jiǎn)單紡錘形圖形成一個(gè)完整的紡錘形，那么說(shuō)明查詢本身就在索引中出現(xiàn)過(guò)?？梢灾苯邮褂盟饕闹С謭D集合作為查詢的結(jié)果，不需要再做驗(yàn)證。

2) 否則，還需要再次通過(guò)驗(yàn)證器驗(yàn)證才能作為查詢的結(jié)果。先從簡(jiǎn)單紡錘形圖中所有葉子結(jié)點(diǎn)中取出它們的支持圖集合，并把這些集合的交集作為查詢結(jié)果的候選集，驗(yàn)證完后作為查詢結(jié)果。只取所有的葉子結(jié)點(diǎn)是因?yàn)椋粢粋€(gè)結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，那么它一定有一個(gè)后代并且這個(gè)后代的支持圖集合是它的支持圖集合的子集，所以沒(méi)有必要再和非葉子結(jié)點(diǎn)的支持圖集合做交集操作。

3　實(shí)驗(yàn)結(jié)果與分析

本文所實(shí)現(xiàn)的程序稱為Inc-Info，將與之前的算法Prague進(jìn)行比較，并進(jìn)行性能測(cè)試。實(shí)驗(yàn)是在一臺(tái)IntelCorei7-4700MQ處理器、12GB內(nèi)存、運(yùn)行Windows8.1x64操作系統(tǒng)的計(jì)算機(jī)上進(jìn)行的。實(shí)驗(yàn)環(huán)境上安裝有Java1.8和Graphviz2.38。

實(shí)驗(yàn)的數(shù)據(jù)集是AIDS抗病毒數(shù)據(jù)集，是一個(gè)真實(shí)的數(shù)據(jù)集，總共包含有43 000個(gè)化學(xué)結(jié)構(gòu)。取頻率閾值α為0.1，并運(yùn)行g(shù)Span生成頻繁片段。

圖4顯示了在AIDS數(shù)據(jù)集上建立索引，得到片段數(shù)與索引大小、片段大小的關(guān)系。頻繁片段的總數(shù)為2847，構(gòu)建時(shí)間為70分鐘，總索引大小為139.3MB，其中支持圖集合占138.5MB，數(shù)據(jù)庫(kù)文件占用磁盤總空間237MB。實(shí)驗(yàn)表明，片段個(gè)數(shù)會(huì)隨著片段大小的增長(zhǎng)而增多，但是達(dá)到一個(gè)最大值后反而會(huì)下降，最后歸零，說(shuō)明此算法片段數(shù)是可控的。在最后得到的增量信息索引中，支持圖集合占據(jù)了絕大部分空間，說(shuō)明本算法表示索引結(jié)構(gòu)部分的信息是十分高效的。

圖4　索引大小分布圖

本文手工構(gòu)建了18個(gè)查詢圖，作為測(cè)試樣例。在Inc-Info和Prague上輸入測(cè)試Q1-Q18，得到查詢用時(shí)，見(jiàn)圖5、圖6所示。其中Q7-Q12、Q15-Q18的圖比較大，Prague無(wú)法處理，因此沒(méi)有結(jié)果。可以發(fā)現(xiàn)Inc-Info的查詢用時(shí)較小。

圖5　Q1-Q9測(cè)試用時(shí)

圖6　Q10-Q18測(cè)試用時(shí)

表1是在Inc-Info和Prague上輸入Q1后，刪除一條邊所獲得的操作用時(shí)。Prague不支持刪除邊5-邊7的操作，因?yàn)镻rague不能留下不連通的查詢圖，這點(diǎn)上Inc-Info較為靈活。而且可以看到Inc-Info較Prague在時(shí)間效率上有優(yōu)勢(shì)。

表1　刪除邊測(cè)試結(jié)果

4　結(jié)　語(yǔ)

本文提出了能夠快速轉(zhuǎn)移的新索引結(jié)構(gòu)、一種新的查詢時(shí)數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單紡錘形圖，組成一種新的相似度查詢過(guò)濾算法。這種新算法可以支持更大的查詢圖，并有更高的查詢性能。通過(guò)實(shí)驗(yàn)，將本文系統(tǒng)和現(xiàn)有系統(tǒng)進(jìn)行比較，證明了本文提供的算法在實(shí)踐上也具有良好的表現(xiàn)。未來(lái)可能的研究方向?qū)㈥P(guān)注如何縮小增量信息索引的大小，加快索引構(gòu)建速度。

[1]SunZ,WangHZ,WangHX,etal.Efficientsubgraphmatchingonbillionnodegraphs[J].ProceedingsoftheVLDBEndowment,2012,5(9):788-799.

[2]GareyMR,JohnsonDS.Computersandintractability:aguidetothetheoryofNP-completeness[M].USA:W.H.FreemanandCompany,1979.

[3]GiugnoR,ShashaD.GraphGrep:afastanduniversalmethodforqueryinggraphs[C]//Proceedingsofthe16thInternationalConferenceonPatternRecognition,Quebec,Canada,2002,2:112-115.

[4]ZhaoPX,YuJX,YuPS.Graphindexing:tree+delta>=graph[C]//Proceedingsofthe33rdInternationalConferenceonVeryLargeDataBases,2007:938-949.

[5]YanXF,YuPS,HanJW.Graphindexing:afrequentstructure-basedapproach[C]//Proceedingsofthe2004ACMSIGMODInternationalConferenceonManagementofData,2004:335-346.

[6]ChengJ,KeYP,NgW,etal.FG-Index:towardsverification-freequeryprocessingongraphdatabases[C]//Proceedingsofthe2007ACMSIGMODInternationalConferenceonManagementofData,2007:857-872.

[7]Canonicalform[EB/OL].Wikipedia[2015-03-20].http://en.wikipedia.org/wiki/Canonical_form.

[8]JinC,BhowmickSS,XiaoXK,etal.GBLENDER:towardsblendingvisualqueryformulationandqueryprocessingingraphdatabases[C]//Proceedingsofthe2010ACMSIGMODInternationalConferenceonManagementofData,2010:111-122.

[9]YanXF,HanJW.gSpan:graph-basedsubstructurepatternmining[C]//Proceedingsofthe2002IEEEInternationalConferenceonDataMining,2002:721-724.

[10]JinCJ,BhowmickSS,ChoiB,etal.Prague:towardsblendingpracticalvisualsubgraphqueryformulationandqueryprocessing[C]//Proceedingsofthe2012IEEE28thInternationalConferenceonDataEngineering,2012:222-233.

ASUBGRAPHQUERYALGORITHMBASEDONINCREMENTALINFORMATIONINDEX

WangChaohuiHuangYifu

(KeyLabofIntelligentInformationProcessing,SchoolofComputerScience,FudanUniversity,Shanghai200433,China)

Currentlysubgraphisomorphicqueryalgorithmsingraphdatabasemainlydependoninvertedindex.However,theprocessingofthosegraphdatabaseswithhugedataandthecomplicatedqueriesincreasinglybecomesachallenge.Thepurposeofourresearchistodesignanalgorithm,weusedanewindexasthecoreofqueryprocessing,recordedeverytinychangeinquerygraph,andmaintaineditwithaspecialdatastructure.Firstweintroducedanindexalgorithm,andthengraduallyanalysedthewholeprocessofindexandquery,andusedthealgorithmtohaveimplementedasystem,finallywecarriedouttheexperimentsondifferentdatasetsandqueries.Thisalgorithmhasbeenprovedwithgoodtimeandspaceproductivityandscalability.Thenewindexalgorithmisabletosupportgreaterquerygraphandmoreflexiblequery.Throughtheimplementedcomparativeexperimentsbetweenthissystemandothersystems,weverifiedtheefficiencyofthisalgorithm.

GraphdatabaseSubgraphisomorphismFragmentSubgraphqueryIndexQueryalgorithm

2015-05-18。王超琿，碩士生，主研領(lǐng)域：數(shù)據(jù)庫(kù)。黃一夫，碩士生。

TP

ADOI:10.3969/j.issn.1000-386x.2016.10.009