基于雙索引的子圖查詢算法

陸慧琳,黃 博

(復(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)

傳統(tǒng)的子圖查詢算法大多只在圖數(shù)據(jù)庫(kù)上進(jìn)行一次挖掘算法,即在圖數(shù)據(jù)庫(kù)上建立穩(wěn)定的數(shù)據(jù)庫(kù)索引后將不再對(duì)索引進(jìn)行更新。隨著查詢興趣的改變或數(shù)據(jù)庫(kù)的頻繁更新,原有的數(shù)據(jù)庫(kù)索引將不再能提供有用的信息來(lái)減少查詢過(guò)程中候選圖的數(shù)量。為此,提出一種雙索引的子圖查詢算法,同時(shí)在數(shù)據(jù)庫(kù)和查詢流上挖掘頻繁子圖并建立索引。子圖查詢和查詢流索引的建立同步進(jìn)行,即使查詢興趣改變,查詢流索引也能自適應(yīng)地更新索引信息來(lái)優(yōu)化查詢效率。針對(duì)數(shù)據(jù)庫(kù)的頻繁更新,查詢流索引已提供實(shí)時(shí)的有效信息,數(shù)據(jù)庫(kù)索引無(wú)需重新建立。實(shí)驗(yàn)結(jié)果表明,雙索引的結(jié)合能有效提高查詢子圖的處理效率。

雙索引;查詢流索引;子圖查詢;頻繁子圖;圖數(shù)據(jù)庫(kù);子圖同構(gòu)

1 概述

圖作為一種通用的數(shù)據(jù)結(jié)構(gòu)可以用來(lái)表示各種復(fù)雜的數(shù)據(jù),被廣泛地應(yīng)用于各個(gè)領(lǐng)域,包括化學(xué)、生物信息[1]、軟件工程、社交網(wǎng)絡(luò)以及互聯(lián)網(wǎng)[2]等。而對(duì)于圖數(shù)據(jù)庫(kù)的管理與傳統(tǒng)的數(shù)據(jù)庫(kù)有許多的不同,其中基于圖數(shù)據(jù)庫(kù)的查詢有著明顯的區(qū)別。查詢匹配過(guò)程中重要的一環(huán)工作是子圖同構(gòu)檢測(cè),但是同構(gòu)檢測(cè)本身是NP問(wèn)題[3]。為了降低花費(fèi)在子圖同構(gòu)檢測(cè)上的時(shí)間,可以通過(guò)建立有效的索引來(lái)減少查詢過(guò)程中候選圖的數(shù)量,從而縮短整個(gè)子圖查詢所需的時(shí)間。

文獻(xiàn)[4]是最早針對(duì)子圖查詢問(wèn)題的研究,它提出以路徑為特征建立索引;文獻(xiàn)[5]提出采用樹形結(jié)構(gòu)+部分圖結(jié)構(gòu)作為索引;文獻(xiàn)[6]同樣采用了樹+部分圖,不過(guò)它采用了一種基于哈希值的指紋技術(shù);文獻(xiàn)[7]采用了兩步挖掘方法,先用深度優(yōu)先生成子樹,再用廣度優(yōu)先擴(kuò)展成子圖;文獻(xiàn)[8-9]都采用了頻繁子圖作為索引特征,前者使用差別率函數(shù)保留那些過(guò)濾能力較強(qiáng)的子圖,后者將所有頻繁子圖分別存儲(chǔ)在內(nèi)存和硬盤中。

傳統(tǒng)的子圖搜索算法大多只在圖數(shù)據(jù)庫(kù)上建立索引,本文采取雙索引的方法,同時(shí)在圖數(shù)據(jù)庫(kù)和查詢流上建立索引。在子圖查詢的過(guò)程中,挖掘在查詢流中的頻繁子圖,實(shí)時(shí)地建立查詢流索引作為數(shù)據(jù)庫(kù)索引的補(bǔ)充,反映實(shí)時(shí)的用戶查詢興趣。在查詢流索引的建立過(guò)程中,利用數(shù)據(jù)庫(kù)索引以及查詢的結(jié)果集減小建立索引的代價(jià)。在應(yīng)對(duì)數(shù)據(jù)庫(kù)的頻繁更新時(shí),并不采用重新挖掘整個(gè)數(shù)據(jù)庫(kù)的方法,而是根據(jù)用戶需求將查詢流索引中的重要索引圖更新到數(shù)據(jù)庫(kù)索引中。

2 基本概念

2.1 相關(guān)定義

定義1(圖) 一個(gè)圖G可由一組五元組(V,E,LV,LE,l)表示。其中,V表示圖中結(jié)點(diǎn)的集合;E是圖中邊的集合;LV,LE分別表示圖中結(jié)點(diǎn)和邊標(biāo)號(hào)的集合;l是標(biāo)號(hào)映射函數(shù),定義了V→LV和E→LE的映射關(guān)系。

定義2(子圖同構(gòu)) 有2個(gè)圖G1(V1,E1,LV1,LE1,l1)和G2(V2,E2,LV2,LE2,l2),如果存在一個(gè)單射函數(shù)f∶V1→V2,使得:

(1)?u∈V1,l1(u)=l2(f(u));

(2)?(u,v)∈E1,l1(u,v)=l2(f(u),f(v))成立,那么G1和G2是子圖同構(gòu)的,G1是G2的同構(gòu)子圖。

定義3(支持集、支持度) 給定一個(gè)圖數(shù)據(jù)庫(kù)GD={g1,g2,…,gn},一個(gè)子圖g的支持集為:

SSg={g′∈GD|g是g′的同構(gòu)子圖}

支持度為:

定義4(候選集、必要集) 給定一個(gè)圖g,它的候選集CSg、必要集ESg和支持集SSg之間的關(guān)系為:

必要集ESg?支持集SSg?候選集CSg

2.2 問(wèn)題描述

本文要解決的問(wèn)題是:給出一串查詢流QS={q1,q2,…,qn,…},在圖數(shù)據(jù)庫(kù)GD={g1,g2,…,gn}中進(jìn)行子圖匹配查詢,返回每個(gè)查詢qx的結(jié)果集:

RSqx={g∈GD|qx是g的同構(gòu)子圖}

3 子圖查詢算法

本文算法最大的特點(diǎn)是雙索引結(jié)構(gòu)。傳統(tǒng)的子圖搜索方法大多只在數(shù)據(jù)庫(kù)上建立索引,并且單獨(dú)地處理每個(gè)查詢。而本文利用查詢之間可能存在的相似性,在查詢流上動(dòng)態(tài)地建立查詢流索引,與數(shù)據(jù)庫(kù)索引結(jié)合成為基于雙索引的子圖查詢方法。本文的雙索引都是基于頻繁子圖,且索引指向的都是數(shù)據(jù)庫(kù)中的圖。

圖1為本文算法的子圖查詢流程:查詢流中的一個(gè)查詢q進(jìn)入處理窗口;在枚舉q的子圖過(guò)程中,依次與數(shù)據(jù)庫(kù)索引和查詢流索引進(jìn)行匹配過(guò)濾;同時(shí),記錄在此過(guò)程中涉及到的查詢流子圖;過(guò)濾后的候選集再進(jìn)行同構(gòu)檢測(cè),得到查詢q的結(jié)果集;查詢q的結(jié)果集作為涉及到的查詢流子圖的必要集更新到查詢流索引中,同時(shí),達(dá)到頻繁條件的查詢流索引圖將計(jì)算其支持集。

圖1 子圖查詢算法總流程

3.1 數(shù)據(jù)庫(kù)索引

定義5(數(shù)據(jù)庫(kù)頻繁子圖) 給定一個(gè)圖數(shù)據(jù)庫(kù)GD={g1,g2,…,gn},且給定一個(gè)頻繁系數(shù)δd,如果一個(gè)子圖g在圖數(shù)據(jù)庫(kù)GD中的支持度support(g)≥δd×|GDg|,那么則稱子圖g為數(shù)據(jù)庫(kù)頻繁子圖。

頻繁子圖的概念是相對(duì)的,一個(gè)圖是否頻繁取決于頻繁系數(shù)δd的設(shè)定。

3.1.1 索引結(jié)構(gòu)

本文采用類似于經(jīng)典的gSpan[10]頻繁子圖挖掘算法對(duì)圖數(shù)據(jù)庫(kù)進(jìn)行候選圖的生成與挖掘。圖2是由一個(gè)圖數(shù)據(jù)庫(kù)生成的部分候選圖,圖標(biāo)號(hào)右邊的數(shù)字表示的是子圖在數(shù)據(jù)庫(kù)中的支持度。

圖2 數(shù)據(jù)庫(kù)頻繁子圖的候選圖

采用樹形結(jié)構(gòu)對(duì)頻繁子圖進(jìn)行管理。圖3是基于圖2中的候選圖建立的數(shù)據(jù)庫(kù)索引樹。樹中,每個(gè)結(jié)點(diǎn)表示一個(gè)候選圖;在第LX層的子圖有X條邊;樹的根結(jié)點(diǎn)為空集;L0層的圖只有一個(gè)結(jié)點(diǎn),沒(méi)有邊;一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)是它擴(kuò)展一條邊后的超圖。

圖3 數(shù)據(jù)庫(kù)索引樹

在本文的例子中,圖數(shù)據(jù)庫(kù)的大小為1 000,如果頻繁系數(shù)δd定義為0.3,那么圖3中灰色結(jié)點(diǎn)為頻繁子圖,這些頻繁子圖將被最終編入數(shù)據(jù)庫(kù)索引;白色結(jié)點(diǎn)為非頻繁子圖,將被直接剪枝。下一小節(jié)將具體說(shuō)明索引樹的建立過(guò)程。

3.1.2 索引建立

確定頻繁系數(shù)δd后,開始對(duì)圖數(shù)據(jù)庫(kù)GD進(jìn)行數(shù)據(jù)庫(kù)索引的建立:

(1)標(biāo)號(hào)映射。把數(shù)據(jù)庫(kù)中圖的結(jié)點(diǎn)標(biāo)號(hào)和邊標(biāo)號(hào)按出現(xiàn)頻率升序排序,出現(xiàn)頻次小于δd×|GDg|的結(jié)點(diǎn)和邊可以直接從枚舉過(guò)程中排除(因?yàn)榘@些結(jié)點(diǎn)或者邊的子圖肯定不是頻繁子圖),其余標(biāo)號(hào)按出現(xiàn)頻率升序映射到一個(gè)字典序。這樣做的優(yōu)點(diǎn)在于:在挖掘過(guò)程中對(duì)非頻繁子圖能更早地剪枝;且同一子圖在進(jìn)行支持集計(jì)算時(shí)能大量減少同構(gòu)檢測(cè)次數(shù)。

(2)按字典序。對(duì)只有一個(gè)結(jié)點(diǎn)的圖(L0層)建立以其為樹根的索引樹。

(3)邊擴(kuò)展。按DFS碼[10]遞增的順序,將當(dāng)前子圖進(jìn)行邊擴(kuò)展。比如,在本文的例子中,圖2中的圖f1為結(jié)點(diǎn)A擴(kuò)展一條標(biāo)號(hào)為a的邊生成的子圖(采用DFS碼遞增的方法可以大量避免同一個(gè)圖的重復(fù)枚舉。詳細(xì)見(jiàn)文獻(xiàn)[10])。

(4)支持度計(jì)算。在計(jì)算擴(kuò)展子圖f的支持度時(shí),并不需要對(duì)整個(gè)數(shù)據(jù)庫(kù)圖進(jìn)行同構(gòu)檢測(cè),擴(kuò)展子圖父結(jié)點(diǎn)的支持集就是f的候選集。比如在計(jì)算圖3中候選圖f3的支持集時(shí),它的候選集就是f2的支持集。

如果當(dāng)前擴(kuò)展子圖f是頻繁子圖,則將其加入數(shù)據(jù)庫(kù)索引樹,并且以子圖f為當(dāng)前子圖回到算法第(3)步。

如果當(dāng)前擴(kuò)展子圖f不是頻繁子圖,則直接將其剪枝,因?yàn)樗某瑘D也不可能是頻繁的。接下來(lái)以擴(kuò)展子圖f的父結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)回到算法第(3)步。

(5)當(dāng)所有以單結(jié)點(diǎn)圖(L0層)為根的樹建立完成后,算法結(jié)束。

3.1.3 具體實(shí)現(xiàn)

在具體的實(shí)現(xiàn)中,本文采用哈希表來(lái)幫助快速定位樹中的頻繁子圖以及它們的支持集。圖結(jié)構(gòu)本身很難進(jìn)行直接哈希,此處再次利用了DFS碼。每個(gè)頻繁子圖可以轉(zhuǎn)換成一個(gè)由字符串表示的最小DFS碼,比如圖 2中f4的最小 DFS碼為: 01AaB02AaB03AaB。除了以上提到的快速定位,使用DFS碼的優(yōu)點(diǎn)還在于:

(1)在頻繁子圖挖掘過(guò)程中,可以避免枚舉子圖的遺漏和重復(fù)。

(2)當(dāng)需要檢測(cè)兩個(gè)圖是否相同時(shí),只需進(jìn)行簡(jiǎn)單的字符串匹配,而不是時(shí)間開銷很大的同構(gòu)檢測(cè)。

3.2 查詢流索引

在建立查詢流索之前,先要明確查詢流索引中頻繁子圖的定義。查詢流中頻繁的概念與數(shù)據(jù)庫(kù)并不相同,那是因?yàn)閿?shù)據(jù)庫(kù)是靜態(tài)的,而查詢流是源源不斷的動(dòng)態(tài)變化著。一個(gè)子圖在數(shù)據(jù)庫(kù)中是否頻繁非常明確:support(g)≥δd|GDg|(定義5),但是查詢流的大小|QS|一直在增長(zhǎng),顯然查詢流不能像數(shù)據(jù)庫(kù)那樣定義頻繁子圖。這里引入一個(gè)時(shí)間窗的概念。籠統(tǒng)地講,用戶只對(duì)當(dāng)前時(shí)間窗內(nèi)的查詢流感興趣,而頻繁子圖的概念也相對(duì)于當(dāng)前時(shí)間窗口內(nèi)的查詢流。

定義6(歷史支持度、當(dāng)前支持度) 給定一個(gè)查詢流QS={q1,q2,…,qn,…}和一個(gè)時(shí)間窗口大小window_size,當(dāng)前查詢?yōu)閝n。

一個(gè)查詢流索引中的結(jié)點(diǎn)f的歷史支持度為:

support_hisf=|{qi∈QS|f是qi的同構(gòu)子圖,且(?n/window_size」-1)×window_size＜i≤?n/ window_size」×window_size|

f的當(dāng)前支持度為:

support_curf=|{qi∈QS|f是qi的同構(gòu)子圖,且?n/window_size」×window_size＜i≤n}|+support_hisf

定義7(查詢流頻繁子圖) 給定時(shí)間窗口大小window_size和查詢流頻繁系數(shù)δq,如果一個(gè)查詢流索引中的結(jié)點(diǎn)f的當(dāng)前支持度support_curf≥δq×window_size,那么f被稱為查詢流頻繁子圖。

從定義7注意到,當(dāng)前支持度中包含了歷史支持度。在理想狀態(tài)下,希望記錄一個(gè)子圖f在時(shí)間窗口內(nèi)精確的支持度。但為了精確,必須記錄下f在查詢流中每次出現(xiàn)的查詢序列號(hào),空間消耗較大。所以本文給出了當(dāng)前支持度的近似定義。

除了頻繁子圖的定義不同,查詢流索引的另一個(gè)重要問(wèn)題是其動(dòng)態(tài)增長(zhǎng)性。查詢流持續(xù)不斷地進(jìn)入處理窗口,相應(yīng)的查詢流索引也會(huì)越來(lái)越大。為了控制查詢流索引的規(guī)模,引入了時(shí)間戳的概念。

定義8(時(shí)間戳) 假設(shè)查詢流QS={q1,q2,…,qn,…},1,2,…,n,…,為每個(gè)查詢的序列號(hào)。查詢流索引中的每個(gè)結(jié)點(diǎn)S都有一個(gè)時(shí)間戳timeS,其值為最后一次出現(xiàn)在查詢流中的查詢序列號(hào)。

在每個(gè)時(shí)間窗口結(jié)束時(shí),掃描整個(gè)查詢流索引,將時(shí)間戳小于當(dāng)前窗口的結(jié)點(diǎn)刪除。

3.2.1 索引結(jié)構(gòu)

數(shù)據(jù)庫(kù)索引中存儲(chǔ)的都是頻繁子圖,但查詢流索引中存儲(chǔ)的不僅僅是頻繁子圖,也存儲(chǔ)那些將來(lái)可能會(huì)變成頻繁的子圖。這些潛在頻繁子圖并沒(méi)有準(zhǔn)確地計(jì)算出支持集,而在將來(lái)某一刻它變成頻繁子圖時(shí),需要借助它的子圖的支持集來(lái)作為它的候選集進(jìn)行支持集計(jì)算。而已知支持集的子圖越多,需要進(jìn)行同構(gòu)檢測(cè)的候選集就越小。所以,在查詢流索引中很有必要記錄它與多個(gè)子圖的包含關(guān)系。

另外,在查詢流中頻繁的子圖也有可能在數(shù)據(jù)庫(kù)中是頻繁的。為了減少重復(fù)的計(jì)算和存儲(chǔ),以及充分地利用數(shù)據(jù)庫(kù)索引中的信息,采取數(shù)據(jù)庫(kù)索引和查詢流索引信息共享的數(shù)據(jù)結(jié)構(gòu)。

圖4是一個(gè)查詢流索引的示例,圖中圓形結(jié)點(diǎn)為數(shù)據(jù)庫(kù)索引中的頻繁子圖(圖3);方形結(jié)點(diǎn)為查詢流索引中的子圖,其中灰色結(jié)點(diǎn)為頻繁子圖且已經(jīng)計(jì)算出支持集;白色結(jié)點(diǎn)為非頻繁子圖;圖中連接方形結(jié)點(diǎn)的虛線表示2個(gè)結(jié)點(diǎn)的子圖同構(gòu)關(guān)系。從圖中可以看到與數(shù)據(jù)庫(kù)索引的區(qū)別:索引中的每個(gè)結(jié)點(diǎn)會(huì)有不止一個(gè)父親結(jié)點(diǎn)。這樣設(shè)計(jì)的好處在于可以縮小索引圖的候選集大小。比如圖中f2達(dá)到頻繁子圖條件時(shí),其候選集CSf′2=SSf′1∩SSf′2,父結(jié)點(diǎn)越多,候選集越小。

圖4 查詢流索引

3.2.2 索引建立與子圖查詢

查詢流索引的建立與子圖查詢的處理過(guò)程是互相交織在一起的。處理查詢的大致步驟為:枚舉,過(guò)濾和驗(yàn)證:

(1)枚舉查詢q的所有邊長(zhǎng)小于Lmax的子圖集SD,與數(shù)據(jù)庫(kù)索引和查詢流索引進(jìn)行匹配,匹配的結(jié)果有4種:

1)子圖在數(shù)據(jù)庫(kù)索引中(子集SD1);

2)子圖在查詢流索引中,且已經(jīng)是頻繁子圖(子集SD2);

3)子圖在查詢流索引中,但還沒(méi)有達(dá)到頻繁的條件,則將其當(dāng)前支持度加1(子集SD3);

4)子圖既不在數(shù)據(jù)庫(kù)索引也不在查詢流索引中,則將其添加到查詢流索引中,當(dāng)前支持度為1 (子集SD4)。

(2)把子圖集 SD中的所有頻繁子圖(SD1+SD2)的支持集作交,作為查詢q的候選集。

(3)在候選集上進(jìn)行子圖同構(gòu)檢測(cè),得到查詢q的結(jié)果集。

(4)查詢q的結(jié)果集作為子圖集SD中部分子圖(SD3+SD4)的必要集,更新到查詢流索引中。如果SD中有子圖達(dá)到查詢流頻繁的條件,則計(jì)算其支持集。

(5)定期掃描查詢流索引,刪除超出時(shí)間窗外的子圖,防止查詢流索引的無(wú)休止增長(zhǎng)。

圖5、圖6是一個(gè)包括了查詢流索引更新的子圖查詢示例。查詢q進(jìn)入處理窗口后,對(duì)其進(jìn)行子圖枚舉(圖5中q.0～q.5),得到的匹配結(jié)果為:

得到查詢q的候選集為:

在CSq上進(jìn)行同構(gòu)檢測(cè)后,得到查詢q的結(jié)構(gòu)集RSq。將RSq作為SD3和SD4中子圖的必要集更新到數(shù)據(jù)庫(kù)中。

圖5 查詢q及其枚舉子圖

圖6 處理查詢q后更新的雙索引結(jié)構(gòu)

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

本文將與2個(gè)經(jīng)典的子圖搜索算法FG-Index[9]和GCoding[11]進(jìn)行實(shí)驗(yàn)比較,以驗(yàn)證本文算法的可行性。實(shí)驗(yàn)環(huán)境為Intel i5 2.5 GHz CPU,8 GB內(nèi)存,64位Linux系統(tǒng)。

本文采用的實(shí)驗(yàn)集為生物領(lǐng)域的AIDS數(shù)據(jù)庫(kù),該數(shù)據(jù)庫(kù)包含1萬(wàn)個(gè)分子圖。實(shí)驗(yàn)中的查詢流是根據(jù)AIDS數(shù)據(jù)庫(kù)隨機(jī)生成,按邊數(shù)(4,8,12,16,20)等比例生成后進(jìn)行混合。在實(shí)驗(yàn)中,查詢流按查詢個(gè)數(shù)分為1 000～6 000。數(shù)據(jù)庫(kù)頻繁系數(shù)δd為0.1;查詢流頻繁系數(shù)δq為0.01;最大頻繁子圖邊數(shù)Lmax為4;時(shí)間窗口window_size為500。

圖7顯示了平均查詢時(shí)間隨著查詢流大小增加的變化曲線。從實(shí)驗(yàn)結(jié)果可看出,本文算法相較于傳統(tǒng)算法具有以下優(yōu)勢(shì):隨著查詢流中所含查詢數(shù)量的增加,查詢之間的相似性被充分挖掘,查詢流索引中存儲(chǔ)了更多有用的信息,平均的查詢時(shí)間開銷就會(huì)隨之降低。

圖7 平均查詢時(shí)間隨查詢流大小的變化曲線

圖8顯示了平均候選集大小隨著查詢流大小增加的變化曲線。這里的候選集大小是以同構(gòu)檢測(cè)的次數(shù)來(lái)計(jì)量。從圖中可以看到:在查詢流較小時(shí),候選集大小相對(duì)較大。其主要原因在于:在建立查詢流索引的過(guò)程中,進(jìn)行了查詢流頻繁子圖的支持集計(jì)算,其中包含了大量同構(gòu)檢測(cè)計(jì)算。這在查詢流較小時(shí),會(huì)產(chǎn)生額外的同構(gòu)檢測(cè)次數(shù)。但隨著查詢流的增大,處理查詢前期建立的查詢流索引為后來(lái)的查詢提供了大量的有用信息,降低了平均的候選集大小。

圖8 平均候選集大小隨查詢流大小的變化曲線

5 結(jié)束語(yǔ)

本文提出一種基于雙索引的子圖搜索算法,相較于傳統(tǒng)算法,本文算法引入了查詢流索引,采用時(shí)間窗的概念定義了查詢流頻繁子圖,時(shí)間窗的概念不僅控制了索引的規(guī)模也實(shí)時(shí)地反映了查詢興趣。在子圖查詢過(guò)程中,提高了總的查詢效率。下一步的研究方向?qū)⒅赜诓樵兞魉饕膬?yōu)化,減少查詢流索引產(chǎn)生的額外空間開銷,提高挖掘出的查詢流頻繁子圖的質(zhì)量,加速查詢流索引的建立。

[1] 彭佳揚(yáng),楊路明,王建新,等.一種高效挖掘生物網(wǎng)絡(luò)閉合頻繁子圖的算法[J].高技術(shù)通訊,2009,19(2): 188-193.

[2] 樓宇波,馬 堅(jiān),周皓峰,等.基于頻繁鏈接的Web權(quán)威資源挖掘[J].計(jì)算機(jī)研究與發(fā)展,2003,40(7):1095-1103.

[3] Johnson D S,Garey M R.Computers and Intractability: A Guide to the Theory of Np-completeness[M]. [S.1.]:W.H.Freeman and Company,1979.

[4] Giugno R,Shasha D.GraphGrep:A Fast and Universal Method for Querying Graphs[C]//Proceedings of ICPR’02.Quebec,Canada:IEEE Press,2002:123-129.

[5] Zhao Peixiang,Yu J X,Yu P S.Graph Indexing:Tree+delta＞=graph[C]//Proceedings of VLDB’2007. [S.1.]:IEEE Press,2007:233-241.

[6] Klein K,Kriege N,Mutzel P.CT-Index:Fingerprint-based Graph Indexing Combining Cycles and Trees[C]// Proceedings of ICDE’11.Hannover,Germany:IEEE Press, 2011:258-265.

[7] 李先通,李建中,高 宏.一種高效頻繁子圖挖掘算法[J].軟件學(xué)報(bào),2007,18(10):2469-2480.

[8] Yan Xifeng,Yu P S,Han Jiawei.Graph Indexing:A Frequent Structure-based Approach[C]//Proceedings of SIGMOD’04.Paris,France:ACM Press,2004:568-576.

[9] Cheng J,Ke Y,Ng A,et al.FG-index:Towards Verification-free Query Processing on Graph Data-bases[C]//Proceedings of SIGMOD’07.Beijing,China:[s.n.],2007: 541-549.

[10] Yan Xifeng,Han Jiawei.gSpan:Graph-based Substructure Pattern Mining[C]//Proceedings of ICDM’02.Maebashi, Japan:IEEE Press,2002:236-246.

[11] Zou Lei,Chen Lei,Xu J,et al.A Novel Spectral Coding in A LargeGraph Database[C]//Proceedingsof EDBT’08.Nantes,France:ACM Press,2008:321-329.

編輯 索書志

Subgraph Query Algorithm Based on Dual Index

LU Huilin,HUANG Bo
(Key Lab of Intelligent Information Processing,School of Computer Science,Fudan University,Shanghai 200433,China)

Most traditional subgraph query algorithms only conduct a mine-at-once algorithm on the graph database. That is,after establishing a stable database index,the index is no longer be updated.This kind of algorithms may encounter such problems:with the query interest frequently changing or the database frequently updating,the original database index becomes increasingly obsolete and no longer provides useful information to effectively reduce the number of candidate graphs.Based on this consideration,this paper proposes a dual index structure which mines frequent subgraphs on the database and the query stream,and establishes index on them.The process of subgraph query and the establishment of query index are simultaneous.They complement each other.So even if the query interest changes,the query stream index can be adaptively updated to optimize the query performance.For the frequent updates of database,the database index doesnot need to be re-built,because the query stream index provides useful information in real time. Experimental results show that the dual index improves the processing efficiency of subgraph query.

dual index;query stream index;subgraph query;frequent subgraph;graph database;subgraph isomorphism

1000-3428(2015)01-0044-05

A

TP391

10.3969/j.issn.1000-3428.2015.01.008

陸慧琳(1988-),女,碩士研究生,主研方向:數(shù)據(jù)庫(kù)技術(shù),數(shù)據(jù)挖掘;黃 博,碩士。

2014-03-05

2014-04-03 E-mail:luhuilin@fudan.edu.cn

中文引用格式:陸慧琳,黃 博.基于雙索引的子圖查詢算法[J].計(jì)算機(jī)工程,2015,41(1):44-48.

英文引用格式:Lu Huilin,Huang Bo.Subgraph Query Algorithm Based on Dual Index[J].Computer Engineering,2015, 41(1):44-48.