溫菊屏 胡小生 林冬梅 曾亞光

摘要：針對k步可達(dá)性查詢算法無法解決帶距離約束的圖可達(dá)性查詢問題，提出基于參考節(jié)點嵌入的圖可達(dá)性查詢算法。首先，從所有節(jié)點中選出極少數(shù)有代表性的全局參考節(jié)點，預(yù)先計算所有節(jié)點與全局參考節(jié)點之間的最短路徑距離；然后，采用最短路徑樹和范圍最小值查詢技術(shù)求得局部參考節(jié)點；接著，利用三角不等式關(guān)系得到查詢點對距離范圍；最后，根據(jù)查詢條件中的距離值與查詢點對距離范圍上、下限值的大小關(guān)系，可快速得出可達(dá)性結(jié)論。針對社會關(guān)系網(wǎng)絡(luò)和公路網(wǎng)絡(luò)數(shù)據(jù)，將所提算法與Dijkstra算法、KReach算法進(jìn)行實驗對比測試。相較于KReach算法，其索引建立時間小4個數(shù)量級，其索引規(guī)模小2個數(shù)量級；相較于Dijkstra算法，在公路網(wǎng)絡(luò)和社會關(guān)系網(wǎng)絡(luò)中，直接得出可達(dá)性結(jié)論的比例分別為92%和78.6%，其查詢時間大大縮短，分別降低了95.5%和92%。實驗結(jié)果表明：所提算法能夠通過使用較小的索引開銷，實現(xiàn)在線查詢計算復(fù)雜度的降低，可很好地解決既適用于有權(quán)圖又適用于無權(quán)圖帶距離約束的可達(dá)性查詢問題。

關(guān)鍵詞：

k步可達(dá)性查詢；帶距離約束的圖可達(dá)性查詢；參考節(jié)點嵌入；三角不等式關(guān)系；最短路徑樹

中圖分類號： TP301.6 文獻(xiàn)標(biāo)志碼：A

0引言

針對圖G=（V，E）中任意兩個節(jié)點間的路徑存在性進(jìn)行判定，稱為圖的可達(dá)性問題。如果兩點之間存在路徑，則稱u可達(dá)v，簡記u → v。圖中節(jié)點間可達(dá)性判定，在現(xiàn)實很多領(lǐng)域有著廣泛的應(yīng)用，例如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、地理導(dǎo)航、Internet路由、可擴展標(biāo)記語言（Extensible Markup Language， XML）索引、基于資源描述框架（Resource Description Framework， RDF）的本體查詢等。如何有效地回答可達(dá)性查詢問題成為目前研究的熱點。

區(qū)別于傳統(tǒng)圖可達(dá)性查詢問題[1-5]回答一個節(jié)點t是否可達(dá)另一個節(jié)點s，k步可達(dá)性問題研究[6-11]在很多現(xiàn)實網(wǎng)絡(luò)中有著更為重要的意義[12]，k值大小直接反映節(jié)點s對節(jié)點t影響的程度。k步可達(dá)性查詢問題回答是否存在一條從節(jié)點t到節(jié)點s的路徑，路徑長度不超過k步，如果存在，則用t→k s表示，在此稱為k步可達(dá)性問題。例如，在一個無線網(wǎng)絡(luò)或者傳感器網(wǎng)絡(luò)中，廣播消息在任何一次轉(zhuǎn)發(fā)過程中都有可能丟失，經(jīng)過多次的轉(zhuǎn)發(fā)，接收的概率指數(shù)級降低。在這種情況下，兩個節(jié)點之間是否可達(dá)實際意義不大，應(yīng)該更加關(guān)心在k步兩點之間是否可達(dá)，它可反映一個節(jié)點對另一個節(jié)點的影響程度。還有一種情況是：在社會關(guān)系網(wǎng)絡(luò)中，由于六度分隔理論，任意兩個陌生人最多通過6個人一定能相互認(rèn)識，因此更為關(guān)心的應(yīng)該是兩人之間能否通過極小的幾步可達(dá)。雖然經(jīng)典可達(dá)性問題可以看作k步是否可達(dá)的一種特殊情況（k=∞），但是k步是否可達(dá)不是簡單地從經(jīng)典可達(dá)性問題導(dǎo)出，因為k步是否可達(dá)性問題更具有挑戰(zhàn)性，需要解決更多的問題。

本文研究的既不是傳統(tǒng)的可達(dá)性查詢問題，也不是k步可達(dá)性查詢問題，而是帶距離約束的可達(dá)性查詢問題，與k步可達(dá)性查詢問題通常只能針對無權(quán)圖，回答一個節(jié)點經(jīng)過k條邊是否可達(dá)另一節(jié)點的問題所不同的是：帶距離約束的可達(dá)性查詢可回答兩節(jié)點之間在k值距離范圍內(nèi)是否可達(dá)，既適用于無權(quán)圖也適用于有權(quán)圖。例如，用戶可以查詢“廣州到深圳在150公里之內(nèi)是否可達(dá)”。帶距離約束的查詢比一般的可達(dá)性查詢，以及近年來研究較多的無權(quán)圖上k步可達(dá)性查詢問題更具有實際意義。針對帶距離約束的可達(dá)性查詢問題，本文提出一種簡單高效的處理方法——參考節(jié)點嵌入機制[13]，其核心思想為：從圖中所有節(jié)點中選出有代表性的參考節(jié)點，預(yù)先計算出參考節(jié)點到所有節(jié)點之間的最短路徑距離，然后根據(jù)三角不等式關(guān)系，計算出待查詢兩節(jié)點之間距離的上、下限值，根據(jù)k值大小，在絕大部分的情況下可迅速判斷距離k值內(nèi)是否可達(dá)，在不可判斷的情況下，再進(jìn)行最短路徑距離計算，通過精確的距離來判斷是否可達(dá)。由于選擇的參考節(jié)點是所有節(jié)點中很小一部分，因此只需要極小的預(yù)存儲空間?；趫D可達(dá)性查詢問題，本文的工作概括起來主要有以下幾點：

1）對圖可達(dá)性查詢問題（包括傳統(tǒng)可達(dá)性問題及k步可達(dá)性查詢問題）的研究現(xiàn)狀進(jìn)行了總結(jié)。

2）針對帶距離約束的可達(dá)性查詢問題，提出一種基于參考節(jié)點嵌入的索引方法，通過索引可快速確定查詢點對之間的距離范圍，比較k值與距離范圍的上、下限值之間的大小關(guān)系，在絕大部分情況下，可以直接給出可達(dá)性結(jié)論，無需進(jìn)行最短路徑距離的精確計算，使得查詢效率更為高效。

3）為了縮緊距離范圍上、下限值，引入局部參考節(jié)點，使用最短路徑樹及范圍最小值查詢技術(shù)，設(shè)計了基于參考節(jié)點嵌入的圖可達(dá)性查詢算法。

4）在數(shù)字參考書目和圖書館項目（Digital Bibliography & Library Project， DBLP）圖和公路網(wǎng)絡(luò)圖數(shù)據(jù)上進(jìn)行實驗，實驗結(jié)果對直接給出可達(dá)性結(jié)論的比例和查詢時間進(jìn)行分析。本文設(shè)計的算法查詢時間位于2ms～6ms，70%～92%的查詢都可以基于本文設(shè)計的索引快速給出可達(dá)性結(jié)論。

5）選取一種k步可達(dá)性查詢算法——KReach與本文帶距離約束的可達(dá)性查詢算法，在DBLP無權(quán)圖上進(jìn)行實驗，實驗結(jié)果從索引構(gòu)建時間、索引大小及查詢響應(yīng)時間等指標(biāo)進(jìn)行分析。實驗結(jié)果顯示，本文的方法在建立索引的時間和索引的空間開銷上比KReach分別低了4個和2個數(shù)量級，而查詢時間比KReach慢了4個數(shù)量級；但是本文方法可以適用于有權(quán)圖和無權(quán)圖，而KReach只能回答無權(quán)圖上的可達(dá)性，因此本文的方法具有更為廣泛和實際的應(yīng)用價值。

1圖可達(dá)性問題研究現(xiàn)狀

對于一個具有n個頂點、m條邊的圖，任意的兩個節(jié)點u和v，如果存在最短路徑，則節(jié)點u到節(jié)點v可達(dá)，否則不可達(dá)。當(dāng)圖的規(guī)模比較小時，可使用最短路徑算法或深度優(yōu)先遍歷（DepthFirst Search， DFS）算法來實現(xiàn)圖可達(dá)性查詢問題。其缺點是查詢時間復(fù)雜度過高，對于大圖和超大圖而言，難以應(yīng)用到實際中。

另外有一種簡單的方法是：預(yù)先計算出圖中節(jié)點間的可達(dá)性情況——圖鄰接矩陣的傳遞閉包，并將其存儲下來，當(dāng)查詢圖中任意兩個節(jié)點u和v之間是否可達(dá)，只需查詢節(jié)點u的傳遞閉包即可，如果包含節(jié)點v，則說明節(jié)點u和節(jié)點v之間可達(dá)，否則不可達(dá)。這個方法可在常數(shù)時間內(nèi)完成可達(dá)性查詢問題，由于預(yù)先計算的時間復(fù)雜度較大，為O（n3），預(yù)存的空間復(fù)雜度達(dá)到O（n2），當(dāng)圖更新時需要重新計算傳遞閉包，因此也難以應(yīng)用到實際中。

針對圖可達(dá)性查詢問題，常常通過給圖中節(jié)點作標(biāo)記的方法（Labeling Scheme）[14]來解決，主要有3種代表性方法：1）位向量標(biāo)記方案（Bit Vector Labeling Schemes）。該方案預(yù)先計算所花費的時間復(fù)雜度為O（n），預(yù)存的空間復(fù)雜度為O（n2），查詢時間復(fù)雜度達(dá)到了O（n），由于標(biāo)記長度依賴于節(jié)點個數(shù)，因此不適用于圖更新的情況。2）前綴標(biāo)記方案（Prefix Labeling Scheme）。該方案的優(yōu)點是可以動態(tài)適應(yīng)圖的更新，但是節(jié)點間可達(dá)性查詢依賴于字符串的操作，使之不易優(yōu)化，并且從樹擴展到圖時，節(jié)點的標(biāo)記數(shù)量會呈爆炸式增長。3）區(qū)間標(biāo)記方案（Interval Labeling Scheme）。該方案的主要思想是先構(gòu)造一棵生成樹，并給樹中節(jié)點作好標(biāo)記，接著對節(jié)點按照反拓?fù)漤樞蜻M(jìn)行標(biāo)記，并且通過圖中的非樹邊對其向上復(fù)制，以保存可達(dá)性信息，通常處理類似樹或森林結(jié)構(gòu)的圖問題比較有效。其缺點是由于標(biāo)記采用自然數(shù)，對于插入等動態(tài)更新操作顯得繁瑣。

近幾年，為了提高圖可達(dá)性查詢效率，大量可達(dá)性索引方法被相繼提出[1]，這些方法旨在索引規(guī)模、查詢時間以及構(gòu)建時間三個方面取得平衡?？蛇_(dá)性索引研究的熱點集中在大規(guī)模圖數(shù)據(jù)可達(dá)性查詢處理、動態(tài)圖數(shù)據(jù)可達(dá)性處理和受限可達(dá)性查詢處理。

同時，存在幾種基于經(jīng)典可達(dá)性查詢問題拓展的研究方向：1）不確定圖上的可達(dá)性查詢研究[5]，該問題在現(xiàn)實中有著廣泛的應(yīng)用，例如生物學(xué)研究中，通常要研究蛋白質(zhì)交互網(wǎng)絡(luò)中任意兩個蛋白質(zhì)分子間是否有交互作用及交互強度的交換信息；為了在社交網(wǎng)絡(luò)中推薦好友，需要預(yù)先知道用戶之間的關(guān)聯(lián)關(guān)系等。2）帶條件限制的可達(dá)性查詢研究[15-17]，兩點之間的邊必須帶有某種標(biāo)簽屬性。

以上都是針對兩點之間是否可達(dá)進(jìn)行研究，目前出現(xiàn)一個新的研究熱點，判斷兩點之間在k步之內(nèi)是否可達(dá)，即k步可達(dá)性查詢問題，此研究具有更大的實際意義。例如：在社交網(wǎng)絡(luò)，通常要作的是以某人為起點查找到離他最近的若干個人，以此來尋找比較近的朋友或者合作關(guān)系。

現(xiàn)今求解k步可達(dá)性查詢問題方法主要有4大類：1）基于圖遍歷的求解方法，該方法按照遍歷的規(guī)則從頂點u出發(fā)判斷在k步之內(nèi)是否可達(dá)頂點v，廣度優(yōu)先遍歷（BreathFirst Search， BFS）按照通過已找到的頂點和未找到的頂點之間的邊向外擴展，不會出現(xiàn)深度優(yōu)先遍歷（DFS）算法中的回溯現(xiàn)象，此類方法效率低下。2）基于區(qū)間標(biāo)簽求解方法[6-7]，典型代表是經(jīng)隨機間隔標(biāo)記的圖可達(dá)性索引（Graph reachability indexing via RAndomized Interval Labeling， GRAIL請補充GRAIL和PLL的英文全稱。）方法[6]，其基本思想是給每一個頂點v附加兩個區(qū)間標(biāo)簽L1和L2，這兩個區(qū)間分別包含所有v可達(dá)頂點對應(yīng)的區(qū)間，用這種方法來回答k步可達(dá)性查詢時，若u和v的區(qū)間滿足包含關(guān)系，但u的出度非常大且可達(dá)v的孩子頂點很少時，系統(tǒng)需要訪問u的大量孩子頂點，最終遞歸處理會訪問大量無用頂點，最壞情況下和基于廣度優(yōu)先遍歷來求解k步可達(dá)性查詢的代價一樣低效。BiRch算法[7]在GRAIL方法上作了一定的改進(jìn)，提出了一種雙向搜索策略，并且設(shè)計了基于雙向廣度層數(shù)和雙向拓?fù)鋵訑?shù)的剪枝策略來輔助過濾，以減少需要訪問的頂點數(shù)量。3）基于最短路徑的方法[8，11]，典型代表是剪枝參考標(biāo)記（Pruned Landmark Labeling， PLL）[8]方法，在進(jìn)行深度優(yōu)先遍歷時事先計算出每個節(jié)點的距離標(biāo)簽，利用剪枝和位操作并行運算兩個技術(shù)來進(jìn)行相應(yīng)的優(yōu)化。4）基于k步索引的方法[9-10]，文獻(xiàn)[9]中設(shè)計的KReach算法，其基本原理是先根據(jù)原圖的一個頂點覆蓋集合，建立k步可達(dá)索引，實現(xiàn)k步可達(dá)性的查詢。算法缺陷在于索引是根據(jù)某一個k值進(jìn)行構(gòu)建，對不同的k值要作不同的索引。例如，如果索引基于k=3進(jìn)行構(gòu)建，只能回答查詢點對之間3步是否可達(dá)，無法回答其他步數(shù)之內(nèi)是否可達(dá)的查詢問題。在文獻(xiàn)[10]中，算法雖然作了一定的改進(jìn)，可以回答任意k步是否可達(dá)的查詢問題，但是，建立索引的開銷隨之升高，在圖比較稠密情況下，仍然存在索引規(guī)模急劇膨大的問題。

然而，在實際應(yīng)用中，例如公路網(wǎng)絡(luò)，往往不是查詢兩點之間經(jīng)過多少條邊是否可達(dá)，而是判斷在多遠(yuǎn)路程之內(nèi)是否可達(dá)。在這種情況下，此類問題，只能通過帶距離約束的可達(dá)性查詢算法加以解決。本文提出的基于參考節(jié)點嵌入的圖可達(dá)性查詢算法屬于帶距離約束的可達(dá)性查詢算法，該算法具有通用性，對無權(quán)圖、有權(quán)圖都適用。當(dāng)查詢的圖為無權(quán)圖時，邊上的權(quán)值為1，此時帶距離約束的可達(dá)性查詢算法變?yōu)閗步可達(dá)性查詢算法，此時的k值即表示邊的條數(shù)，也代表兩點之間的距離。當(dāng)查詢的圖為有權(quán)圖時，本文算法可以回答兩點之間在某個距離范圍是否可達(dá)，可解決k步可達(dá)性查詢算法無法解決的查詢條件中帶有距離值的可達(dá)性問題。

2基于參考節(jié)點嵌入的圖可達(dá)性查詢

一個圖通常表示為G=（V，E，w）。其中V是頂點的集合，E是邊的集合，w：E → R表示一個邊權(quán)重函數(shù)，代表一條邊映射成一個實數(shù)域上的權(quán)重。w（u，v）是一個正數(shù)，它表示節(jié)點u到節(jié)點v的距離長度，如果一個圖是無權(quán)圖，那么每條邊的權(quán)w（u，v）就是1。

假設(shè)定義：n=|V|，m=|E|，則n、m分別表示圖中節(jié)點數(shù)和邊數(shù)，對于一個節(jié)點對a，b∈V，p（a，b）=（a，v1，v2，…，vl-1，b）表示a、b之間對應(yīng)的一條路徑，對于有向圖而言，a為起點，b為終點，其中{a，v1，v2，…，vl-1，b}V，{（a，v1），（v1，v2），…，（vl-1，b）}E，|p|=l，l表示路徑p的長度，對于無權(quán)圖而言，l表示路徑上邊數(shù)之和，對于有權(quán)圖而言，l表示路徑上各邊長度之和。假定SP（a，b）表示節(jié)點a到節(jié)點b所有路徑的集合；O（a，b）表示節(jié)點a到節(jié)點b最短路徑距離，則O（a，b）的計算如式（1）所示：

O（a，b）=minp∈SP（a，b）|p|（1）

在回答帶距離約束的可達(dá)性查詢問題時，并不是所有情況下都必須計算出精確的最短路徑距離。如果能夠快速計算出兩點之間最短路徑的范圍區(qū)間，在絕大部分情況下通過距離k值和距離范圍上、下限值大小關(guān)系，直接給出可達(dá)性結(jié)論，而在極少數(shù)情況下，需要精確計算出查詢點對之間的最短路徑距離，與k值進(jìn)行比較，給出可達(dá)性結(jié)論，這將極大提高圖可達(dá)性查詢的效率。

基于參考節(jié)點嵌入的圖可達(dá)性查詢算法如算法1所示。

算法1基于參考節(jié)點嵌入的圖可達(dá)性查詢算法。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：一個有向圖G=（V，E，w）、查詢點對a和b、距離值k。

輸出：一個表達(dá)a在k值距離內(nèi)是否可達(dá)b真假性的邏輯值。

1）

range（a，b，&upper，&lower）/*算法2或算法4實現(xiàn)*/

2）

if （k

3）

return false；

4）

if （k≥upper）

5）

return true；

6）

if （k≥lower&&k

7）

{ dist=shortestpathdistance（a，b）；

8）

if （dist≤k）

9）

return true；

10）

else

11）

return false；}

程序后

算法1的第1）行代碼為求查詢點對最短路徑距離范圍區(qū)間上、下限值range函數(shù)的調(diào)用。range函數(shù)如果只是依據(jù)全局參考節(jié)點來確定距離范圍，則由2.1節(jié)的算法2加以實現(xiàn)。為了進(jìn)一步提高距離范圍的精度，使得在作查詢時直接給出可達(dá)性結(jié)論的可能性變大，需要在全局參考節(jié)點基礎(chǔ)上，按照某種選擇策略選出與查詢點對位置相關(guān)的局部參考節(jié)點，根據(jù)全局和局部參考節(jié)點兩個信息，計算出更為精確的查詢點對距離范圍區(qū)間，此時range函數(shù)則由2.2.4節(jié)的算法4加以實現(xiàn)。

2.1最短路徑距離范圍區(qū)間的確定

本文將參考節(jié)點嵌入思想引入到圖可達(dá)性查詢研究中，利用預(yù)先計算出參考節(jié)點與其他所有節(jié)點之間的距離，快速計算出兩點之間距離的上、下限值，從而確定距離范圍區(qū)間。本文引入的參考節(jié)點嵌入思想來自于文獻(xiàn)[13]，該思想用于最短路徑距離估算，其主要原理是：從所有節(jié)點中選擇少量有代表性的參考節(jié)點，預(yù)先計算出參考節(jié)點與其他所有節(jié)點之間的距離，并且存儲下來，在需要計算兩點距離時，通過預(yù)存的距離，并利用三角不等式關(guān)系估算出兩點之間的近似距離。參考節(jié)點嵌入思想廣泛應(yīng)用在社會關(guān)系網(wǎng)絡(luò)、公路網(wǎng)絡(luò)、因特網(wǎng)等網(wǎng)絡(luò)數(shù)據(jù)中，例如為了減少客戶端的訪問延遲，在因特網(wǎng)中查詢最近的服務(wù)器，或者在公路網(wǎng)絡(luò)中查詢兩地之間的最短路徑。

在此約定，本文討論的帶距離約束的圖可達(dá)性查詢算法，k值代表距離值，不是步數(shù)值。假設(shè)選定的參考節(jié)點集合S={l1，l2，…，ld}V，對于集合中每一個li∈V，預(yù)先計算出參考節(jié)點與所有節(jié)點之間的最短路徑距離，對于圖中每個節(jié)點v∈V，使用一個d維的向量來表示該點到所有參考節(jié)點的最短路徑距離：

D（v）=〈ο（l1，v），ο（l2，v），…，ο（ld，v）〉

根據(jù)預(yù)存距離值，基于三角不等式關(guān)系，可獲得每一個參考節(jié)點對應(yīng)的查詢點對a、b距離范圍的上、下限值，最終從所有的下限值中取最大值，從所有的上限值中取最小值，最終形成查詢點對a、b距離范圍區(qū)間，如式（2）、（3）所示：

o（a，b）≥maxli∈S {|ο（li，a）-o（li，b）|}（2）

ο（a，b）≤minli∈S {ο（li，a）+ο（li，b）}（3）

當(dāng)查詢點對的距離上、下限值確定之后，可達(dá)性判斷結(jié)論的給出可以分以下3種情況：

1）當(dāng)k

2）當(dāng)k≥minli∈S {ο（li，a）+ο（li，b）}時，說明k值等于或者大于距離的上限值，此時可以馬上給出兩點之間可達(dá)的結(jié)論，此處對應(yīng)算法1中第4）行代碼條件成立的情況；

3）當(dāng)k

如果給出的距離范圍比較小時，大部分情況下都可以使用第1）、2）情況直接給出可達(dá)性結(jié)論，如果給出的距離范圍太大時，k值位于上、下限值之間的概率變大，無法利用第1）、2）情況直接給出判斷，必須進(jìn)入第3）種情況，在線計算兩點之間的最短路徑距離，因此，距離范圍的大小直接影響到查詢效率，當(dāng)參考節(jié)點選擇策略比較優(yōu)化時，則通過三角不等式給出的距離范圍更小，距離上、下限值更接近真實的距離值。查詢點對最短路徑距離范圍區(qū)間的確定通過算法2實現(xiàn)，如下所示。

算法2確定查詢點對最短路徑距離范圍區(qū)間算法。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：一個有向圖G=（V，E，w）、查詢點對a和b。

輸出：距離范圍區(qū)間上限值upper、下限值lower。

1）

Compute a vertex set S={l1，l2，…，ld}V/*求參考節(jié)點集合S*/

2）

for each v∈V do

3）

Compute vector D（v）=〈ο（l1，v），ο（l2，v），…，ο（ld，v）〉

4）

for each li∈S do

5）

Compute |o（li，a）-o（li，b）|

6）

Compute o（li，a）+o（li，b）

7）

lower=maxli∈S {|ο（li，a）-o（li，b）|}

8）

upper=minli∈S {ο（li，a）+o（li，b）}

9）

return upper，lower

程序后

算法2第1）行代碼實現(xiàn)參考節(jié)點的選擇。如今選擇參考節(jié)點的方法是主要有隨機選擇法、各類基于圖的啟發(fā)式算法：例如基于度、基于中介中心性（betweenness centrality）、基于接近中心性（closeness centrality）等啟發(fā)式算法。盡管各種啟發(fā)式算法都致力于最優(yōu)化參考節(jié)點的選擇，但是參考節(jié)點的選擇都沒有考慮到與查詢點對位置之間的關(guān)系，以至于可能出現(xiàn)兩個查詢點對之間很近；但與選出的參考節(jié)點很遠(yuǎn)，根據(jù)三角不等式算出的距離上、下限值范圍過大的情況。目前，在最短路徑估算方面，一種與查詢相關(guān)的局部參考節(jié)點嵌入機制[18]被提出，此方法提供了更為精確的最短路徑距離估算。此方法可以很好地應(yīng)用于帶距離約束的圖可達(dá)性查詢問題中，更為精確地定位距離上、下限值。

2.2與查詢相關(guān)的局部參考節(jié)點嵌入機制

2.2.1與查詢相關(guān)的局部參考節(jié)點概念

通過圖說明與查詢相關(guān)的局部參考節(jié)點概念，如圖1所示。在圖1中，實線代表兩個點之間的一條邊，虛線則表示兩點之間有一條包含多個中間連接點的路徑，其中中間連接點信息省略，（a，e， f，g，b）路徑是a和b之間的最短路徑。

根據(jù)式（6）、（7）進(jìn)行加法和減法運算，式（4）可變成式（8），如下所示：

o（c，a）-o（c，b）≤o（a，b）≤o（c，a）+o（c，b）+2o（l1，c）（8）

對比式（5）、（8），可以發(fā)現(xiàn)全局參考節(jié)點與局部參考節(jié)點給出的查詢點對a、b的下限值一樣，不同的是上限值。l1參考節(jié)點給出的上限值比c參考節(jié)點給出的上限值更大（前者比后者大2o（l1，c）），因此需要結(jié)合局部參考節(jié)點信息對范圍區(qū)間的上限值進(jìn)行修正，修正為o（c，a）+o（c，b），修正的結(jié)果再結(jié)合式（6）、式（7），查詢點對a、b的上限值如式（9）所示：

o（a，b）≤o（l1，a）+o（l1，b）-2o（l1，c）（9）

通過以上分析，可以發(fā)現(xiàn)局部參考節(jié)點的引入，可以使得查詢點對a、b的上限值變小，接下來的問題就轉(zhuǎn)化為給定一個任意查詢點對及全局參考節(jié)點集合S，如何找到與每一個全局參考節(jié)點相對應(yīng)的局部參考節(jié)點，并最終從計算出來的所有上限值中取最小值，獲得新的距離范圍上限值，如式（10）所示：

ο（a，b）≤minli∈S {ο（li，a）+ο（li，b）-2o（li，c）}（10）

局部參考節(jié)點的引入讓距離的上限值變得更小，使得距離范圍區(qū)間更為緊縮。每一個局部參考節(jié)點都和某一個全局參考節(jié)點相對應(yīng)。以圖1為例，相對于全局參考節(jié)點l1而言，離節(jié)點a、b更近的節(jié)點c稱為與查詢點對a、b相關(guān)的局部參考節(jié)點。同理，相對于全局參考節(jié)點l2、l3而言，節(jié)點d、h稱為與查詢點對a、b相關(guān)的局部參考節(jié)點。

2.2.2基于局部參考節(jié)點的最短路徑樹

為了找到與每一個全局參考節(jié)點相對應(yīng)的局部參考節(jié)點，可通過以全局參考節(jié)點為根的最短路徑樹加以實現(xiàn)。

定義1假定一個圖表示為G=（V，E，w），以r（r∈V）為根節(jié)點的最短路徑樹（Shortest Path Tree， SPT）是一棵這樣的生成樹：從r到每一個節(jié)點v（v∈V）都是一條r到v之間最短的路徑，并且這條最短路徑的長度是r到v之間的最短距離，如圖2所示。

圖2是針對圖1中全局參考節(jié)點l1的一個最短路徑樹。注意從圖1導(dǎo)出的以節(jié)點l1為根的最短路徑樹并不唯一。通過圖2可以發(fā)現(xiàn)節(jié)點c比節(jié)點l1更為接近節(jié)點a、b，是與查詢相關(guān)的局部參考節(jié)點，它即為a、b的最小共同祖先（Least Common Ancestor， LCA）節(jié)點。

定義2假設(shè)T為一棵根為l，帶有n個節(jié)點的樹，所謂樹T中節(jié)點u，v的LCA節(jié)點是一個離根最遠(yuǎn)的節(jié)點u，v的共同祖先節(jié)點，它可由函數(shù)LCA（u，v，l）計算獲得。

因此，圖2中相對于全局參考節(jié)點l1而言，與查詢點對a、b相關(guān)的局部參考節(jié)點c，可由函數(shù)LCA（u，v，l1）計算獲得，因此問題又轉(zhuǎn)化為求根節(jié)點為l1的最短路徑樹中節(jié)點a、b的最小共同祖先問題。

此時a、b兩點之間距離上限值由式（11）獲得：

2.2.3范圍最小值查詢技術(shù)

在參考文獻(xiàn)[19]中介紹的范圍最小值查詢（Range Minimum Query， RMQ）技術(shù)，可以快速找到一個最短路徑樹中兩個節(jié)點之間的LCA節(jié)點。

定義3假定A為一個長度為n的一維數(shù)組：A[1，2，…，n]，范圍最小值查詢RMQA（i， j）表示返回數(shù)組A[i，…， j]最小元素值，其中i、 j表示數(shù)組的下標(biāo)值，其范圍是：1≤i≤j≤n。

由于節(jié)點a、b的LCA是對樹T進(jìn)行深度優(yōu)先搜索時，在訪問節(jié)點a和節(jié)點b之間離根最近（節(jié)點深度最?。┑哪莻€節(jié)點，因此，兩個節(jié)點之間的LCA節(jié)點問題又轉(zhuǎn)化為以下最小值查詢問題：

1）由于對由n個節(jié)點構(gòu)成的樹T作歐拉環(huán)游深度優(yōu)先遍歷時，需要對n-1條邊的每條邊作兩次訪問，因此，用數(shù)組trace[1，2，…，2n-1]來記錄遍歷過程中節(jié)點的信息。圖2的最短路徑樹，對應(yīng)的trace數(shù)組為：trace=（l1，…，c，e，a，…，h，…，l3，…，h，…，a，e， f，e，c，d，…，l2，…，d，g，b，g，d，c，…，l1）。

2）用數(shù)組L[1，2，…，2n-1]記錄trace數(shù)組中對應(yīng)節(jié)點在樹T中的深度值，假定根節(jié)點的深度值為0，離它一步可達(dá)的孩子節(jié)點深度值則為1，以此類推。

3）用數(shù)組stamp[1，2，…，n]記錄樹T中n個節(jié)點在深度優(yōu)先遍歷時在數(shù)組trace中第一次出現(xiàn)的下標(biāo)值，即stamp[a]=mini{trace[i]=a}，a∈V。

因此，在以全局參考節(jié)點l1為根節(jié)點的最短路徑樹中，與查詢點對a、b相關(guān)的局部參考節(jié)點的計算式如下：

LCA（a，b，li）=trace[arg minstamp[a]≤i≤stamp[b]L[i]]=trace[RMQL（stamp[a]，stamp[b]）]（12）

2.2.4與查詢相關(guān)的局部參考節(jié)點選擇算法

算法2中第1）行代碼，是基于圖的啟發(fā)式算法進(jìn)行參考節(jié)點的選擇，為了找到更為緊縮的距離范圍區(qū)間，需借助局部參考節(jié)點對距離范圍區(qū)間進(jìn)行修正，局部參考節(jié)點的獲得通過與查詢相關(guān)的局部參考節(jié)點選擇算法加以實現(xiàn)，如算法3所示。

算法3與查詢相關(guān)的局部參考節(jié)點選擇算法。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：一個有向圖G=（V，E，w）、一個全局參考節(jié)點l∈S（S={l1，l2，…，ld}V）、查詢點對a和b。

輸出：局部參考節(jié)點c。

1）

Create a shortest path tree rooted at a vertex l

2）

Create an array trace[2*n-1]

3）

Create an array L[2*n-1]

4）

Create an array stamp[n]

5）

i=stamp[a]

6）

j=stamp[b]

7）

t=RMQL（i， j）

8）

c=trace[t]

9）

return c

程序后

算法3可以計算獲得查詢點對a、b對應(yīng)于全局參考節(jié)點l的局部參考節(jié)點，該算法可以用來定義求局部參考節(jié)點的函數(shù)LCA，c=LCA（a，b，l），根據(jù)式（10）可知，查詢點對a、b距離的上限值要作修正，因此確定查詢點對最短路徑距離范圍區(qū)間的算法2需要修改為算法4，如下所示。

算法4基于局部參考節(jié)點確定查詢點對距離范圍區(qū)間算法。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：一個有向圖G=（V，E，w）、查詢點對a和b。

輸出：距離范圍區(qū)間上限值upper、下限值lower。

1）

Compute a vertex set S={l1，l2，…，ld}V/*求參考節(jié)點集合S*/

2）

for each v∈V do

3）

Compute vector D（v）=〈ο（l1，v），ο（l2，v），…，ο（ld，v）〉

4）

for each li∈S do

5）

c=LCA（a，b，li）/*LCA函數(shù)由算法3實現(xiàn)*/

6）

Compute |o（li，a）-o（li，b）|

7）

Compute o（li，a）+o（li，b）-2o（li，c）

8）

lower=maxli∈S {|ο（li，a）-o（li，b）|}

9）

upper=minli∈S {ο（li，a）+o（li，b）-2o（li，c）}

10）

return upper，lower

程序后

2.3時間復(fù)雜度分析

2.3.1離線計算時間復(fù)雜度分析

計算一個點到其他各點最短路徑距離時間復(fù)雜度為O（n*log n+m），在計算最短路徑的同時，以該節(jié)點為根的最短路徑樹也自動生成。另外，對每一個全局參考節(jié)點而言，建立一個對應(yīng)的RMQ查詢表的時間復(fù)雜度為O（n），兩個部分之和為O（n*log n+m）。假設(shè)集合S為全局參考節(jié)點集合，d=|S|代表全局參考節(jié)點個數(shù)，因此，總時間復(fù)雜度為O（d*n*log n+d*m），請注意d是一個比較小的常數(shù)，由于通常情況下dn，則時間復(fù)雜度大約為O（n*log n+m）。

2.3.2離線計算空間復(fù)雜度分析

構(gòu)建與查詢相關(guān)的局部參考節(jié)點嵌入的最短路徑樹需要的空間，可以分為以下兩個部分：

1）對于每個全局參考節(jié)點，需要存儲預(yù)先計算到各個節(jié)點之間的最短路徑距離，因此，空間復(fù)雜度為O（d*n）。

2）對于每個全局參考節(jié)點，需要計算對應(yīng)的最短路徑樹，以及在對其進(jìn)行深度優(yōu)先遍歷時，生成trace、L、stamp數(shù)組。以上每個部分的空間復(fù)雜度都為O（n），則所有全局參考節(jié)點需要的空間復(fù)雜度為O（d*n）。

將以上兩個部分求和，總的空間復(fù)雜度為O（d*n）。

2.3.3在線查詢的時間復(fù)雜度分析

分兩種情況來討論：

1）如果可以通過上、下限值給出可達(dá)性結(jié)論，則查詢的時間復(fù)雜度取決于式（11），對于每一個全局參考節(jié)點而言，有3次查詢預(yù)先計算的最短路徑距離，時間復(fù)雜度為O（1）；另外，為了找到查詢點對的最小共同祖先（LCA），通過RMQ算法實現(xiàn)，其時間復(fù)雜度為O（1），因此考慮到d個全局參考節(jié)點，總共的時間復(fù)雜度為O（d）。

2）當(dāng)k值在上、下限值之間，需要進(jìn)一步計算兩點之間的最短路徑距離來進(jìn)行可達(dá)性判定時，時間復(fù)雜度則為O（n*log n+m）。

最好的情況是可通過距離上、下限值直接給出可達(dá)性結(jié)論，其時間復(fù)雜度O（d），比起通過直接求兩點之間最短路徑距離，給出可達(dá)性判斷的時間復(fù)雜度O（n*log n+m）而言，復(fù)雜度大大降低，因此使用一個合理的參考節(jié)點嵌入機制，可使得大部分點對之間可達(dá)性判斷屬于以上第1）種情況，其時間復(fù)雜度可大大降低。

3實驗結(jié)果與分析

3.1實驗環(huán)境

實驗使用機器的基本配置為Intel Xeon X5550 2.67GHz CPU，48GB內(nèi)存，操作系統(tǒng)為Linux。本文采用的實驗數(shù)據(jù)來源于兩個真實的圖——DBLP數(shù)據(jù)集和紐約公路網(wǎng)絡(luò)數(shù)據(jù)集。其中，DBLP是一個計算機領(lǐng)域內(nèi)對研究的成果以作者為核心進(jìn)行集成的計算機類英文文獻(xiàn)的數(shù)據(jù)庫系統(tǒng)。實驗使用的DBLP數(shù)據(jù)集選取數(shù)據(jù)庫、數(shù)據(jù)挖掘、信息檢索和人工智能這四個研究領(lǐng)域的參考文獻(xiàn)數(shù)據(jù)，該數(shù)據(jù)組成了一個反映四個領(lǐng)域內(nèi)最高產(chǎn)作者合著者關(guān)系的大圖，該圖是無權(quán)圖，每條邊權(quán)值都為1，其中，每個節(jié)點表示一個作者，每條邊表示兩個作者之間的合著關(guān)系。紐約公路網(wǎng)絡(luò)數(shù)據(jù)屬于公路網(wǎng)絡(luò)，是有權(quán)圖，每條邊的大小反映兩個點之間距離的遠(yuǎn)近。

實驗分為兩大部分：第1部分是本文設(shè)計的基于參考節(jié)點嵌入的圖可達(dá)性查詢算法與Dijkstra算法進(jìn)行對比；第2部分是本文算法與k步可達(dá)性查詢算法的一個代表KReach算法進(jìn)行對比。所有算法都基于Microsoft Visual C++實現(xiàn)。

3.2第1部分實驗——算法性能測試

第1部分實驗將從兩個方面進(jìn)行測試：

1）使用Dijkstra算法計算出所有查詢點對之間精確距離進(jìn)行可達(dá)性判斷，與基于參考節(jié)點嵌入的可達(dá)性查詢算法進(jìn)行可達(dá)性判斷，比較這兩種算法給出可達(dá)性結(jié)論運行時間的長短。

2）使用基于參考節(jié)點嵌入的可達(dá)性查詢算法時，計算出所有點對之間可達(dá)性判斷中，通過k值大于等于上限值或者小于下限值的關(guān)系直接給出可達(dá)性結(jié)論的比例。

3.2.1時間測試

針對兩個數(shù)據(jù)集，取2000個點構(gòu)成圖。對于每一個圖而言，采用下面的方法產(chǎn)生500個查詢用于測試：隨機產(chǎn)生500個點對表示出發(fā)點和目的點。每個查詢的k值根據(jù)整個圖中所有點對之間的最短路徑距離最小值和最大值之間隨機產(chǎn)生，這樣能確保查詢點對之間可達(dá)性結(jié)論均勻覆蓋可達(dá)和不可達(dá)情況。這兩個圖所有點對之間的最短路徑距離長度分布如圖3～4所示。從圖3可以看出DBLP圖所有點對之間距離范圍為1～15，k值應(yīng)取1～15的隨機數(shù)；從圖4可以看出公路網(wǎng)絡(luò)圖所有點對之間距離范圍為1～226，k值應(yīng)取1～226的隨機數(shù)。

針對兩個不同的圖，分別作兩次數(shù)據(jù)測試。每次數(shù)據(jù)測試，確保均在相同的查詢數(shù)據(jù)前提下，使用Dijkstra算法和基于參考節(jié)點嵌入的可達(dá)性查詢算法（以下簡稱可達(dá)性查詢算法）進(jìn)行可達(dá)性判斷，采集兩者各自運行時間，具體數(shù)據(jù)如下表1所示。其中：d表示參考節(jié)點數(shù)目；tz表示平均每一個點對使用Dijkstra算法運行的時間；tk表示平均每個點對使用可達(dá)性查詢算法運行的時間。

從表1數(shù)據(jù)可以發(fā)現(xiàn)，不管是DBLP圖還是公路網(wǎng)絡(luò)圖，其運行時間都大大縮短，其中公路網(wǎng)絡(luò)的效果更為明顯。相較于直接計算最短路徑距離進(jìn)行可達(dá)性判斷，當(dāng)d=20時，兩者的運行時間都是最小值。相對于最短路徑算法，在DBLP圖和公路網(wǎng)絡(luò)圖中，運行時間分別降低了92%和95.5%。

接下來，將以上運行時間隨著參考節(jié)點的增加而變化的趨勢用圖表直觀表示出來，如圖5所示。從數(shù)據(jù)的變化趨勢可以發(fā)現(xiàn)：隨著參考節(jié)點數(shù)目的增加，可達(dá)性查詢算法的運行時間開始呈減少趨勢，原因在于參考節(jié)點數(shù)目越多，確定距離上、限值的范圍就更為精確，則直接給出可達(dá)性判斷的情況就越多，因此運行時間越來越少，但是到達(dá)一個最低點之后，運行時間又呈增加趨勢，原因在于隨著參考節(jié)點數(shù)目的增加，用于確定距離上下限范圍的開銷也變得越大。結(jié)合表1數(shù)據(jù)和圖5數(shù)據(jù)的變化趨勢可以看出，兩個數(shù)據(jù)集都是d=20時運行時間最短。

3.2.2比例測試

針對兩個數(shù)據(jù)集取2000個點構(gòu)成圖，分別作兩次數(shù)據(jù)測試。每次都隨機產(chǎn)生500個點對和對應(yīng)合理的k值，統(tǒng)計出通過k值與上、下限值的關(guān)系直接給出可達(dá)性結(jié)論的點對數(shù)占總點對數(shù)的比例，其值用percentage表示，該值隨著參考節(jié)點數(shù)目（d值）的變化也發(fā)生改變，如表2所示。

從表2數(shù)據(jù)可以發(fā)現(xiàn)：percentage值對DBLP圖而言偏低，最高78.6%，最低69.6%；對公路網(wǎng)絡(luò)圖而言，最高92%，最低79.2%。分析其原因在于這兩個數(shù)據(jù)集合屬于不同類型的數(shù)據(jù)：DBLP數(shù)據(jù)是小半徑的社會關(guān)系網(wǎng)絡(luò)數(shù)據(jù)，其符合六度分隔理論，點對之間的距離差別不大，只有通過提高參考節(jié)點的數(shù)目來收緊上、下限值，獲得更為精確的距離范圍，因此相較于公路網(wǎng)絡(luò)圖而言，直接獲得可達(dá)性結(jié)論的比例值偏低；而公路網(wǎng)絡(luò)由于是有權(quán)值的圖，兩點之間的距離跨度較大，用同樣數(shù)量的參考節(jié)點，可以更高比例直接回答可達(dá)性結(jié)論。

接下來，將2000個點構(gòu)成的DBLP圖和公路網(wǎng)絡(luò)圖的percentage值以圖表形式顯示，如圖6所示。從圖6可以發(fā)現(xiàn)比例值都是隨著參考節(jié)點數(shù)目的增加而增加，原因在于參考節(jié)點數(shù)目越多，距離上、下限值就越精確，通過k值與上、下限值的關(guān)系直接給出可達(dá)性結(jié)論的情況就越多，因此，提高參考節(jié)點的數(shù)目可提高直接給出可達(dá)性結(jié)論的比例。

通過時間和比例值數(shù)據(jù)的測試，發(fā)現(xiàn)參考節(jié)點數(shù)目的確定非常重要：參考節(jié)點數(shù)越多，直接給出可達(dá)性結(jié)論的比例就越高，運行時間也會隨之減少；但是參考節(jié)點數(shù)達(dá)到一個值之后，用于給出距離上、下限值的開銷也會越大，運行時間又會增加，因此選擇合適大小的d值非常重要。此方法針對不同類型的數(shù)據(jù)，都可以達(dá)到減少運行時間的目的，直接給出可達(dá)性結(jié)論的比例用于點對之間跨度比較大的數(shù)據(jù)集，效果更好。

3.3第2部分實驗——性能對比測試

由于KReach算法屬于k步可達(dá)性查詢算法，它只能處理無權(quán)圖，因此本文設(shè)計算法與KReach算法只在無權(quán)圖DBLP數(shù)據(jù)上作實驗對比。衡量一個查詢算法的性能不能只看查詢時間長短，而要綜合考慮索引建立時間、索引大小、查詢時間三個方面因素。

針對同樣的500個查詢請求，實驗采集兩個算法的索引建立時間、索引大小、查詢時間這3個指標(biāo)數(shù)據(jù)，結(jié)果如表3所示。

從表3數(shù)據(jù)可以看出，本文設(shè)計算法除了查詢時間，在索引建立時間和索引所占空間大小都有明顯優(yōu)勢，索引建立時間比KReach算法低了4個數(shù)量級，索引大小比KReach算法小了2個數(shù)量級。原因在于KReach算法針對每一個k值都建立一個對應(yīng)的索引，在查詢條件固定一個k值時優(yōu)勢明顯；但針對不同查詢點對k值不同的情況下，要花費更大的代價建立對應(yīng)的索引信息。KReach算法采取用索引建立時間和空間代價換取查詢時間縮短的策略，在查詢時只需要直接查詢索引表即可，時間復(fù)雜度為O（1），而本文設(shè)計的算法在線查詢的時間復(fù)雜度在2.3.3節(jié)有詳細(xì)描述，最好情況下時間復(fù)雜度為O（d），最壞情況下為O（n*log n+m）。從表2的DBLP數(shù)據(jù)可以看出，直接給出可達(dá)性結(jié)論的點對數(shù)占總點對數(shù)的比例percentage值最大為78.6%，可在常量時間內(nèi)查詢索引表后進(jìn)行簡單計算即可給出可達(dá)性結(jié)論，然而，仍然存在21.4%查詢點對落入最壞情況——需要在線計算最短路徑距離給出可達(dá)性結(jié)論，因此總體的查詢時間相較于KReach算法更長。然而，衡量查詢算法性能好壞要綜合考慮索引建立時間、索引大小、查詢時間三個因素，不能單單只看在線查詢時間長短，隨著圖規(guī)模的進(jìn)一步加大，KReach算法建立索引的開銷會急劇膨大，以索引建立時間和空間代價換取查詢時間縮短的做法不太可取，并且本文算法適用范圍更廣，既適用于有權(quán)圖又適用于無權(quán)圖，因此綜合比較，本文所提算法可被廣泛地應(yīng)用。

4結(jié)語

本文提出一種解決帶距離約束的可達(dá)性查詢問題的算法，該算法可以回答兩點之間多少距離范圍之內(nèi)是否可達(dá)。相較于k步可達(dá)性查詢算法只能在無權(quán)圖上回答節(jié)點t在k步長之內(nèi)是否可達(dá)節(jié)點s，帶距離約束的可達(dá)性查詢算法可以回答節(jié)點t在k值距離之內(nèi)是否可達(dá)節(jié)點s，既適用于無權(quán)圖也適用于有權(quán)圖，該算法更具有更為廣泛和實際的應(yīng)用價值。本文的創(chuàng)新點在于將參考節(jié)點嵌入機制引入到圖查詢研究中，設(shè)計出用于解決帶距離約束的可達(dá)性查詢問題的算法——基于參考節(jié)點嵌入的圖可達(dá)性查詢算法，該算法的優(yōu)點是索引規(guī)模小，索引建立時間短，大部分情況下可以通過查詢索引表進(jìn)行簡單計算，直接給出可達(dá)性結(jié)論。今后工作的重點是在參考節(jié)點的選擇策略方面作進(jìn)一步的研究，更為快速和精確地確定兩點之間距離的上、下限值，使得能夠通過查詢索引表直接給出可達(dá)性結(jié)論的比例提高，進(jìn)一步縮短查詢時間，提高查詢效率。

參考文獻(xiàn)：

[1]

富麗貞，孟小峰.大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)：現(xiàn)狀與展望[J].計算機研究與發(fā)展，2015，52（1）：116-129.（FU L Z， MENG X F. Reachability indexing for largescale graphs： studies and forecasts [J]. Journal of Computer Research and Development， 2015， 52（1）： 116-129.）

[2]

CHEN Y J， CHEN Y B. Decomposing DAGs into spanning trees： a new way to compress transitive closures [C]// Proceedings of the 27th International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2011： 1007-1018.

[3]

SEBASTIAAN J V S， OEGE D M. A memory efficient reachability data structure through bit vector compression [C]// SIGMOD11： Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2011： 913-924.

[4]

李世峰.大規(guī)模有向圖的可達(dá)查詢關(guān)鍵技術(shù)研究[D].沈陽：遼寧大學(xué)，2014：10-14.（LI S F. Research on key techniques of reachability query for largescale digraphs [D]. Shenyang： Liaoning University， 2014： 10-14.）

[5]

翟秋瑛.基于可達(dá)性的不確定圖查詢研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013：1-7.（ZHAI Q Y. The query research based on reachability of uncertain graph [D]. Harbin： Harbin Institute of Technology， 2013： 1-7.）

[6]

YILDIRIM H， CHAOJI V， ZAKI M J. GRAIL： scalable reachability index for large graphs [J]. PVLDB Journal， 2010， 3（1）： 276-284.

[7]

周軍鋒，陳偉，費春蘋，等.BiRch：一種處理k步可達(dá)性查詢的雙向搜索算法[J].通信學(xué)報，2015，36（8）：50-60.（ZHOU J F， CHEN W， FEI C P， et al. BiRch： a bidirectional search algorithm for kstep reachability queries [J]. Journal on Communications， 2015， 36（8）： 50-60.）

[8]

AKIBA T， IWATA Y， YOSHIDA Y. Fast exact shortestpath distance queries on large networks by pruned landmark labeling [C]// SIGMOD13： Proceedings of the 13th Special Interest Group on Management of Data Conference. New York： ACM， 2013： 349-360.

[9]

CHENG J， SHANG Z， CHENG H. KReach： who is in your small world [J]. Proceedings of the VLDB Endowment， 2012， 5（11）： 1292-1303.

[10]

CHENG J， SHANG Z， CHENG H. Efficient processing of khop reachability queries [J]. The VLDB Journal， 2014， 23（2）： 227-252.

[11]

WEI F. TEDI： efficient shortest path query answering on graphs [C]// Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. New York： ACM， 2010： 99-110.

[12]

QIAO M， QIN L， CHENG H， et al. TopK nearest keyword search on large graphs [C]// Proceedings of the 39th International Conference on Very Large Data Bases. New York： VLDB Endowment， 2013： 901-912.

[13]

MICHALIS P， FRANCESCO B， CARLOS C， et al. Fast shortest path distance estimation in large networks [C]// Proceedings of the 18th ACM Conference on Information and Knowledge Management. New York： ACM， 2009： 867-876.

[14]

宋勁柯.FLS：一種支持更新的圖可達(dá)性標(biāo)記算法[D].上海：復(fù)旦大學(xué)，2009：1-3.（SONG J K. FLS： a labelling scheme to solve the reachability problem of dynamic updating graph [D]. Shanghai： Fudan University， 2009： 1-3.）

[15]

SAYED A， KAYED M， HAMMOSHI M. Efficient evaluation of reachability query for directed acyclic XML graph based on a prime number labelling schema [J]. Egyptian Informatics Journal， 2012， 13（3）： 209-216.

[16]

ZOU L， XU K， YU J X， et al. Efficient processing of labelconstraint reachability queries in large graphs [J]. Information Systems， 2014， 40（1）： 47-66.

[17]

陳明涵.不確定圖上基于標(biāo)簽限制的可達(dá)性查詢技術(shù)的研究[D].沈陽：東北大學(xué)，2013：10-17.（CHEN M H. Research on labelconstraint reachability queries in uncertain graphs [D]. Shenyang： Northeastern University， 2013： 10-17.）

[18]

QIAO M， CHENG H， CHANG L J， et al. Approximate shortest distance computing： a querydependent local lankmark scheme [J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（1）： 55-68.

[19]

BENDER M A， FARACHCOLTON M. The LCA problem revisited [C]// LATIN00 Proceedings of the 4th Latin American Symposium on Theoretical Informatics. Berlin： Springer， 2000： 88-94.