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

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

關(guān)鍵詞：

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

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

0引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

有序號(hào)的程序——————————Shift+Alt+Y

程序前

輸入：一個(gè)有向圖G=（V，E，w）、查詢點(diǎn)對(duì)a和b、距離值k。

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

1）

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

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

本文將參考節(jié)點(diǎn)嵌入思想引入到圖可達(dá)性查詢研究中，利用預(yù)先計(jì)算出參考節(jié)點(diǎn)與其他所有節(jié)點(diǎn)之間的距離，快速計(jì)算出兩點(diǎn)之間距離的上、下限值，從而確定距離范圍區(qū)間。本文引入的參考節(jié)點(diǎn)嵌入思想來自于文獻(xiàn)[13]，該思想用于最短路徑距離估算，其主要原理是：從所有節(jié)點(diǎn)中選擇少量有代表性的參考節(jié)點(diǎn)，預(yù)先計(jì)算出參考節(jié)點(diǎn)與其他所有節(jié)點(diǎn)之間的距離，并且存儲(chǔ)下來，在需要計(jì)算兩點(diǎn)距離時(shí)，通過預(yù)存的距離，并利用三角不等式關(guān)系估算出兩點(diǎn)之間的近似距離。參考節(jié)點(diǎn)嵌入思想廣泛應(yīng)用在社會(huì)關(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é)點(diǎn)集合S={l1，l2，…，ld}V，對(duì)于集合中每一個(gè)li∈V，預(yù)先計(jì)算出參考節(jié)點(diǎn)與所有節(jié)點(diǎn)之間的最短路徑距離，對(duì)于圖中每個(gè)節(jié)點(diǎn)v∈V，使用一個(gè)d維的向量來表示該點(diǎn)到所有參考節(jié)點(diǎn)的最短路徑距離：

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

根據(jù)預(yù)存距離值，基于三角不等式關(guān)系，可獲得每一個(gè)參考節(jié)點(diǎn)對(duì)應(yīng)的查詢點(diǎn)對(duì)a、b距離范圍的上、下限值，最終從所有的下限值中取最大值，從所有的上限值中取最小值，最終形成查詢點(diǎn)對(duì)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)查詢點(diǎn)對(duì)的距離上、下限值確定之后，可達(dá)性判斷結(jié)論的給出可以分以下3種情況：

1）當(dāng)k

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

3）當(dāng)k

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

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

有序號(hào)的程序——————————Shift+Alt+Y

程序前

輸入：一個(gè)有向圖G=（V，E，w）、查詢點(diǎn)對(duì)a和b。

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

1）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

此時(shí)a、b兩點(diǎn)之間距離上限值由式（11）獲得：

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

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

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

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

1）由于對(duì)由n個(gè)節(jié)點(diǎn)構(gòu)成的樹T作歐拉環(huán)游深度優(yōu)先遍歷時(shí)，需要對(duì)n-1條邊的每條邊作兩次訪問，因此，用數(shù)組trace[1，2，…，2n-1]來記錄遍歷過程中節(jié)點(diǎn)的信息。圖2的最短路徑樹，對(duì)應(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ù)組中對(duì)應(yīng)節(jié)點(diǎn)在樹T中的深度值，假定根節(jié)點(diǎn)的深度值為0，離它一步可達(dá)的孩子節(jié)點(diǎn)深度值則為1，以此類推。

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

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

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é)點(diǎn)選擇算法

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

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

有序號(hào)的程序——————————Shift+Alt+Y

程序前

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

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

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

有序號(hào)的程序——————————Shift+Alt+Y

程序前

輸入：一個(gè)有向圖G=（V，E，w）、查詢點(diǎn)對(duì)a和b。

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

1）

Compute a vertex set S={l1，l2，…，ld}V/*求參考節(jié)點(diǎn)集合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實(shí)現(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時(shí)間復(fù)雜度分析

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

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

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

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

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

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

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

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

分兩種情況來討論：

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

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

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

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

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

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

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

3.2第1部分實(shí)驗(yàn)——算法性能測試

第1部分實(shí)驗(yàn)將從兩個(gè)方面進(jìn)行測試：

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

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

3.2.1時(shí)間測試

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

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

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

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

3.2.2比例測試

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

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

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

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

3.3第2部分實(shí)驗(yàn)——性能對(duì)比測試

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

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

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

4結(jié)語

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

參考文獻(xiàn)：

[1]

富麗貞，孟小峰.大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)：現(xiàn)狀與展望[J].計(jì)算機(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]

周軍鋒，陳偉，費(fèi)春蘋，等.BiRch：一種處理k步可達(dá)性查詢的雙向搜索算法[J].通信學(xué)報(bào)，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.