標(biāo)簽約束可達(dá)查詢的高效處理方法

杜 明 楊 云 周軍鋒 陳子陽 楊安平

1(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 201620) 2(上海立信會計(jì)金融學(xué)院信息管理學(xué)院 上海 201620)duming@dhu.edu.cn)

可達(dá)性查詢是數(shù)據(jù)圖上的基本操作之一，用于回答有向圖中指定的2個頂點(diǎn)間是否存在有向路徑，在過去一段時間得到了深入研究[1-16].可達(dá)性查詢可用于社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、語義網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等檢測指定的兩點(diǎn)間是否存在某種特定聯(lián)系，也可作為基本的原子操作，協(xié)助回答圖上的結(jié)構(gòu)化查詢，如XQuery或者SPARQL(SPARQL protocol and RDF query language)表達(dá)式.隨著實(shí)際應(yīng)用中圖規(guī)模不斷增大和查詢約束條件的增加，可達(dá)性查詢的處理方法也需要支持更多的查詢約束條件.例如，在實(shí)際的數(shù)據(jù)圖中，每條邊除了表示兩點(diǎn)之間直接可達(dá)的關(guān)系外，還常常附帶有表示關(guān)系特征的文本標(biāo)簽.用戶在查詢時除了關(guān)心兩點(diǎn)之間是否可達(dá)外，可能想更進(jìn)一步知道兩點(diǎn)之間可達(dá)路徑上的文本標(biāo)簽是否滿足指定的標(biāo)簽約束[17-22].類似的查詢有：從哈爾濱出發(fā)僅通過高速路是否能到達(dá)廣州，用戶A和用戶B的聯(lián)系是否與工程或者學(xué)術(shù)相關(guān)，用戶A和用戶B是否存在師生或者血緣上的關(guān)聯(lián)等.這些問題被稱為標(biāo)簽約束可達(dá)查詢的處理問題.

為了回答標(biāo)簽約束的可達(dá)性查詢，研究者提出了多種索引技術(shù)來加速查詢響應(yīng)的速度[17-22]，其中最新工作是文獻(xiàn)[21]提出的基于地標(biāo)索引的方法.該方法選擇k個地標(biāo)點(diǎn)，然后建立2種索引：1)每個地標(biāo)點(diǎn)的可達(dá)點(diǎn)及其最小路徑標(biāo)簽集；2)非地標(biāo)點(diǎn)的部分可達(dá)點(diǎn)及其路徑標(biāo)簽集.查詢處理時，如果索引可回答查詢，則返回結(jié)果；否則需要通過圖遍歷操作得到結(jié)果.實(shí)際中，該方法建立的索引的可達(dá)信息覆蓋率較低，需要執(zhí)行昂貴的圖遍歷操作.

針對以上問題，本文首先提出一種基于部分點(diǎn)的雙向路徑標(biāo)簽索引方法，不僅顯著提升可達(dá)信息的覆蓋率，而且索引規(guī)模顯著降低.該方法的提出基于以下觀察：假設(shè)頂點(diǎn)v可達(dá)的頂點(diǎn)集是N，M是可達(dá)v的頂點(diǎn)集，則基于本文的方法，處理v記錄的可達(dá)頂點(diǎn)對數(shù)量是|M|×|N|+|M|+|N|，而文獻(xiàn)[21]構(gòu)建的是單向索引，僅記錄|N|個可達(dá)頂點(diǎn)對信息.基于本文的雙向索引處理查詢可顯著減少圖遍歷的代價，提升系統(tǒng)性能.其次，本文提出一種基于標(biāo)簽集合包含關(guān)系的壓縮優(yōu)化策略，進(jìn)一步減少索引規(guī)模.在此基礎(chǔ)上，本文提出一種完全索引技術(shù)，用以記錄所有頂點(diǎn)對的可達(dá)信息，從而在查詢處理時完全避免圖遍歷操作.最后，基于真實(shí)數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了本文所提方法的高效性.

1 背景知識及相關(guān)工作

1.1 相關(guān)概念

本文處理的是有向無環(huán)標(biāo)簽圖，對于有環(huán)的情況，可通過借鑒文獻(xiàn)[20]的方法進(jìn)行處理,將其轉(zhuǎn)換為無環(huán)圖.一個有向無環(huán)圖中的有向邊體現(xiàn)了頂點(diǎn)間的可達(dá)偏序關(guān)系，通過拓?fù)渑判蚩蓪㈨旤c(diǎn)的偏序關(guān)系全序化，拓?fù)涮柤礊槿蜿P(guān)系的序號.拓?fù)渑判蜻^程中，對于每個被處理頂點(diǎn)s建立1個拓?fù)涮朮(s)，則對圖中任意從s到t的有向邊(s,t)來說，有X(s)X(t)成立，則s不可達(dá)t.

假設(shè)Lp={a1,a2,…,an},后續(xù)討論中,為了簡化表示,在上下文允許的情況下,本文以字符串的形式表示Lp,即Lp=a1a2…an.假設(shè)Lpi=a1a2…ai且Lpi?Lp,則該關(guān)系也可在上下文允許的情況下表示為a1a2…ai?a1a2…an.表1列出了本文經(jīng)常使用的符號及其意義.

Table 1 The Symbols Used in This Paper and Description表1 本文所用符號及其意義

1.2 相關(guān)工作

1.2.1 無約束的可達(dá)性查詢

該類查詢主要用于判斷從源點(diǎn)到目標(biāo)點(diǎn)是否存在路徑.在最新的研究中[14-16],文獻(xiàn)[14]討論了2hop label的并行構(gòu)建策略，主要用于回答最短路徑和一般無約束的可達(dá)查詢.文獻(xiàn)[15]討論了大圖上的近似可達(dá)查詢處理問題，并提供了近似解決方案.文獻(xiàn)[16]改進(jìn)了2hop label以便加速時態(tài)圖上的最快路徑查詢.以上文獻(xiàn)均無法用來回答標(biāo)簽約束的可達(dá)查詢，和本文方法沒有可比性.

1.2.2 對點(diǎn)和邊都進(jìn)行標(biāo)簽約束的可達(dá)性查詢

該類查詢對路徑上的點(diǎn)和邊都進(jìn)行約束,并且點(diǎn)和邊具有多個標(biāo)簽，主要用于判斷從源點(diǎn)到目標(biāo)點(diǎn)是否存在路徑，并且路徑上所有點(diǎn)和邊的標(biāo)簽都滿足給定的標(biāo)簽約束.針對該類查詢，文獻(xiàn)[17]中提出在二級存儲框架中開發(fā)，將圖形拓?fù)浯鎯υ谥鞔鎯χ校瑯?biāo)簽信息存儲在輔助存儲中.Yung等人[17]提出一種基于散列映射的算法，其基本思想是利用“完美”散列函數(shù)將頂點(diǎn)和邊的多個標(biāo)簽映射成散列值，并將散列值存儲在主存儲器中.查詢時，從源點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷(breadth first search, BFS)深度優(yōu)先遍歷(depth first search, DFS)，遍歷的過程中驗(yàn)證散列值.對于可能存在散列沖突的頂點(diǎn)或邊，則需訪問輔助存儲器中存儲的標(biāo)簽，通過比對標(biāo)簽決定是否繼續(xù)遍歷該分支.最終篩選滿足約束的點(diǎn)和邊進(jìn)行遍歷，直至到達(dá)終點(diǎn)返回可達(dá)或者中途就停止了遍歷返回不可達(dá).

1.2.3 僅對邊進(jìn)行標(biāo)簽約束的可達(dá)性查詢

該類查詢主要用于判斷給定2個頂點(diǎn)是否存在有向路徑，且路徑中每條邊的標(biāo)簽僅使用預(yù)定義標(biāo)簽集中的標(biāo)簽.針對該類查詢，研究者們提出多種不同的解決方法，主要有4種:

1) 基于生成樹索引方法

文獻(xiàn)[19]提出一個基于樹狀結(jié)構(gòu)的索引框架.首先定義了2個頂點(diǎn)間的最小路徑標(biāo)簽集，然后利用有向最大權(quán)生成樹算法和采樣技術(shù)為圖G生成一棵有向生成樹T，同時對非樹邊建立一個包含標(biāo)簽集壓縮的部分傳遞閉包NT.基于T，圖中的所有路徑被劃分為3組Ps,Pe,Pn.Ps包含所有成對路徑，其中第1條邊是T的一部分；Pe包含所有成對路徑，其中最后1條邊是T的一部分；Pn包含所有成對路徑，其中第1條和最后1條邊都不在T中.NT(u,v)包含u和v之間的Pn中路徑的所有路徑標(biāo)簽.實(shí)際上，該方法是在無約束可達(dá)查詢的樹狀索引基礎(chǔ)上，增加了標(biāo)簽集約束實(shí)現(xiàn)的，因此該算法存在很多冗余路徑并且具有樹狀索引對稠密圖處理效率較低問題.

2) 基于二分圖索引方法

文獻(xiàn)[20]提出利用強(qiáng)連通分量(strong connected component, SCC)將圖轉(zhuǎn)換為二分圖來實(shí)現(xiàn)標(biāo)簽約束可達(dá)性查詢.首先將圖G分解為強(qiáng)連通分量C1,C2,…,Ck，并計(jì)算每個Ci的局部傳遞閉包，即Ci中每個頂點(diǎn)到其他點(diǎn)的最短路徑標(biāo)簽集.其次，用二分圖Bi替代每個Ci，將其轉(zhuǎn)化成帶有標(biāo)簽的增強(qiáng)有向無環(huán)圖(augmented directed acyclic graph， ADAG)Ga,d,a，并根據(jù)逆拓?fù)渑判虻捻樞蛞来斡?jì)算Ga,d,a中的每個頂點(diǎn)u的最短路徑標(biāo)簽集.最后，計(jì)算每個u(u∈Ci,u?Ga,d,a)的最短路徑標(biāo)簽集.該方法得到的索引保存了圖中每個頂點(diǎn)的完整可達(dá)性信息，即標(biāo)簽圖的完全傳遞閉包.因此查詢應(yīng)答相當(dāng)于索引中的簡單查找，但索引構(gòu)建時間過長，索引規(guī)模過大.

3) 基于地標(biāo)點(diǎn)索引方法

文獻(xiàn)[21]提出選擇地標(biāo)點(diǎn)建立索引，并維護(hù)其傳遞閉包中頂點(diǎn)可達(dá)信息的地標(biāo)索引(landmark index， LI+)方法.具體來說，將圖中頂點(diǎn)按出度與入度總和降序排列，并選擇前k個點(diǎn)作為地標(biāo)頂點(diǎn).對于地標(biāo)點(diǎn)，計(jì)算其到其他點(diǎn)的最小路徑標(biāo)簽集，并利用輔助索引重新組織部分地標(biāo)索引；對于非地標(biāo)點(diǎn),計(jì)算部分路徑標(biāo)簽集.查詢時，如果該條查詢的源點(diǎn)是地標(biāo)點(diǎn)，則查找地標(biāo)索引進(jìn)行回答，否則查找非地標(biāo)索引.若也不能通過非地標(biāo)點(diǎn)索引回答,則執(zhí)行遍歷，遍歷過程中可以通過輔助索引進(jìn)行剪枝.該方法的主要缺點(diǎn)是索引的可達(dá)信息覆蓋率低，圖遍歷代價高.

4) 基于隨機(jī)游走的采樣算法

文獻(xiàn)[22]基于隨機(jī)游走的采樣算法來回答具有全范圍正則表達(dá)式約束的可達(dá)性查詢，且可擴(kuò)展到大圖，但該算法提供的是非精確解的近似解決方案,和本文方法不具有可比性.

2 基于部分點(diǎn)的雙向索引

文獻(xiàn)[21]通過構(gòu)建k個地標(biāo)點(diǎn)的單向可達(dá)索引來回答查詢.假設(shè)頂點(diǎn)v可達(dá)的頂點(diǎn)集是N，則1個地標(biāo)點(diǎn)對應(yīng)的索引僅能回答v與|N|個點(diǎn)的可達(dá)關(guān)系.由于k值與圖中頂點(diǎn)數(shù)量相比較小，通常情況下文獻(xiàn)[21]提出的單向地標(biāo)索引的可達(dá)信息覆蓋率低，查詢過程中不可避免需要執(zhí)行大量昂貴的遍歷操作.針對該問題，本文提出通過構(gòu)建v的雙向路徑標(biāo)簽索引來提升索引的可達(dá)信息覆蓋率.假設(shè)M是可達(dá)v的頂點(diǎn)集，則基于本文的方法，處理v記錄的可達(dá)頂點(diǎn)對數(shù)量是|M|×|N|+|M|+|N|，其中M中的頂點(diǎn)通過v可達(dá)N中頂點(diǎn)，且可達(dá)頂點(diǎn)對數(shù)量為|M|×|N|，|M|表示M中頂點(diǎn)和v的可達(dá)頂點(diǎn)對數(shù)量，|N|表示v和N中頂點(diǎn)的可達(dá)頂點(diǎn)對數(shù)量.下面具體介紹該索引的構(gòu)建方法.

2.1 索引構(gòu)建

2.1.1 基本思想

Fig. 1 Labeled DAG G圖1 有向無環(huán)標(biāo)簽圖G

Table 2 The Initial Path Label Index for Fig. 1表2 初始路徑標(biāo)簽索引

針對以上問題，本文僅構(gòu)建基于k個頂點(diǎn)的標(biāo)簽索引來減小索引規(guī)模，同時提出2種優(yōu)化方法來降低索引規(guī)模.下面具體介紹.

定理1.給定頂點(diǎn)v，在基于v建立標(biāo)簽索引的過程中，如果遇到已處理過的地標(biāo)點(diǎn)u，則無需從u繼續(xù)遍歷.

證明. 首先，在處理u的過程中，已經(jīng)記錄了所有u到u可達(dá)頂點(diǎn)的路徑標(biāo)簽以及可達(dá)u的頂點(diǎn)到u之間的路徑標(biāo)簽.其次，在處理v時，如果遍歷過程中遇到了u，一方面，在處理u時已經(jīng)得到v和u之間路徑的標(biāo)簽，另一方面，如圖2所示，對u可達(dá)的任意頂點(diǎn)x，處理u時已經(jīng)得到了兩者之間的路徑標(biāo)簽.處理v時，如果沿著u繼續(xù)遍歷到x，則得到的標(biāo)簽等價于u到x已經(jīng)得到的標(biāo)簽與v到u之間路徑標(biāo)簽的并集.由于這些信息已經(jīng)具備，因此無需專門記錄v到x的路徑標(biāo)簽.

證畢.

Fig. 2 Illustration of landmark nodes圖2 地標(biāo)點(diǎn)作用示意圖

定理2.給定頂點(diǎn)v，在基于v建立標(biāo)簽索引的過程中，對于遍歷到的頂點(diǎn)w滿足：1)v可達(dá)w，路徑標(biāo)簽是L1；2)v和w之間通過遍歷非地標(biāo)點(diǎn)得到的路徑標(biāo)簽是L2.如果L2?L1，則無需從w出發(fā)繼續(xù)遍歷.

證明. 如圖2所示，從v出發(fā)建立標(biāo)簽索引.當(dāng)遍歷到w時，發(fā)現(xiàn)v可達(dá)w，其路徑標(biāo)簽是L1=l1∪l2，且v通過非地標(biāo)點(diǎn)遍歷到w的路徑標(biāo)簽是L，如果L1?L成立，說明對于w之后遍歷到的任一點(diǎn)x，v通過直接遍歷得到的路徑標(biāo)簽是L∪l3，而通過u計(jì)算得到的路徑標(biāo)簽是L1∪l3，可知通過非地標(biāo)點(diǎn)得到的標(biāo)簽始終是通過地標(biāo)點(diǎn)的超集，因此無需從w繼續(xù)遍歷.

證畢.

針對圖1，假設(shè)選擇2個地標(biāo)點(diǎn)v2和v1，處理順序是先v2后v1，則基于上述2種優(yōu)化方法構(gòu)建的路徑標(biāo)簽索引如表3所示.例如，處理完v2再處理v1時，通過BFS遍歷到v2，由于v2已被處理過，由定理1可得，不更新索引且停止該條分支的遍歷，并開始下一條分支的遍歷.當(dāng)BFS通過路徑v1,v3,v5遍歷到v5時，其路徑標(biāo)簽L=ab.由已構(gòu)建的索引可知，v1通過地標(biāo)點(diǎn)v2可達(dá)v5，對應(yīng)的路徑標(biāo)簽為L=a.因?yàn)長?L，由定理2得，不更新索引且無需從v5繼續(xù)遍歷.

Table 3 Optimized Path Label Index表3 優(yōu)化的路徑標(biāo)簽索引

2.1.2 索引構(gòu)建算法

算法1基于以上2個定理構(gòu)建雙向路徑標(biāo)簽索引(bidirectional path label index, BPLI).

本文采用文獻(xiàn)[23]中的策略，即按照(dout(v)+1)×(din(v)+1)遞減的順序?qū)D中頂點(diǎn)排序，選擇前k個地標(biāo)點(diǎn)(行①).對每個地標(biāo)點(diǎn)v，調(diào)用BiBFS(v)從正反2個方向進(jìn)行遍歷，分別建立被訪問頂點(diǎn)的inLabel和outLabel(行②③).在基于地標(biāo)點(diǎn)構(gòu)建路徑標(biāo)簽索引的過程中，同時應(yīng)用定理1和定理2進(jìn)行剪枝來減小索引規(guī)模.對于每個遍歷到的點(diǎn)，函數(shù)isSuperset(s,t,L)用于根據(jù)定理2以及定理1判斷是否還繼續(xù)遍歷該分支.

算法1的時間復(fù)雜度是O(|V|+|E|)，空間復(fù)雜度是O(|V|).因?yàn)橐粋€頂點(diǎn)進(jìn)行BFS操作的最壞代價是O(|V|+|E|)，而算法1僅僅處理了k個頂點(diǎn)(k是自定義的常數(shù))，因此，時間復(fù)雜度是O(|V|+|E|).此外，BFS操作需要借助一個輔助隊(duì)列，總的大小為O(|V|)，又每個頂點(diǎn)包含2個拓?fù)涮枺虼丝偟目臻g復(fù)雜度是O(|V|).

例2.對于圖1，根據(jù)(dout(v)+1)×(din(v)+1)對圖中頂點(diǎn)降序排列，得到的頂點(diǎn)順序?yàn)椋簐2→v1→v0→v3→v4→v5.假設(shè)選擇2個地標(biāo)點(diǎn)，則地標(biāo)點(diǎn)的處理順序是v2→v1.

1) 在處理v2時.初始化inLabel(v2)={(v2,?)}和outLabel(v2)={(v2,?)}.從v2出發(fā)執(zhí)行BFS遍歷到v4和v5，由于marked(v4)=0，需判斷outLabel(v2)與inLabel(v4)是否存在頂點(diǎn)交集.發(fā)現(xiàn)outLabel(v2)與inLabel(v4)沒有交集，因此將(v2,c)插入到inLabel(v4)中.同理，將(v2,a)插入到inLabel(v5)中.此時v2已沒有出鄰居，從v2出發(fā)執(zhí)行反向BFS遍歷到v0和v1.因?yàn)関0未被標(biāo)記且outLabel(v0)與inLabel(v2)沒有交集，將(v2,b)插入到outLabel(v0)中.同理，將(v2,a)插入到outLabel(v1)中.繼續(xù)反向BFS遍歷到v0，由已構(gòu)建的outLabel(v0)和inLabel(v2)可得L=b，而遍歷路徑v2,v1,v0的標(biāo)簽為L=ac.根據(jù)集合關(guān)系將(v2,ac)插入到outLabel(v0)中.至此，v2正反2個方向的遍歷結(jié)束，將其標(biāo)記為marked(v2)=1.

2) 在處理v1時.從v1出發(fā)執(zhí)行BFS遍歷到v2，由于v2已被標(biāo)記過，由定理1得，不更新索引并停止該分支的遍歷，開始下一分支的遍歷，即遍歷到v3.因?yàn)閛utLabel(v1)和inLabel(v3)沒有交集，將(v1,a)插入到inLabel(v3)中.繼續(xù)執(zhí)行BFS遍歷，經(jīng)過路徑v1,v3,v5遍歷到v5，對應(yīng)的路徑標(biāo)簽L=ab，由已構(gòu)建的索引知outLabel(v1)與inLabel(v5)的頂點(diǎn)交集為v2，對應(yīng)的標(biāo)簽取并集可得L=a.又L?L，由定理2得，不更新索引且無需從v5繼續(xù)遍歷.接下來，從v1出發(fā)執(zhí)行反向BFS遍歷到v0，因?yàn)関0未被標(biāo)記且outLabel(v0)與inLabel(v1)沒有交集，將(v1,c)插入到outLabel(v0)中.至此，v1正反2個方向的遍歷結(jié)束并標(biāo)記marked(v1)=1.因此，針對圖1建立的索引如表3所示.

2.2 查詢策略

給定查詢s→Lt，可通過求解outLabel(s)和inLabel(t)的交集來判斷s是否可達(dá)t.如果交集為空，說明s通過地標(biāo)點(diǎn)不可達(dá)t，需要進(jìn)行遍歷判斷是否可達(dá)；如果交集不為空，說明s可達(dá)t，需要進(jìn)一步檢測路徑標(biāo)簽是否滿足要求，具體檢測方法是對于交集中的每個點(diǎn)v，將L(s,v)與L(v,t)進(jìn)行合并，判斷合并的結(jié)果是否是L的子集.若是，則說明標(biāo)簽可達(dá)，否則需要進(jìn)行遍歷.

例如，當(dāng)給定查詢v1→abcv5時，outLabel(v1)與inLabel(v5)的頂點(diǎn)交集為v2，對應(yīng)的路徑標(biāo)簽L=a?abc，所以v1→abcv5.當(dāng)給定查詢v3→acv4時，outLabel(v3)與inLabel(v4)沒有交集，不能直接通過索引判斷，需要執(zhí)行遍歷得出v3acv4.

可以看出，基于部分地標(biāo)點(diǎn)構(gòu)建的路徑索引不能高效處理不可達(dá)查詢，為此本文進(jìn)一步利用文獻(xiàn)[13]中提出的基于棧的互逆拓?fù)漤樞蚍椒▉砜焖偬幚聿豢蛇_(dá)查詢.簡而言之，得出拓?fù)漤樞騒后，在構(gòu)建逆序拓?fù)漤樞験時，始終優(yōu)先訪問拓?fù)漤樞騒中拓?fù)涮栕畲笄宜腥豚従泳辉L問的頂點(diǎn).具體操作步驟見文獻(xiàn)[13]，此處不再贅述.

由文獻(xiàn)[13]可知，求解2個互逆拓?fù)漤樞虻臅r間代價為O(|V|+|E|)，且后文中索引大小包含了拓?fù)涮柕拇鎯﹂_銷.

3 基于所有點(diǎn)的雙向索引

由于算法1選擇k個頂點(diǎn)建立索引，對某些數(shù)據(jù)集而言，可能存在索引覆蓋率低的問題，并且當(dāng)索引判斷不了時還需要執(zhí)行遍歷操作.基于第2節(jié)給出的定理1和定理2，本文進(jìn)一步提出對所有點(diǎn)建立雙向路徑標(biāo)簽索引.由于這種索引可用于回答不可達(dá)查詢，因此基于所有點(diǎn)建立路徑標(biāo)簽索引時，不再需要拓?fù)湫蛱栠M(jìn)行過濾，且無需執(zhí)行圖上的遍歷操作.

基于第2節(jié)構(gòu)建路徑標(biāo)簽的思路為所有點(diǎn)構(gòu)建的路徑標(biāo)簽索引如表4所示.查詢算法如算法3所示.

Table 4 Path Label Index for All Nodes表4 所有點(diǎn)的路徑標(biāo)簽索引

該方法的時間復(fù)雜度為O(|V|×(|V|+|E|)×|Lmax|)，空間復(fù)雜度為O(|V|×|Lmax|)，這里|Lmax|表示所有頂點(diǎn)中最長的標(biāo)簽長度.雖然看起來時間復(fù)雜度較高，但實(shí)驗(yàn)結(jié)果顯示，由于剪枝技術(shù)的有效性，索引時間比現(xiàn)有方法更快.

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)所用機(jī)器的基本配置為Intel?CoreTMi5-6600 CPU@3.30 GHz，4 GB內(nèi)存，1 TB硬盤，操作系統(tǒng)為Linux Ubuntu 16.04.用于比較的算法包括基于遍歷的BFS算法、LI+算法[21]以及本文提出的2種算法.所有算法均采用C++語言實(shí)現(xiàn)，通過G++7.3.0編譯器進(jìn)行編譯.所有算法的源代碼由本文作者實(shí)現(xiàn).

4.2 數(shù)據(jù)集

本文所用數(shù)據(jù)集為23個真實(shí)數(shù)據(jù)集，相關(guān)統(tǒng)計(jì)信息如表5所示.其中，d表示平均出度，約定d≥4時為稠密圖，|V|≥100 000時為大圖.

Table 5 The Information of Dataset Statistics表5 數(shù)據(jù)集統(tǒng)計(jì)信息

4.3 查詢集

為了比較不同算法對標(biāo)簽可達(dá)查詢處理的整體性能，本文生成100萬個可達(dá)查詢和100萬個不可達(dá)查詢來進(jìn)行測試，并且|L|≤8.

針對上述的查詢集，所有的運(yùn)行時間都是執(zhí)行10次100萬個查詢的總時間取平均值.所有結(jié)果均保留到小數(shù)點(diǎn)后2位.本文實(shí)驗(yàn)的評估指標(biāo)包括：

1) 索引構(gòu)建時間;

2) 索引大小;

3) 查詢時間.

4.4 實(shí)驗(yàn)結(jié)果

4.4.1 索引構(gòu)建時間

圖3比較了不同規(guī)模數(shù)據(jù)集上的索引構(gòu)建時間.從圖3可以看出，在索引構(gòu)建時間方面，BPLI和BPLI+優(yōu)于LI+.對于規(guī)模較小的圖，如Kegg數(shù)據(jù)集，BPLI比LI+快1372倍，BPLI+比LI+快891倍.在Pubmed數(shù)據(jù)集上，BPLI比LI+快21.6倍，BPLI+比LI+快4.4倍.在規(guī)模較大的圖上，如Email-EuAll數(shù)據(jù)集，BPLI比LI+快1042倍，BPLI+比LI+快623倍.在Cit-Patents數(shù)據(jù)集上，BPLI比LI+快111倍，BPLI+比LI+快46倍.原因在于，LI+除了構(gòu)建地標(biāo)點(diǎn)的所有單向索引和非地標(biāo)點(diǎn)的部分單向索引外，還需要根據(jù)路徑標(biāo)簽對地標(biāo)點(diǎn)的索引進(jìn)行重新組織，因此會耗費(fèi)大量時間.

4.4.2 索引大小

Fig. 3 Comparison of index construction time on different datasets圖3 不同規(guī)模數(shù)據(jù)集上的索引構(gòu)建時間對比

Fig. 4 Comparison of index size on different datasets圖4 不同規(guī)模數(shù)據(jù)集上的索引大小對比

4.4.3 查詢時間

圖5和圖6展示了不同算法分別處理100萬不可達(dá)查詢及100萬可達(dá)查詢的查詢時間對比.當(dāng)查詢時間超過10 000 ms時，均顯示10 000 ms.本文有如下觀察：

1) BPLI方法與BPLI+方法處理可達(dá)查詢以及不可達(dá)查詢的效率均高于LI+.原因在于：BPLI使用了拓?fù)涮柼幚聿豢蛇_(dá)查詢，且路徑標(biāo)簽索引的可達(dá)覆蓋率高，因此查詢響應(yīng)時間較短；BPLI+方法無需遍歷操作，且索引規(guī)模不大，因此查詢響應(yīng)時間最短.

2) BFS沒有索引協(xié)助，因此查詢響應(yīng)時間最長.

Fig. 5 Comparison of query time on unreachable query workload圖5 不可達(dá)查詢的查詢時間對比

Fig. 6 Comparison of query time on reachable query workload圖6 可達(dá)查詢的查詢時間對比

5 結(jié)束語

針對現(xiàn)有方法在處理大圖上標(biāo)簽約束可達(dá)性查詢時索引構(gòu)建時間長、索引規(guī)模大且查詢響應(yīng)慢的問題，本文提出了2種基于地標(biāo)點(diǎn)的雙向路徑標(biāo)簽索引，并基于所提出的優(yōu)化方法來減小索引規(guī)模.實(shí)驗(yàn)結(jié)果從索引構(gòu)建時間、索引大小以及查詢時間3方面驗(yàn)證了本文所提方法的高效性.例如，本文方法在Email-EuAll數(shù)據(jù)集上的索引規(guī)模比LI+降低了96.67%，索引構(gòu)建時間比LI+降低了99%，可達(dá)查詢數(shù)據(jù)集上查詢時間比LI+提高了17倍，不可達(dá)查詢數(shù)據(jù)集上查詢時間比LI+提高了26倍.