有向圖上k步可達(dá)查詢(xún)處理

杜明 林鏗 周軍鋒

摘 要：給定一個(gè)有向圖，一個(gè)k步可達(dá)查詢(xún)u→？kv用來(lái)回答在該圖中是否存在一條從頂點(diǎn)u到頂點(diǎn)v且長(zhǎng)度不大于k的有向路徑。k步可達(dá)查詢(xún)是一種基本的圖操作并在過(guò)去十年間被廣泛地研究。已有的k步可達(dá)查詢(xún)算法仍存在許多弊端，例如不可達(dá)查詢(xún)效率低，索引規(guī)模大和索引構(gòu)建時(shí)間長(zhǎng)等。本文針對(duì)上述問(wèn)題提出了2種優(yōu)化方法，分別是基于互逆拓?fù)湫蛱?hào)以及基于等價(jià)頂點(diǎn)的圖壓縮方法.前者提高了不可達(dá)查詢(xún)的效率，后者減少了索引規(guī)模和索引構(gòu)建時(shí)間。實(shí)驗(yàn)結(jié)果表明，本文提出的方法可以有效地處理k步可達(dá)查詢(xún)，并支持大規(guī)模數(shù)據(jù)的處理。

關(guān)鍵詞： 有向圖;k步可達(dá)查詢(xún);圖壓縮

文章編號(hào)： 2095-2163（2021）01-0008-07?中圖分類(lèi)號(hào)：TP301.6?文獻(xiàn)標(biāo)志碼：A

【Abstract】Given a directed graph， a k-hop reachability query u→？kv is used to answer whether there is a directed path from vertex u to vertex v and the length of the path is not greater than k. The k-hop reachability query is a basic graph operation and has been extensively studied in the past years. Existing algorithms still have many drawbacks， such as being inefficient for unreachability queries， large index size and long index construction time. This paper proposes two optimization approaches to make improvements， i.e.， the mutual reversed topological order and the graph compression based on equivalent vertices. The former improves the efficiency of unreachability queries， and the latter reduces the index size and index construction time. The experimental results show that the proposed method can effectively improve the performance of k-hop reachability queries processing and support large-scale graph processing.

【Key words】directed graph; k-hop reachability query; graph compression

0?引?言

隨著互聯(lián)網(wǎng)的快速發(fā)展，各種數(shù)據(jù)的規(guī)模日益龐大。圖是一種常見(jiàn)的數(shù)據(jù)表示模型，其中每個(gè)實(shí)體被簡(jiǎn)單地抽象成圖中的一個(gè)頂點(diǎn)，實(shí)體間的關(guān)系被抽象成2個(gè)頂點(diǎn)之間的一條邊。圖被廣泛地應(yīng)用于各類(lèi)領(lǐng)域，如社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等等[1-3]。在圖模型上的一個(gè)基本操作是回答2個(gè)頂點(diǎn)之間的可達(dá)性查詢(xún)，即判斷在圖中是否存在一條從源頂點(diǎn)u出發(fā)到目標(biāo)頂點(diǎn)v結(jié)束的一條有向路徑?？蛇_(dá)性查詢(xún)?cè)谶^(guò)去被廣泛地研究[4-8]，然而在實(shí)際應(yīng)用中，可達(dá)性查詢(xún)僅能回答2個(gè)實(shí)體之間是否存在某種關(guān)系，而無(wú)法回答這種關(guān)系的強(qiáng)弱程度。

另一種更有價(jià)值的操作是回答2個(gè)頂點(diǎn)之間的k步可達(dá)查詢(xún)[9-10]，即判斷在圖中是否存在一條從源頂點(diǎn)u出發(fā)到目標(biāo)頂點(diǎn)v結(jié)束的一條有向路徑，并且滿(mǎn)足該路徑的長(zhǎng)度不超過(guò)k。k步可達(dá)查詢(xún)相較于可達(dá)性查詢(xún)能提供更多關(guān)于2個(gè)頂點(diǎn)之間的信息，本質(zhì)上，可達(dá)性查詢(xún)是一種特殊的k步可達(dá)查詢(xún)，即當(dāng)k取∞時(shí)。k步可達(dá)查詢(xún)?cè)诂F(xiàn)實(shí)生活中有很多實(shí)際的應(yīng)用。比如在交通網(wǎng)絡(luò)中，經(jīng)常需要回答在2個(gè)地點(diǎn)之間是否存在一條路程不超過(guò)某個(gè)閾值的路線(xiàn)。又比如在社交網(wǎng)絡(luò)中，通過(guò)2個(gè)實(shí)體之間的距離來(lái)判斷這2個(gè)實(shí)體產(chǎn)生關(guān)聯(lián)的可能性。

現(xiàn)有k步可達(dá)查詢(xún)算法大多只能運(yùn)行在有向無(wú)環(huán)圖上，而有向圖上的k步可達(dá)查詢(xún)的相關(guān)研究卻寥寥無(wú)幾。在有向圖上回答k步可達(dá)查詢(xún)的基本方法是BFS[11]或者DFS [12]?；诒闅v的方法因?yàn)椴痪邆淞己玫臄U(kuò)展性，因而查詢(xún)效率低下。另一個(gè)簡(jiǎn)單的實(shí)現(xiàn)方法是將任意2個(gè)頂點(diǎn)之間的最短路徑信息預(yù)先通過(guò)鄰接矩陣的方式存儲(chǔ)起來(lái)，回答查詢(xún)時(shí)僅需要O（1）的時(shí)間內(nèi)即可返回結(jié)果。但是這種方法需要的空間代價(jià)過(guò)大，無(wú)法應(yīng)用于大規(guī)模數(shù)據(jù)圖。

針對(duì)上述算法存在的問(wèn)題，文獻(xiàn)[9]提出了一種基于2-hop索引PLL。PLL的基本思想是通過(guò)為每個(gè)頂點(diǎn)預(yù)先建立一組出標(biāo)簽和一組入標(biāo)簽，這2組標(biāo)簽分別保存了部分頂點(diǎn)與該頂點(diǎn)之間的最短路徑信息，這些部分頂點(diǎn)被稱(chēng)為hop點(diǎn)。2個(gè)頂點(diǎn)之間的k步可達(dá)查詢(xún)問(wèn)題可以被轉(zhuǎn)化為判斷兩點(diǎn)間最短路徑的長(zhǎng)度是否小于等于k的問(wèn)題。

PLL算法本身也存在低效性的問(wèn)題。首先，如果一個(gè)查詢(xún)頂點(diǎn)對(duì)之間是不可達(dá)的，那么PLL算法需要遍歷源頂點(diǎn)的所有出標(biāo)簽以及目標(biāo)頂點(diǎn)的所有入標(biāo)簽才能判斷出這對(duì)查詢(xún)頂點(diǎn)對(duì)是不可達(dá)的。其次，PLL算法在所有的頂點(diǎn)上構(gòu)建索引，因此導(dǎo)致構(gòu)建的索引的時(shí)間較長(zhǎng)，同時(shí)構(gòu)建的索引規(guī)模也較大。

針對(duì)PLL算法存在的以上2種問(wèn)題，本文提出了2種針對(duì)性的優(yōu)化方法。第一種是基于互逆拓?fù)湫蛱?hào)來(lái)加快不可達(dá)查詢(xún)的效率，第二種是基于等價(jià)頂點(diǎn)的圖壓縮方法，通過(guò)去除圖中的冗余頂點(diǎn)和冗余邊，使得圖盡可能地小。實(shí)驗(yàn)結(jié)果表明，本文提出的優(yōu)化方法可以顯著改善索引的構(gòu)建速度，索引規(guī)模更小。

1?相關(guān)工作

1.1?問(wèn)題定義

給定一個(gè)有向圖G=（V，E），其中V={v1，v2，…，vn}是圖中頂點(diǎn)的集合，E={（u，v）|u，v∈V}是圖中邊的集合。當(dāng)一條邊e=（u，v）∈E時(shí)，表示存在一條從頂點(diǎn)u指向頂點(diǎn)v的有向邊。對(duì)于每個(gè)頂點(diǎn)u，本文使用scc（u）來(lái)表示頂點(diǎn)u所在的強(qiáng)連通分量。同時(shí)使用outG（u）={v|（u，v）∈E}來(lái)表示頂點(diǎn)u的出鄰居集合以及使用inG（u）={v|（v，u）∈E}表示頂點(diǎn)u的入鄰居集合。用degout（u）=|outG（u）|表示頂點(diǎn)u的出度，degin（u）=|inG（u）|表示頂點(diǎn)u的入度。

在一個(gè)有向無(wú)環(huán)圖中，拓?fù)渑判蚴菍D中頂點(diǎn)從偏序狀態(tài)轉(zhuǎn)化為全序狀態(tài)。一個(gè)頂點(diǎn)u的拓?fù)湫蛱?hào)是頂點(diǎn)全序關(guān)系的序號(hào)，拓?fù)湫蛱?hào)大的頂點(diǎn)與拓?fù)湫蛱?hào)小的頂點(diǎn)之間不存在有向路徑。

如果2個(gè)頂點(diǎn)u，v滿(mǎn)足outG（u）=outG（v）并且inG（u）=inG（v），即頂點(diǎn)u和頂點(diǎn)v存在相同的出鄰居集合以及相同的入鄰居集合，則稱(chēng)這2個(gè)頂點(diǎn)互為等價(jià)頂點(diǎn)。直觀上，2個(gè)頂點(diǎn)等價(jià)意味著二者可達(dá)相同的頂點(diǎn)集合，且可達(dá)二者的頂點(diǎn)集合也相同。

問(wèn)題定義?給定一個(gè)有向圖G和一個(gè)k步可達(dá)查詢(xún)u→？kv，如果在G中存在一條從u出發(fā)到v的有向路徑，并且該路徑的長(zhǎng)度不超過(guò)k，則返回TRUE，否則返回FALSE。

1.2?相關(guān)算法

1.2.1?PLL算法

PLL（Pruned Landmark Labeling）算法的基本思想是為圖中的每一個(gè)頂點(diǎn)u預(yù)先構(gòu)建2組標(biāo)簽Lout（u）={（h1，d1），…，（hi，di）}和Lin（u）={（h1，d1），…，（hj，dj）}。其中，Lout（u）保存了從頂點(diǎn)u可以到達(dá)的部分頂點(diǎn)以及頂點(diǎn)u到這些頂點(diǎn)之間的距離，類(lèi)似地，Lin（u）保存了從部分可以到達(dá)頂點(diǎn)u的頂點(diǎn)以及這些頂點(diǎn)到頂點(diǎn)u之間的距離。每個(gè)頂點(diǎn)標(biāo)簽中的每一對(duì)元素（h，d）表示hop點(diǎn)h以及h和該頂點(diǎn)之間的最短距離d。

PLL算法將2個(gè)查詢(xún)頂點(diǎn)對(duì)之間的k步可達(dá)查詢(xún)轉(zhuǎn)化為了判斷源頂點(diǎn)u和目標(biāo)頂點(diǎn)v的最短距離是否小于等于k的問(wèn)題。由于標(biāo)簽中的hop點(diǎn)序號(hào)是以升序排列的，因此判斷2個(gè)標(biāo)簽中是否存在一個(gè)公共的hop點(diǎn)的時(shí)間復(fù)雜度為O（n+m），其中n，m分別表示出標(biāo)簽和入標(biāo)簽中元素的個(gè)數(shù)。

PLL算法使用剪枝策略保證了建立的索引中盡可能地減少冗余的最短路徑信息。具體的做法是在對(duì)每一個(gè)hop點(diǎn)進(jìn)行BFS遍歷的過(guò)程中，如果已經(jīng)建立的2-hop索引能夠回答該hop點(diǎn)到當(dāng)前遍歷的頂點(diǎn)之間的最短路徑信息，則PLL算法不會(huì)將該hop點(diǎn)加入到當(dāng)前遍歷的頂點(diǎn)的2-hop標(biāo)簽中，同時(shí)不再?gòu)漠?dāng)前遍歷的頂點(diǎn)執(zhí)行BFS遍歷。

1.2.2?K-Reach算法

K-Reach算法[9，13]的基本思想是首先求解有向圖G的最小頂點(diǎn)覆蓋集C，然后在求解得到的C上建立傳遞閉包，這個(gè)傳遞閉包只包含了C中各個(gè)頂點(diǎn)之間的可達(dá)信息。

當(dāng)回答一個(gè)k步可達(dá)查詢(xún)u→？kv時(shí)，根據(jù)查詢(xún)頂點(diǎn)對(duì)u，v是否屬于C分為如下3種情況：

（1）頂點(diǎn)u和頂點(diǎn)v都屬于最小頂點(diǎn)覆蓋集，此時(shí)可以直接通過(guò)建立的傳遞閉包來(lái)回答查詢(xún)。

（2）頂點(diǎn)u和頂點(diǎn)v中只有一個(gè)屬于C，在這種情況下需要通過(guò)遍歷那個(gè)非最小頂點(diǎn)覆蓋集頂點(diǎn)的出鄰居集合的傳遞閉包或者入鄰居集合的傳遞閉包來(lái)回答查詢(xún)。

（3）頂點(diǎn)u和頂點(diǎn)v中都不屬于C，這是最壞的情況，需要遍歷頂點(diǎn)u的出鄰居集合的傳遞閉包以及v的入鄰居集合的傳遞閉包來(lái)回答查詢(xún)。

K-Reach算法存在如下問(wèn)題：首先該算法構(gòu)建的傳遞閉包索引只能用于回答k等于特定值的k步可達(dá)查詢(xún)。其次，當(dāng)查詢(xún)頂點(diǎn)對(duì)不屬于最小頂點(diǎn)覆蓋集時(shí)，需要遍歷查詢(xún)頂點(diǎn)對(duì)的所有鄰居頂點(diǎn)的傳遞閉包。最后，隨著k值的增大，每個(gè)頂點(diǎn)的傳遞閉包數(shù)量將呈指數(shù)上升，因此該算法將無(wú)法有效地?cái)U(kuò)展到大圖上。

2?優(yōu)化方法

2.1?基于互逆拓?fù)湫蛱?hào)的查詢(xún)優(yōu)化方法

在有向無(wú)環(huán)圖中，一個(gè)頂點(diǎn)的拓?fù)湫蛱?hào)是該頂點(diǎn)在拓?fù)渑判蛑斜惶幚淼捻樞?。如果一個(gè)頂點(diǎn)的拓?fù)湫蛱?hào)大于另一個(gè)頂點(diǎn)的拓?fù)湫蛱?hào)，則前者必然不可達(dá)后者，反之不成立。因此，在一個(gè)有向無(wú)環(huán)圖中，可以通過(guò)判斷2個(gè)頂點(diǎn)的拓?fù)湫蛱?hào)大小來(lái)快速地回答2個(gè)頂點(diǎn)間的不可達(dá)情況。

但是在有向圖中，由于可能存在強(qiáng)連通分量，而拓?fù)渑判虮仨氃跓o(wú)環(huán)圖中才能進(jìn)行，因此必須對(duì)有向圖進(jìn)行一定的變換。在本文中采取的解決方案是將每一個(gè)強(qiáng)連通分量（SCC）壓縮成一個(gè)超級(jí)頂點(diǎn)，從而將有向圖轉(zhuǎn)換成有向無(wú)環(huán)圖。Tarjan算法是用來(lái)求解強(qiáng)連通分量的經(jīng)典算法，該算法可以在線(xiàn)性時(shí)間內(nèi)求解出每個(gè)頂點(diǎn)所屬的強(qiáng)連通分量。對(duì)于屬于同一個(gè)強(qiáng)連通分量中的頂點(diǎn)，將為其賦予相同的拓?fù)湫蛱?hào)。

在拓?fù)渑判蛑?，?duì)于一個(gè)頂點(diǎn)來(lái)說(shuō)，不同的處理順序可以生成不同的拓?fù)湫蛱?hào)，一個(gè)直觀的想法就是為每個(gè)頂點(diǎn)設(shè)置多個(gè)拓?fù)湫蛱?hào)從而過(guò)濾掉等多的不可達(dá)查詢(xún)。然而，每個(gè)拓?fù)湫蛱?hào)都需要一個(gè)整型的存儲(chǔ)空間，過(guò)多的拓?fù)湫蛱?hào)會(huì)導(dǎo)致索引規(guī)模增長(zhǎng)。因此，本文提出構(gòu)建互逆的拓?fù)湫蛱?hào)來(lái)達(dá)到最佳的查詢(xún)效率以及較小的空間開(kāi)銷(xiāo)。

互逆拓?fù)湫蛱?hào)的大致思想是為每個(gè)頂點(diǎn)建立2個(gè)拓?fù)湫蛱?hào)。如果建立頂點(diǎn)u的第一個(gè)拓?fù)湫蛱?hào)要先于建立頂點(diǎn)v的第一個(gè)拓?fù)湫蛱?hào)，則在建立第二個(gè)拓?fù)湫蛱?hào)時(shí)，要優(yōu)先處理頂點(diǎn)v的拓?fù)湫蛱?hào)。這種機(jī)制保證了每個(gè)頂點(diǎn)的2個(gè)拓?fù)湫蛱?hào)構(gòu)成的區(qū)間盡可能地大，從而可以判斷等多的不可達(dá)情況。至此，研究可得算法1、算法2的代碼設(shè)計(jì)詳見(jiàn)如下。

算法1?genTopo（G=（V，E））

輸入：G=（V，E）

輸出：所有頂點(diǎn)的互逆拓?fù)湫蛱?hào)

1?G' ← tarjan（G）

2?construct（G'，X）

3?construct（G'，Y）

4?return （X，Y）

算法2?construct（G=（V，E），T）

1?將入度為0的頂點(diǎn)按照特定的順序入棧S

2?topNum ← 0

3?while S≠ do

4?u ← pop（S）

5?Tu ← topNum

6?topNum ← topNum + 1

7?for each v ∈outG（u） do

8?degin（v） ← degin（v）-1

9?if degin（v） = 0 do

10?push（S，v）

算法1展示了在一個(gè)有向圖上求解互逆拓?fù)湫蛱?hào)的過(guò)程。算法的輸入是G，輸出是G上所有頂點(diǎn)的互逆拓?fù)湫蛱?hào)。第1行首先調(diào)用Tarjan算法將G中的強(qiáng)連通分量壓縮成超級(jí)頂點(diǎn)。第2～3行分別調(diào)用construct方法建立拓?fù)湫蛱?hào)。

在算法2的construct方法中，第1行將入度為0的頂點(diǎn)按照特定的順序入棧S，第2行設(shè)置一個(gè)計(jì)數(shù)器topNum，用來(lái)記錄每個(gè)頂點(diǎn)的處理順序。第3行當(dāng)棧S不為空時(shí)，執(zhí)行第4～10行的操作。第4行先彈出棧首頂點(diǎn)v，并在第5行將頂點(diǎn)v的拓?fù)湫蛱?hào)設(shè)置為topNum，同時(shí)第6行更新topNum。第7～10行按照特定的順序處理頂點(diǎn)v的所有出鄰居，將其入度均做減一處理，如果減后的入度為0，則將該出鄰居頂點(diǎn)入棧。

對(duì)于在同一個(gè)強(qiáng)連通分量中的每個(gè)頂點(diǎn)，各頂點(diǎn)的互逆拓?fù)湫蛱?hào)都等于相應(yīng)頂點(diǎn)所在的超級(jí)頂點(diǎn)的互逆拓?fù)湫蛱?hào)。Tarjan算法和construct方法的時(shí)間復(fù)雜度都為O（m）， 其中m為有向圖G的邊數(shù)，因此整個(gè)genTopo方法的時(shí)間復(fù)雜度為O（m）。

2.2?基于等價(jià)頂點(diǎn)的圖壓縮方法

在1.1節(jié)中給出了等價(jià)頂點(diǎn)的相關(guān)定義。對(duì)于任意2個(gè)相互等價(jià)的頂點(diǎn)u、v，在回答可達(dá)性查詢(xún)時(shí)（除查詢(xún)頂點(diǎn)對(duì)為（u，v）這種特殊情況，稍后討論）可以相互替換。例如當(dāng)回答從頂點(diǎn)u到頂點(diǎn)w（其中w≠v）的k步可達(dá)查詢(xún)時(shí)，可以替換成從頂點(diǎn)v到頂點(diǎn)w的k步可達(dá)查詢(xún)。

根據(jù)該特性，可以實(shí)現(xiàn)基于等價(jià)頂點(diǎn)的圖壓縮算法。具體的做法是對(duì)于互為等價(jià)頂點(diǎn)的一組頂點(diǎn)，只保留其中的一個(gè)頂點(diǎn)，同時(shí)刪除與該頂點(diǎn)等價(jià)的其他頂點(diǎn)。當(dāng)需要回答涉及被刪除頂點(diǎn)的k步可達(dá)查詢(xún)信息時(shí)，可以通過(guò)與查詢(xún)頂點(diǎn)等價(jià)的那個(gè)保留頂點(diǎn)來(lái)判斷可達(dá)性。在對(duì)圖建立2-hop索引之前，通過(guò)先對(duì)圖進(jìn)行基于等價(jià)頂點(diǎn)的圖壓縮，能有效減小圖的規(guī)模，從而降低構(gòu)建索引的時(shí)間和索引大小。

本文采用文獻(xiàn)[14]中提出的基于分治思想的求解等價(jià)頂點(diǎn)方法。該方法的基本思路是首先將頂點(diǎn)集V中的所有頂點(diǎn)視為可能相互等價(jià)的，再將集合V分成2個(gè)集合，這2個(gè)集合中的頂點(diǎn)可能互相等價(jià)，但不同集合中的頂點(diǎn)不可能等價(jià)。接下來(lái)繼續(xù)對(duì)2個(gè)集合進(jìn)行類(lèi)似的分割，直到每個(gè)集合都無(wú)法再繼續(xù)分割下去。最后每個(gè)集合中存儲(chǔ)的頂點(diǎn)都是相互等價(jià)的，而集合之間的頂點(diǎn)是不可能等價(jià)的，該算法的時(shí)間復(fù)雜度是O（m），其中m是圖中邊的個(gè)數(shù)。

對(duì)于2個(gè)等價(jià)頂點(diǎn)u、v，當(dāng)查詢(xún)頂點(diǎn)對(duì)為（u，v）時(shí)，根據(jù)頂點(diǎn)u和頂點(diǎn)v是否位于同一個(gè)強(qiáng)連通分量中，會(huì)存在2種不同的情況，具體如圖1所示。在圖1（a）中，即頂點(diǎn)u和頂點(diǎn)v不在同一個(gè)SCC并且頂點(diǎn)u和頂點(diǎn)v互為等價(jià)頂點(diǎn)，此時(shí)頂點(diǎn)u必然不可達(dá)頂點(diǎn)v、并且頂點(diǎn)v也不可達(dá)頂點(diǎn)u，因此查詢(xún)結(jié)果返回FALSE。在圖1（b）中，頂點(diǎn)u和頂點(diǎn)v位于同一個(gè)SCC、并且頂點(diǎn)u和頂點(diǎn)v互為等價(jià)頂點(diǎn)，則u和v可能是k步可達(dá)的（取決于k值是否大于或等于這2個(gè)頂點(diǎn)之間的最短路徑長(zhǎng)度），此時(shí)可能就需要通過(guò)遍歷或者額外的索引來(lái)處理這種特殊情況。為了處理這種不常見(jiàn)但又確實(shí)存在的查詢(xún)，導(dǎo)致每一次回答查詢(xún)時(shí)都要進(jìn)行額外的判斷，這顯然是十分繁瑣又低效的操作。

為了解決該問(wèn)題，本文提出了一種新的策略，對(duì)于不在同一個(gè)SCC中的等價(jià)頂點(diǎn)，將對(duì)其進(jìn)行壓縮操作。而對(duì)于處于同一個(gè)SCC中的等價(jià)頂點(diǎn)，則將其視為不等價(jià)的，因此無(wú)需進(jìn)行壓縮，等價(jià)頂點(diǎn)之間的k步可達(dá)查詢(xún)可以直接通過(guò)建立的2-hop標(biāo)簽回答。該策略能有效地避免在這種特殊條件下的冗長(zhǎng)而低效的條件分支判斷以及遍歷圖的操作。

2.3?查詢(xún)方法

算法3給出了在2種優(yōu)化方法下的PLL算法的查詢(xún)方法，設(shè)計(jì)代碼依次展開(kāi)如下。

算法3?query（u，v，k）

輸入：源頂點(diǎn)u，目標(biāo)頂點(diǎn)v，查詢(xún)距離k

輸出：TRUE/FALSE

1?if Xu > Xv or Yu > Yv

2?return FALSE

3?ue ← Eu， ve ← Ev

4?if ue = ve

5?return FALSE

6?ui ← 0， vi ← 0

7?while ui < Lout（ue）.size and vi < Lin（ve）.size

8?hu = Lout（ue）[ui].hop， hv = Lin（ve）[vi].hop

9?du = Lout（ue）[ui].dist， dv = Lin（ve）[vi].dist

10?if hu = hv do

11?if du +?dv <= k do

12?return TRUE

13?else

14?ui ← ui + 1， vi ← vi + 1

15?else if hu < hv do

16?ui ← ui + 1

17?else

18?vi ← vi + 1

19?return FLASE

算法3中，第1行先判斷頂點(diǎn)u的拓?fù)湫蛱?hào)X是否大于頂點(diǎn)v的拓?fù)湫蛱?hào)X以及頂點(diǎn)u的拓?fù)湫蛱?hào)Y是否大于頂點(diǎn)v的拓?fù)湫蛱?hào)Y。如果任意一個(gè)條件成立，表明頂點(diǎn)u不可達(dá)頂點(diǎn)v，因此第2行直接返回FALSE。第3行將頂點(diǎn)u和頂點(diǎn)v轉(zhuǎn)換成對(duì)應(yīng)的等價(jià)頂點(diǎn)ue和ve。數(shù)組E保存了每個(gè)頂點(diǎn)與其對(duì)應(yīng)的等價(jià)頂點(diǎn)的關(guān)系，該數(shù)組由2.2節(jié)中所描述的方法求出。第4行如果轉(zhuǎn)換后的等價(jià)頂點(diǎn)相等，則查詢(xún)結(jié)果返回FALSE。否則第6～19行通過(guò)PLL算法構(gòu)建的2-hop標(biāo)簽來(lái)回答查詢(xún)。

3?實(shí)驗(yàn)分析

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

本文實(shí)驗(yàn)中所使用的硬件平臺(tái)為Intel（R）Core（TM） i5-4200M @ 2.5GHz CPU，16G雙通道內(nèi)存，操作系統(tǒng)為Ubuntu 18.04.3 LTS。本次實(shí)驗(yàn)算法采用C++語(yǔ)言實(shí)現(xiàn)，并且查詢(xún)距離k均取值為10。實(shí)驗(yàn)首先比較了PLL算法和PLL算法在分別使用2種優(yōu)化算法的情況下的索引構(gòu)造時(shí)間、索引大小以及查詢(xún)時(shí)間。隨后比較了PLL算法與同時(shí)使用2種優(yōu)化算法的索引構(gòu)造時(shí)間、索引大小以及查詢(xún)時(shí)間。

3.2?數(shù)據(jù)集

本次研究中所使用的10個(gè)數(shù)據(jù)集見(jiàn)表1。這10個(gè)數(shù)據(jù)集都來(lái)自斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集（snap.stanford.edu/data/）。這些圖數(shù)據(jù)集都是有向有環(huán)圖，表1中標(biāo)注了每個(gè)數(shù)據(jù)集的頂點(diǎn)數(shù)V以及邊數(shù)E。本文將頂點(diǎn)數(shù)大于100000的數(shù)據(jù)集稱(chēng)為大數(shù)據(jù)集，因此本次實(shí)驗(yàn)中共有5個(gè)大數(shù)據(jù)集以及5個(gè)小數(shù)據(jù)集。本次實(shí)驗(yàn)使用的查詢(xún)集大小為1000000，其中可達(dá)頂點(diǎn)對(duì)和不可達(dá)頂點(diǎn)對(duì)的比例為1：1。

3.3?性能比較分析

3.3.1?2種優(yōu)化技術(shù)的比較

PLL算法和PLL算法在分別使用了2種優(yōu)化方法之后的索引大小見(jiàn)表2。從表2中可以看到，互逆拓?fù)湫蛱?hào)所需的存儲(chǔ)空間最多，因?yàn)樾枰~外的2個(gè)整型值來(lái)存儲(chǔ)拓?fù)湫蛱?hào)（即PLL+Topo）。其次是PLL算法，最優(yōu)的是使用了基于等價(jià)頂點(diǎn)壓縮的PLL算法（即PLL+GC），因?yàn)閮H在部分點(diǎn)上建立2-hop索引，從而具有最小的索引大小。

PLL算法和PLL算法在分別使用了2種優(yōu)化方法之后的索引構(gòu)造時(shí)間見(jiàn)表3。從表3中可以得到與在索引大小中類(lèi)似的結(jié)論，由于需要額外計(jì)算2個(gè)互逆拓?fù)湫蛱?hào)，因此PLL+Topo的時(shí)間開(kāi)銷(xiāo)最多，但由于求解拓?fù)湫蛱?hào)是線(xiàn)性時(shí)間復(fù)雜度，因此差距并不明顯。其次，雖然PLL+GC方法花費(fèi)了線(xiàn)性時(shí)間來(lái)計(jì)算等價(jià)頂點(diǎn)，但是由于進(jìn)行了圖壓縮，因此整個(gè)索引構(gòu)造時(shí)間相較于PLL算法減少了。

PLL算法和PLL算法在分別使用了2種優(yōu)化方法之后的查詢(xún)時(shí)間見(jiàn)表4。其中，查詢(xún)距離k取10。從表4中可以看出在應(yīng)用了互逆拓?fù)湫蛱?hào)后的查詢(xún)效率有了明顯的提升，在一些數(shù)據(jù)集上有2～3倍左右的提升。PLL算法在回答不可達(dá)查詢(xún)時(shí)的時(shí)間消耗要大于回答可達(dá)的查詢(xún)頂點(diǎn)對(duì)所花費(fèi)的時(shí)間，而互逆拓?fù)湫蛱?hào)能在O（1）的時(shí)間內(nèi)回答絕大部分的不可達(dá)查詢(xún)，因此提高了查詢(xún)的效率。對(duì)于PLL+GC方法來(lái)說(shuō)，由于進(jìn)行了圖壓縮，因此建立的索引大小更小，從而使得查詢(xún)時(shí)需要遍歷的hop頂點(diǎn)數(shù)更少，因此也在一定程度上提高了查詢(xún)效率。

3.3.2?PLL算法與PLL-O方法的比較

PLL算法和PLL算法同時(shí)應(yīng)用了2種優(yōu)化方法（即PLL-O）之后的索引大小見(jiàn)表5。從表5中可以看出在絕大多數(shù)的數(shù)據(jù)集上，PLL-O方法的索引大小要優(yōu)于PLL算法。只有在極個(gè)別圖上（如HepTh），圖壓縮方法對(duì)索引大小帶來(lái)的收益沒(méi)能抵消2個(gè)拓?fù)涮?hào)帶來(lái)的空間開(kāi)銷(xiāo)，此時(shí)PLL-O方法的索引規(guī)模會(huì)略大于PLL算法。

PLL算法和PLL算法同時(shí)應(yīng)用了2種優(yōu)化方法之后的索引構(gòu)造時(shí)間見(jiàn)表6。由于綜合了圖壓縮方法的優(yōu)點(diǎn)，PLL-O算法在整體上的性能都優(yōu)于PLL算法。

PLL算法和PLL算法同時(shí)應(yīng)用了2種優(yōu)化方法之后的查詢(xún)時(shí)間見(jiàn)表7，其中查詢(xún)距離k取10。從表7中可以看出PLL-O方法相比于只應(yīng)用了圖壓縮的方法的查詢(xún)效率要高，然而相對(duì)于僅應(yīng)用互逆拓?fù)湫蛱?hào)的方法來(lái)說(shuō)性能差距不大。但綜合考慮索引大小以及索引構(gòu)造時(shí)間后，PLL-O方法較PLL算法以及僅使用一種優(yōu)化方法的PLL方法仍具有較大的優(yōu)勢(shì)。

4?結(jié)束語(yǔ)

本文針對(duì)已有k步可達(dá)查詢(xún)算法存在的不可達(dá)查詢(xún)效率低，索引構(gòu)造時(shí)間長(zhǎng)，索引規(guī)模大等問(wèn)題提出了2種優(yōu)化的方法，分別是基于等價(jià)頂點(diǎn)的圖壓縮方法以及基于互逆拓?fù)湫蛱?hào)的不可達(dá)查詢(xún)優(yōu)化方法。實(shí)驗(yàn)結(jié)果表明，在同時(shí)應(yīng)用了這2種算法之后，PLL算法的查詢(xún)效率、索引大小以及索引構(gòu)造時(shí)間都有了明顯的提升。

參考文獻(xiàn)

[1]Van HELDEN J， NAIM A， MANCUSO R， et al. Representing and analysing molecular and cellular function using the computer[J]. Biological chemistry， 2000， 381（9-10）： 921-935.

[2]STANN F， HEIDEMANN J. RMST： Reliable data transport in sensor networks[C]//Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications. Anchorage，AK， USA：IEEE， 2003： 102-112.

[3]KUMAR R， TUZHILIN A， FALOUTSOS C， et al. Social networks： Looking ahead[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas， USA：ACM， 2008： 1060.

[4]CHEN Yangjun， CHEN Yibin. An efficient algorithm for answering graph reachability queries[C]//2008 IEEE 24th International Conference on Data Engineering. Cancun，Mexico：IEEE， 2008： 893-902.

[5]YU J X， CHENG Jiefeng. Graph reachability queries： A survey[M]//Managing and Mining Graph Data. Boston， MA：Springer， 2010： 181-215.

[6]CHENG J， HUANG Silu， WU Huanhuan， et al. TF-Label： A topological-folding labeling scheme for reachability querying in a large graph[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York：ACM， 2013： 193-204.

[7]WANG H， HE H， YANG J， et al. Dual labeling： Answering graph reachability queries in constant time[C]//22nd International Conference on Data Engineering （ICDE'06）. Atlanta， Georgia：IEEE， 2006： 75.

[8]WEI Hao， YU J X， LU C，et al. Reachability querying： An independent permutation labeling approach[J]. The VLDB Journal， 2018，27：1-26.

[9]YANO Y， AKIBA T， IWATA Y， et al. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. San Francisco， CA，USA：ACM， 2013： 1601-1606.

[10]CHENG J， SHANG Zechao， CHENG Hong， et al. K-reach： Who is in your small world[J]. Proceedings of the VLDB Endowment， 2012， 5（11）： 1292-1303.

[11]BUNDY A， WALLEN L. Breadth-first search [M]// Catalogue of Artificial Intelligence Tools.Symbolic Computation （Artificial Intelligence）. Berlin /Heidelberg： Springer ， 1984：13.

[12]STEIER D M， ANDERSON A P. Depth-first search [M]// Algorithm synthesis： A Comparative Study. US：Springer， 1989：47-62.

[13]YANO Y， AKIBA T， IWATA Y， et al. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM international conference on Information & Knowledge Management. San Francisco， CA，USA：ACM， 2013： 1601-1606.

[13]TANG Xian， CHEN Ziyang， LI Kai， et al. Efficient computation of the transitive closure size[J]. Cluster Computing，2019，22： 6517-6527.

[14]ZHOU Junfeng， ZHOU Shijie， YU J X， et al. DAG reduction： Fast answering reachability queries[C]//Proceedings of the 2017 ACM International Conference on Management of Data. Raleigh：ACM， 2017： 375-390.