有向無(wú)環(huán)圖上k步可達(dá)查詢優(yōu)化算法

杜 明，楊安平，周軍鋒*，陳子陽(yáng)，楊 云

（1.東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海201620；2.上海立信會(huì)計(jì)金融學(xué)院信息管理學(xué)院，上海201620）

0 引言

給定有向無(wú)環(huán)圖（Directed Acyclic Graph，DAG）G，可達(dá)性查詢u？→v用于回答從頂點(diǎn)u出發(fā)是否存在一條路徑可以到達(dá)頂點(diǎn)v。實(shí)際應(yīng)用中，如社交網(wǎng)絡(luò)、通信與傳感器網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、可擴(kuò)展標(biāo)記語(yǔ)言（eXtensible Markup Language，XML）數(shù)據(jù)、資源描述框架（Resource Description Framework，RDF）數(shù)據(jù)等，可達(dá)性查詢可用于檢測(cè)兩點(diǎn)間是否存在特定關(guān)系?？蛇_(dá)性查詢處理是圖數(shù)據(jù)管理與分析的基本操作之一，是研究者廣泛關(guān)注的熱點(diǎn)問(wèn)題［1-2］。然而，實(shí)際中除了檢測(cè)兩點(diǎn)間是否存在特定關(guān)系，還需要考慮關(guān)系的強(qiáng)弱程度，如存在信號(hào)衰減的傳感器網(wǎng)絡(luò)，用戶更感興趣的是長(zhǎng)度受限的可達(dá)性查詢。傳統(tǒng)的可達(dá)性查詢只能回答兩個(gè)頂點(diǎn)間是否可達(dá)，并不能確定在幾步內(nèi)可達(dá)。本文研究k 步可達(dá)查詢的高效處理問(wèn)題。與基本的可達(dá)性查詢相比，k步可達(dá)查詢用于回答從u出發(fā)，是否存在長(zhǎng)度在k 步之內(nèi)的路徑到v。傳統(tǒng)的可達(dá)查詢可以看作k=∞時(shí)的k 步可達(dá)查詢［3］。由于k 步可達(dá)性查詢體現(xiàn)著圖中頂點(diǎn)對(duì)其他頂點(diǎn)的影響力，因而相對(duì)可達(dá)性查詢而言，能提供更多的信息。

現(xiàn)有解決k 步可達(dá)性查詢的方法主要分為兩類(lèi)：Label-Only［4］和Label+G［5-7］。Label-Only類(lèi)方法的主要思想是通過(guò)構(gòu)建所有可達(dá)頂點(diǎn)間最短路徑的索引，當(dāng)判斷從頂點(diǎn)u能否在k步內(nèi)到達(dá)頂點(diǎn)v 時(shí)，只需通過(guò)標(biāo)簽得到u 和v 之間的最短路徑長(zhǎng)度，然后比較從u 到v 的最短路徑長(zhǎng)度與k 的大小關(guān)系。當(dāng)最短距離大于k 時(shí)，說(shuō)明該查詢不滿足k 步可達(dá)性，否則說(shuō)明該查詢滿足k 步可達(dá)性。Label+G 類(lèi)方法的主要思想是快速構(gòu)建部分可達(dá)信息的索引，處理查詢時(shí)，若索引可回答查詢，則直接返回結(jié)果；否則需要通過(guò)圖遍歷來(lái)得到最終結(jié)果。相比較而言，Label-Only類(lèi)方法的索引規(guī)模大、索引構(gòu)建時(shí)間長(zhǎng)，且當(dāng)查詢不可達(dá)時(shí)，處理效率低。而現(xiàn)有的Label+G 類(lèi)方法由于索引記錄的可達(dá)信息少，查詢處理時(shí)需要遍歷的頂點(diǎn)較多，當(dāng)滿足條件的查詢數(shù)量增多時(shí)，算法性能顯著下降。

針對(duì)以上問(wèn)題，本文提出一種求解k 步可達(dá)查詢的高效Label+G算法kRH。其基本思想是通過(guò)快速構(gòu)建索引規(guī)模小、可達(dá)信息覆蓋廣的索引，從而可以在常量時(shí)間回答更多的查詢，同時(shí)降低圖遍歷的代價(jià)。具體來(lái)說(shuō)，本文的工作如下：

1）提出一種基于部分點(diǎn)的雙向最短路徑索引，用于在常量時(shí)間回答大部分k 步可達(dá)查詢，并提出三種啟發(fā)式規(guī)則來(lái)減小索引規(guī)模。

2）提出基于簡(jiǎn)化圖的正反互逆拓?fù)鋪?lái)提高不可達(dá)查詢的處理效率。

3）提出遠(yuǎn)距離優(yōu)先的雙向搜索策略，并在此基礎(chǔ)上提出高效的查詢處理策略。

4）基于多個(gè)真實(shí)的數(shù)據(jù)集進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果顯示，本文提出的方法比現(xiàn)有方法更高效。

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

1.1 數(shù)據(jù)模型及相關(guān)概念

本文處理有向無(wú)環(huán)圖（DAG）上的k 步可達(dá)查詢。給定DAG，V 表示頂點(diǎn)的集合，E 表示邊的集合。后續(xù)討論中，用(u，v)∈E 表示從u 到v 的邊，δ(u，v)表示u 與v 的最短路徑，Out(u)表示u 指向的頂點(diǎn)集，In(u)表示指向u 的頂點(diǎn)集。Out*(u)表示u 可達(dá)的頂點(diǎn)集，In*(u)表示可達(dá)u 的頂點(diǎn)集。給定G 中任意兩個(gè)頂點(diǎn)u 和v，若從u 到v 存在一條有向路徑，則說(shuō)明u 可達(dá)v，否則說(shuō)明u 不可達(dá)v。若從u 到v 存在一條長(zhǎng)度不大于k 的路徑，說(shuō)明從u 出發(fā)k 步可達(dá)v，用u →kv 表示；否則u不能在k步可達(dá)v，用u?kv表示。

對(duì)于一個(gè)DAG 來(lái)說(shuō)，它體現(xiàn)頂點(diǎn)之間的偏序關(guān)系，通過(guò)拓?fù)渑判颍瑢㈨旤c(diǎn)的偏序關(guān)系轉(zhuǎn)變?yōu)槿蜿P(guān)系，拓?fù)涮?hào)即為全序關(guān)系的序號(hào)。頂點(diǎn)u、v 的拓?fù)涮?hào)分別為Xu和Xv，若存在Xu＞Xv，u不可達(dá)v。

1.2 相關(guān)工作

1.2.1 可達(dá)查詢

針對(duì)圖論中的可達(dá)性查詢，按照索引覆蓋范圍的大小，分為兩大類(lèi)：1）構(gòu)建全索引的方式；2）構(gòu)建部分索引的方式。全索引方式的主要思想是通過(guò)記錄任意兩個(gè)頂點(diǎn)之間的可達(dá)信息來(lái)處理可達(dá)查詢?；谠撍枷?，文獻(xiàn)［8］采用傳遞閉包的方式記錄任意兩個(gè)頂點(diǎn)間的可達(dá)信息，該算法雖然能夠在O(1)的時(shí)間復(fù)雜度內(nèi)處理查詢，缺點(diǎn)是空間復(fù)雜度是，實(shí)際中擴(kuò)展性太差，無(wú)法應(yīng)用于大圖。文獻(xiàn)［9］采用壓縮傳遞閉包的方式，通過(guò)向上向下遍歷給圖中每個(gè)頂點(diǎn)v 附加兩個(gè)區(qū)間LIN(v)和LOUT(v)。當(dāng)需要判斷u 與v是否可達(dá)時(shí)，僅需要判斷u 和v 之間是否存在交集，若交集不為空，則說(shuō)明u 可達(dá)v；否則，u 不可達(dá)v。部分索引方式的主要思想是通過(guò)記錄部分頂點(diǎn)之間的可達(dá)信息配合遍歷的方式來(lái)處理可達(dá)查詢?；谠撍枷耄珿RIPP算法［10］給所有頂點(diǎn)附加一個(gè)區(qū)間，并通過(guò)區(qū)間包含來(lái)判斷頂點(diǎn)間是否可達(dá)，若區(qū)間不包含，則需要通過(guò)遍歷的方法才能判定。Grial 算法［11］在GRIPP 算法的基礎(chǔ)上，采用不同的遍歷方式給圖中所有頂點(diǎn)附加多個(gè)區(qū)間，同樣是采用區(qū)間包含判定是否可達(dá)，對(duì)于不能判斷的查詢，需要采用遍歷的方式才能夠判斷。FELINE 算法［12］通過(guò)給圖中每個(gè)頂點(diǎn)附加兩個(gè)整數(shù)，代表頂點(diǎn)在圖中拓?fù)渑判虻男蛱?hào)，若頂點(diǎn)u 的拓?fù)湫蛱?hào)大于v的拓?fù)湫蛱?hào)，則可以判定u不可達(dá)v。

1.2.2 Label-Only方法

Label-Only 方法的思想是通過(guò)記錄所有頂點(diǎn)對(duì)之間的最短路徑長(zhǎng)度來(lái)回答k 步可達(dá)查詢。基于該思想，一種簡(jiǎn)單的方法是直接記錄所有頂點(diǎn)對(duì)之間的最短路徑長(zhǎng)度，該方法雖然可以O(shè)(1)時(shí)間回答k步可達(dá)查詢，但空間復(fù)雜度為在實(shí)際應(yīng)用中可擴(kuò)展性太差，無(wú)法處理大圖。針對(duì)該問(wèn)題，文獻(xiàn)［9］提出一種壓縮的最短路徑索引PLL（Pruned Landmark Labeling）。其基本思想是為圖中的每一個(gè)頂點(diǎn)v 建立LIN(v)和LOUT(v)兩個(gè)標(biāo)簽，其中LIN(v)標(biāo)簽用來(lái)記錄頂點(diǎn)v與In*(v)中部分頂點(diǎn)間的最短路徑，LOUT(v)用來(lái)記錄v 與Out*(v)中部分頂點(diǎn)間的最短路徑。則u 和v 之間的最短路徑δ(u，v)的計(jì)算問(wèn)題就轉(zhuǎn)換為求解中間節(jié)點(diǎn)和u、v 最短路徑之和的最小值問(wèn)題。當(dāng)需要回答從u 到v 是否k 步可達(dá)時(shí)，只需判斷LIN(v)和LOUT(v)是否存在交集。若不存在交集，則說(shuō)明兩個(gè)頂點(diǎn)不滿足k 步可達(dá)；若存在交集，說(shuō)明u 通過(guò)交集中的任意一個(gè)頂點(diǎn)都可到達(dá)v。基于交集結(jié)果，可得到所有交集頂點(diǎn)與u 和v之間的最短路徑之和，則u和v之間的最短路徑δ(u，v)就等于最短路徑之和中的最小值。如果δ(u，v)≤k，說(shuō)明u →kv；否則，說(shuō)明u?kv。

該方法的問(wèn)題在于兩方面：1）索引規(guī)模大、索引時(shí)間長(zhǎng)，原因在于需要記錄完整的最短路徑信息；2）對(duì)不可達(dá)查詢的處理效率較低，原因是LOUT(u)與LIN(v)的交集為空意味著需要訪問(wèn)LOUT(u)與LIN(v)中的所有信息。

1.2.3 Label+G方法

由于通過(guò)直接遍歷回答查詢的效率太低，而Label-Only方法的索引時(shí)間長(zhǎng)、索引規(guī)模大，研究者試圖通過(guò)僅記錄部分k 步可達(dá)信息來(lái)在效率方面進(jìn)行平衡。其基本思想是在線性或者近似線性時(shí)間復(fù)雜度內(nèi)記錄部分k 步可達(dá)信息，用于減小遍歷操作的搜索空間，根據(jù)其剪枝能力的不同，分為三種類(lèi)型的方法。

第一類(lèi)方法是直接使用傳統(tǒng)的可達(dá)查詢處理方法［10-11］來(lái)回答不可達(dá)查詢，對(duì)于可達(dá)查詢，通過(guò)直接遍歷的方法檢測(cè)是否滿足k 步的條件。該類(lèi)方法雖然索引時(shí)間少，索引規(guī)模小，但當(dāng)滿足條件的查詢數(shù)量增多時(shí)，效率異常低下。

第二類(lèi)方法是構(gòu)建可回答部分k 步可達(dá)查詢的索引來(lái)加快查詢處理的速度。文獻(xiàn)［5-7］基于頂點(diǎn)覆蓋技術(shù)構(gòu)建k 步索引。其基本思想是首先求得原圖的一個(gè)頂點(diǎn)覆蓋集合，然后在頂點(diǎn)覆蓋集上構(gòu)建傳遞閉包作為索引，最后根據(jù)該索引來(lái)處理k 步可達(dá)查詢。這種方法的問(wèn)題是索引只能回答固定k值的可達(dá)查詢，擴(kuò)展性較差。

第三類(lèi)方法［3］采用FELINE 算法［12］作為特定的剪枝條件，來(lái)快速回答不可達(dá)查詢，對(duì)于其他查詢，則提出基于廣度優(yōu)先生成樹(shù)以及廣度層作為剪枝條件來(lái)提高k 步可達(dá)查詢的處理效率。該方法為生成樹(shù)的每個(gè)頂點(diǎn)附加一個(gè)區(qū)間，用于判斷頂點(diǎn)之間的祖先后代關(guān)系。若L(v)?L(u)，說(shuō)明v 是u 的后代，則查詢可通過(guò)比較u 和v 之間的層數(shù)差來(lái)判斷；若L(v)?L(u)，說(shuō)明v不是u的后代，則需要遞歸判斷u的后代中是否存在頂點(diǎn)p，滿足L(v)?L(p)。該算法的缺點(diǎn)是生成樹(shù)的區(qū)間覆蓋率很低，因此，當(dāng)滿足條件的查詢數(shù)量增多時(shí)，查詢效率較低。

相比較而言，Label-Only方法雖然查詢處理時(shí)無(wú)需遍歷操作，但索引規(guī)模大、索引構(gòu)建時(shí)間長(zhǎng)，同時(shí)對(duì)不可達(dá)查詢的處理效率較低；而Label+G 方法雖然索引構(gòu)建時(shí)間短、索引規(guī)模小，但查詢處理時(shí)因需要遍歷操作而顯得效率較低，尤其是當(dāng)滿足條件的查詢?cè)龆鄷r(shí)，效率顯著下降。本文針對(duì)該問(wèn)題，提出一種增強(qiáng)的Label+G 方法，在降低索引規(guī)模的前提下，通過(guò)增強(qiáng)不可達(dá)查詢和可達(dá)查詢的剪枝效果來(lái)縮減遍歷操作的搜索空間，提升k步可達(dá)查詢的處理效率。

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

2.1 雙向最短距離索引的基本思想

本文提出基于部分出度與入度之和較大的頂點(diǎn)（簡(jiǎn)稱(chēng)hop點(diǎn)）建立雙向最短路徑索引來(lái)加速k 步可達(dá)的判斷，這里雙向的意思是不僅記錄a與其可達(dá)點(diǎn)的最短距離，而且記錄a與可達(dá)a 的點(diǎn)的最短距離。具體來(lái)說(shuō)，類(lèi)似于2hop 索引［4］，本文為每個(gè)點(diǎn)v 設(shè)定兩個(gè)標(biāo)簽LIN(v)和LOUT(v)。和2hop 索引的不同在于，兩個(gè)標(biāo)簽中不僅僅記錄了可達(dá)信息，而且記錄了最短路徑信息。其中前者LIN(v)用于存儲(chǔ)可達(dá)v 及其與v 的最短路徑，后者LOUT(v)存儲(chǔ)v可達(dá)的點(diǎn)及其與v的最短距離。

圖1 有向無(wú)環(huán)圖G的示例Fig.1 Example of DAG G

例如，對(duì)圖1 的G，假設(shè)頂點(diǎn)的處理順序是c →a →b →d →e →f →g。當(dāng) 處 理c 時(shí)，其 可 達(dá) 點(diǎn) 為c，e，f，g，可達(dá)c 的點(diǎn)為a，b。因此將元組加入到LIN(u（)其中u ∈{c，e，f，g}）中，這里dis 表示c 到u 的最短路徑長(zhǎng)度。類(lèi)似地，將加入LOUT(v)中（其中v ∈{a，b}），這里dis表示v和c 的最短路徑長(zhǎng)度。表1 是基于圖1 所有頂點(diǎn)構(gòu)建的最短路徑索引。

表1 基于所有頂點(diǎn)的最短路徑索引Tab.1 Shortest path index based on all points

基于表1的索引，則給定任意兩點(diǎn)a和b，判斷a是否可在k 步到達(dá)b，則只需比較LOUT(a)和LIN(b)：如果二者的交集為空，說(shuō)明a 不可達(dá)b；否則說(shuō)明a 可達(dá)b。如果a 可達(dá)b，將a 通過(guò)交集中每個(gè)點(diǎn)到達(dá)b 的路徑長(zhǎng)度計(jì)算出來(lái)，取其最小值即為a 和b 的最短路徑長(zhǎng)度。如果該長(zhǎng)度小于給定的k 值，則說(shuō)明a可以在k步可達(dá)b，否則a不能在k步到達(dá)b。

2.2 雙向最短距離索引的優(yōu)化

雖然該索引可回答所有查詢，且無(wú)需在圖上執(zhí)行遍歷操作，但其索引規(guī)模太大，且求解交集的代價(jià)太高。為此，提出僅構(gòu)建部分點(diǎn)的雙向路徑索引來(lái)減小索引規(guī)模。原因在于：1）實(shí)際中的圖存在少量度很大的點(diǎn)，相應(yīng)地，其可達(dá)頂點(diǎn)也通常比較多，選擇這樣的點(diǎn)構(gòu)建雙向最短路徑可以顯著增加所維護(hù)的可達(dá)點(diǎn)對(duì)數(shù)量及通過(guò)這種點(diǎn)的最短路徑長(zhǎng)度。2）我們的實(shí)驗(yàn)表明，對(duì)一般圖來(lái)說(shuō)，要么32 個(gè)點(diǎn)已經(jīng)維護(hù)了足夠多的可達(dá)信息，再增加頂點(diǎn)后，可達(dá)信息并沒(méi)有明顯增加；要么32 個(gè)點(diǎn)僅維護(hù)少量可達(dá)信息，再增加這種點(diǎn)同樣不會(huì)顯著增加可達(dá)信息維護(hù)量。如圖2 所示，從實(shí)際數(shù)據(jù)上的測(cè)試結(jié)果可以看出：對(duì)于amaze 數(shù)據(jù)集，即使k=1，雙向索引的可達(dá)覆蓋率也可接近100%；而對(duì)cit-Patents 而言，即使k 值增加到32，可達(dá)覆蓋率依然非常??；另外兩個(gè)數(shù)據(jù)集上，當(dāng)k 值增加到16以后，數(shù)據(jù)基本不再發(fā)生變化。

圖2 k個(gè)hop 點(diǎn)可達(dá)覆蓋率Fig.2 Coverage of reachability for k hop nodes

基于以上觀察，取32 個(gè)點(diǎn)構(gòu)建雙向最短路徑索引。假設(shè)對(duì)于圖1 所示的DAG G，本文取c 和f 兩個(gè)點(diǎn)構(gòu)建雙向最短路徑索引，如表2 所示。顯然，和表1 的索引相比，表2 的規(guī)模降低了。實(shí)際上，表2還可以進(jìn)一步優(yōu)化。

表2 基于c和f的最短路徑索引Tab.2 Shortest path index based on c and f

定理1當(dāng)基于頂點(diǎn)v 構(gòu)建雙向最短路徑索引時(shí)，如果向上（向下）遍歷的過(guò)程中遇到了已處理的hop 點(diǎn)u，則無(wú)需從u繼續(xù)向上（向下）遍歷。

證明 如圖3 所示，假設(shè)x 可達(dá)u，當(dāng)前處理的是hop 點(diǎn)v，hop點(diǎn)u在v之前處理。當(dāng)從v向上遍歷時(shí)遇到了u?；趗得到的標(biāo)簽，假設(shè)求得x 到u 的距離是d1，u 到v的距離是d2，則x通過(guò)u 到v 的距離是d1+d2。顯然，從v 向上遍歷遇到u，所求u 與v 之間的距離仍然是d2，因此即使在u 不停止，所得x 和v的距離仍然是d1+d2，因此，無(wú)需從u繼續(xù)向上遍歷。

圖3 hop點(diǎn)作用示意圖Fig.3 Schematic diagram of hop nodes intension

定理2當(dāng)基于頂點(diǎn)v 構(gòu)建雙向最短路徑索引時(shí)，如果向上（向下）遍歷的過(guò)程中通過(guò)非hop點(diǎn)遇到了w，且w通過(guò)u到v的距離小于w 通過(guò)非hop 點(diǎn)到v 的距離，則無(wú)需從w 繼續(xù)向上（向下）遍歷。

證明 如圖3 所示，假設(shè)hop 點(diǎn)u 先處理，目前處理的是hop 點(diǎn)v。假設(shè)從v 向上遍歷，通過(guò)非hop 點(diǎn)到達(dá)w，路徑長(zhǎng)度是d4。如果w 和u的最短距離是d3，且d3+d2≤d4，顯然無(wú)需在LOUT(w)中記錄其和v 的距離d4，因?yàn)閐4不是最短距離。因此，無(wú)需從w開(kāi)始繼續(xù)向上遍歷。

基于定理1和定理2，在求解雙向最短路徑索引的過(guò)程中可有效減小索引規(guī)模，提高索引構(gòu)建的速度。例如，對(duì)圖1 的G 而言，假設(shè)選擇兩個(gè)hop 點(diǎn)c 和f 來(lái)構(gòu)建雙向最短路徑索引。先處理的是點(diǎn)c，當(dāng)處理第二個(gè)點(diǎn)f時(shí)，當(dāng)從其向上遍歷遇到第一個(gè)hop 點(diǎn)c時(shí)，可根據(jù)定理1 立即停止遍歷，當(dāng)從非hop 點(diǎn)遍歷到b 時(shí)，可根據(jù)定理2 立即停止遍歷。當(dāng)處理完這兩個(gè)點(diǎn)后，所得到的雙向路徑索引如表3所示。

表3 基于c和f的優(yōu)化后的最短路徑索引Tab.3 Optimized shortest path index based on c and f

3 基于棧的正反互逆拓?fù)?/h2>

可達(dá)是k步可達(dá)的必要條件，因此，若查詢不可達(dá)，則必定k步不可達(dá)?；诖?，本文使用拓?fù)湫蛱?hào)為基礎(chǔ)的方法來(lái)快速判斷不可達(dá)。其基本思想是：給定兩個(gè)頂點(diǎn)u和v，若u的拓?fù)涮?hào)大于v的拓?fù)涮?hào)，則u不可達(dá)v，因此u在k步內(nèi)不可達(dá)v。

文獻(xiàn)［3］通過(guò)使用互逆的兩個(gè)拓?fù)涮?hào)來(lái)增強(qiáng)不可達(dá)查詢的判斷能力。具體而言，給定第一個(gè)拓?fù)漤樞颍跇?gòu)建逆序拓?fù)鋾r(shí)，始終優(yōu)先訪問(wèn)第一個(gè)拓?fù)涮?hào)最大且所有入鄰居均被訪問(wèn)的頂點(diǎn)。以此建立的拓?fù)浞Q(chēng)為第一遍拓?fù)涞哪嫦蛲負(fù)?。雖然實(shí)際中互逆拓?fù)淇煽焖倥袛嗪芏嗖豢蛇_(dá)查詢，但仍然存在兩方面的問(wèn)題。

首先，在實(shí)際應(yīng)用中，基于正向建立的兩個(gè)互逆拓?fù)涮?hào)仍然存在很多不可達(dá)查詢無(wú)法判斷的問(wèn)題。針對(duì)該問(wèn)題，本文提出構(gòu)建正反互逆拓?fù)鋪?lái)過(guò)濾更多的不可達(dá)查詢。其基本思想是：首先，刪除已處理的hop 點(diǎn)。原因是與hop 點(diǎn)關(guān)聯(lián)的最短路徑均已處理完畢，后續(xù)的最短路徑計(jì)算與其無(wú)關(guān)。刪除hop點(diǎn)之后，數(shù)據(jù)圖得以很大程度上的簡(jiǎn)化。其次，自頂向下、以深度優(yōu)先的方式構(gòu)建正向互逆拓?fù)?。最后，沿著邊的相反方向，以自底向上，以深度?yōu)先的方式構(gòu)建反向互逆拓?fù)洹?/p>

其次，文獻(xiàn)［12］基于堆求解逆序拓?fù)洌鋾r(shí)間復(fù)雜度為O(|V|log|V|)。本文設(shè)計(jì)了高效算法在線性時(shí)間構(gòu)建正反互逆拓?fù)洹Ｅc以上工作相比，由于首先刪除了hop 點(diǎn)，因而所建立的正反互逆拓?fù)淇梢赃^(guò)濾更多的不可達(dá)查詢。和文獻(xiàn)［12］相比，本文提出的正反互逆拓?fù)渌饕哂芯€性的時(shí)間復(fù)雜度，同時(shí)能過(guò)濾更多的不可達(dá)查詢。和文獻(xiàn)［3］的方法相比，由于我們?cè)谇蠼庹椿ツ嫱負(fù)渲叭コ薶op 點(diǎn)，數(shù)據(jù)圖得以很大程度的簡(jiǎn)化，因而效率更高。

4 索引構(gòu)建

4.1 基于hop點(diǎn)的最短距離索引構(gòu)建

4.1.1 算法描述

給定DAG G，求解hop 點(diǎn)的最短路徑索引總體上分為3步。首先求解hop 點(diǎn)，然后基于hop 點(diǎn)執(zhí)行廣度優(yōu)先遍歷（Breadth First Search，BFS）建立LIN索引，最后基于hop 點(diǎn)執(zhí)行反向BFS建立LOUT索引。下面分別予以說(shuō)明。

（1）根據(jù)(In(v)+1)*(Out(v)+1)從大到小的順序選擇前32個(gè)頂點(diǎn)作為hop點(diǎn)。如算法1第1）行。

（2）從hop 點(diǎn)v 開(kāi)始執(zhí)行BFS，對(duì)于遍歷到的頂點(diǎn)u，若是通過(guò)標(biāo)簽計(jì)算得到了長(zhǎng)度大于從v 到u 的路徑長(zhǎng)度，則更新LIN(u)并繼續(xù)訪問(wèn)u可達(dá)的點(diǎn)；若是通過(guò)標(biāo)簽計(jì)算得到的長(zhǎng)度小于從v 點(diǎn)到u 的路徑長(zhǎng)度，則不更新LIN(u)且不再?gòu)膗 出發(fā)繼續(xù)BFS。如算法1第2）～12）行所示。

（3）從hop點(diǎn)開(kāi)始執(zhí)行反向BFS，對(duì)于遍歷到的頂點(diǎn)u，若是通過(guò)標(biāo)簽得到的長(zhǎng)度大于從hop點(diǎn)到u的路徑長(zhǎng)度，則更新LOUT(u)并且訪問(wèn)u的父親；若通過(guò)標(biāo)簽得到的長(zhǎng)度小于從hop點(diǎn)到u 的路徑長(zhǎng)度，則不更新LOUT(u)且不訪問(wèn)u 的父親。如算法1第13）行所示。

算法1 hop(G=(V，E))。

算法1 用于求解基于hop 頂點(diǎn)的最短路徑，其中QU(v，u，LOUT(v)，LIN(u))表示通過(guò)標(biāo)簽求解得到從v 到u 的最短路徑長(zhǎng)度，Dis(v，u)表示基于BFS得到從v到u路徑長(zhǎng)度，初始值為0，Q表示隊(duì)列。算法1中第1）行按照規(guī)則選擇度大的32 個(gè)頂點(diǎn)作為hop 點(diǎn)。第2）、3）行將hop 點(diǎn)依次執(zhí)行入隊(duì)操作。當(dāng)隊(duì)列不空時(shí)，執(zhí)行出隊(duì)操作（第5）、6）行）。若通過(guò)標(biāo)簽求得的最短路徑不大于遍歷的路徑長(zhǎng)度，則停止訪問(wèn)其后代（第7）、8）行）；否則，更新LIN標(biāo)簽，并將其后代加入到Q 中（第9）～12）行）。將hop點(diǎn)v再入隊(duì)列，通過(guò)執(zhí)行反向BFS構(gòu)建第13）行）。

注 意，算 法1 中 需 要 在 第7）行 調(diào) 用 函 數(shù)QU(v，u，LOUT(v)，LIN(u))求解根據(jù)已處理hop 點(diǎn)得到的路徑長(zhǎng)度。這一操作需要比較LOUT和LIN，即執(zhí)行集合求交集的操作。為了加快集合交集操作的處理，需要先對(duì)集合中的頂點(diǎn)按照編號(hào)，或者某種序號(hào)進(jìn)行排序。

4.1.2 索引優(yōu)化

若v 和u 之 間 通 過(guò)hop 點(diǎn) 有 路 徑 相 連，則 函 數(shù)QU(v，u，LOUT(v)，LIN(u))進(jìn)行集合交集操作的結(jié)果是經(jīng)過(guò)hop 點(diǎn)相連的路徑長(zhǎng)度，無(wú)需知道hop 點(diǎn)是誰(shuí)。因此，采用如下規(guī)則對(duì)算法1進(jìn)行優(yōu)化。

規(guī)則1 所有頂點(diǎn)的LIN或者LOUT中無(wú)需存儲(chǔ)頂點(diǎn)自身編號(hào)，只需存儲(chǔ)代表頂點(diǎn)處理順序的數(shù)字即可。

根據(jù)規(guī)則1，構(gòu)建索引時(shí)，無(wú)需執(zhí)行排序操作，對(duì)第i 個(gè)處理的hop 點(diǎn)，直接在相應(yīng)頂點(diǎn)的標(biāo)簽中加入即可，這里的i表示當(dāng)前hop點(diǎn)是第i個(gè)被處理的hop點(diǎn)，dis是hop點(diǎn)和當(dāng)前點(diǎn)的最短路徑距離。

進(jìn)一步，由于只選擇了32個(gè)hop點(diǎn)，且實(shí)際中數(shù)據(jù)圖的拓?fù)鋵訑?shù)有限，因此無(wú)需使用兩個(gè)整數(shù)來(lái)表示標(biāo)簽中的元組。利用規(guī)則2來(lái)進(jìn)一步減少索引規(guī)模。

4.2 正反互逆拓?fù)錁?gòu)建

求解正反互逆的拓?fù)涮?hào)索引總體上分為4 步：首先刪除32 個(gè)hop 點(diǎn)，然后求解正向的拓?fù)涮?hào)X，接著基于X 求其逆向拓?fù)涮?hào)Y，最后在反向圖上求解兩個(gè)拓?fù)涮?hào)索引M和N。

給定一個(gè)有向無(wú)環(huán)圖G，可以通過(guò)以下步驟得到X：1）將G中入度為0的頂點(diǎn)入棧S。2）對(duì)棧中元素執(zhí)行以下操作：（a）將S的棧頂元素v出棧，并標(biāo)記v的拓?fù)漤樞颍唬╞）刪除v及所有從v 出發(fā)的邊；（c）將v 的孩子中入度為0 的頂點(diǎn)插入S。3）重復(fù)步驟2）直到S為空，相應(yīng)的頂點(diǎn)出棧順序稱(chēng)為X。

給定X，同樣基于棧可以得到其逆向拓?fù)漤樞験?；静僮鞣椒ㄈ缦拢菏紫人腥攵葹? 的頂點(diǎn)按照它們?cè)赬 中從小到大的順序進(jìn)入棧S。對(duì)棧中元素執(zhí)行以下操作：1）將S的棧頂元素v 出棧，并標(biāo)記v 的逆向拓?fù)涮?hào)；2）刪除v 及從v 出發(fā)的邊；3）將v的孩子中入度為0 的頂點(diǎn)按照它們?cè)赬 中從小到大的順序入棧。執(zhí)行上述步驟，直至棧空即可得到第二次拓?fù)漤樞験。

定理3求解逆向拓?fù)鋾r(shí)，棧頂元素和使用堆選擇的拓?fù)涮?hào)最大的元素為相同頂點(diǎn)。

證明 首先，使用大頂堆時(shí)，堆頂元素是當(dāng)前堆中拓?fù)涮?hào)最大的頂點(diǎn)。其次，使用棧時(shí)，本文首先將入度為0 的頂點(diǎn)按照第一遍拓?fù)涞捻樞驈男〉酱笕霔?，因此可以保證對(duì)初始入度為0 的頂點(diǎn)，棧頂元素的拓?fù)涮?hào)最大。最后，由于棧頂元素的拓?fù)涮?hào)最大，其孩子的拓?fù)涮?hào)必然也大于棧中元素的拓?fù)涮?hào)。每處理一個(gè)棧頂元素，其孩子中可進(jìn)一步拓?fù)涞捻旤c(diǎn)也是按照第一遍拓?fù)涞捻樞驈男〉酱笕霔＃@樣可以保證棧頂元素始終具有最大的拓?fù)涮?hào)。因而可以保證每次處理的都是可拓?fù)涞捻旤c(diǎn)中拓?fù)涮?hào)最大的。

算法2 genTopo(G=(V，E))。

輸入 G=(V，E)；

輸出 所有頂點(diǎn)v的四個(gè)拓?fù)湫蛱?hào)X，Y，M，N。

1） 從G中刪除32個(gè)hop點(diǎn)

2） Construct(G，X)

3） Construct(G，Y)

4） 將G的邊反轉(zhuǎn)，執(zhí)行第1)～2)行，求解反向互逆拓?fù)?/p>

第2）、3）行都是調(diào)用的Construct函數(shù)，代碼如下所示：

Function Construct(G=(V，E)，H)

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

2） topoNum ←0

3） while S ≠? do

4） v ←pop(S)

5） HV←topoNum

6） topoNum ←topoNum+1

7） for each u ∈Out(v) do

8） insize(u)←insize(u)-1

9） if insize(u)=0 then push u into S

在得到正向互逆的拓?fù)浜?，將圖的邊反轉(zhuǎn)，在反向圖上執(zhí)行上述步驟，從而得到反向圖上的拓?fù)涮?hào)M 和N。最終，這4個(gè)拓?fù)漤樞驑?gòu)成本文提出的正反互逆的拓?fù)涮?hào)索引。

算法2 用于求解給定的DAG G 的正反互逆拓?fù)湫蛱?hào)，其中第2）行調(diào)用函數(shù)Construct 求解第一個(gè)拓?fù)漤樞騒，第3）行求X 的逆向拓?fù)鋂，第4）行求解反向互逆拓?fù)銶 和N。函數(shù)Construct 用于根據(jù)特定順序得到一個(gè)拓?fù)湫蛱?hào)，其中S 為棧，Hv表示頂點(diǎn)的拓?fù)湫蛱?hào)。insize(v)表示存儲(chǔ)頂點(diǎn)v 入度的臨時(shí)數(shù)組。第1）行將圖中入度為0 的頂點(diǎn)入棧。從第3）～9）行的迭代中，每循環(huán)一次處理一個(gè)頂點(diǎn)。具體做法是，第4）～5）行元素出棧并設(shè)定其拓?fù)涮?hào)，然后在第7）～9）行將其出鄰居的入度減1，若入度為0，則將其入棧。需要注意的是，算法第1）行，對(duì)于第一和第三遍拓?fù)?，特定順序不代表任何含義，只要找到一個(gè)入度為0 的頂點(diǎn)就將其入棧。第二遍和第四遍求的分別是第一、三遍的逆向拓?fù)?，這時(shí)，特定順序代表在第一邊拓?fù)浜?，根?jù)第一遍拓?fù)湫蛱?hào)的升序?qū)⑷攵葹? 的頂點(diǎn)入棧，這樣就能保證第一、二遍拓?fù)浠ツ?，第三、四遍拓?fù)浠ツ?。另外，?）行按照存儲(chǔ)順序處理，當(dāng)執(zhí)行第一遍拓?fù)浜?，圖的鄰接表中頂點(diǎn)按照拓?fù)涮?hào)升序排序，且第二遍處理的是基于拓?fù)渑判蚝蟮泥徑颖磉M(jìn)行處理。這么做是為了在保證互逆的基礎(chǔ)上，避免排序操作。

對(duì)圖1的G 而言，在求解正反拓?fù)涮?hào)之前，首先刪除32個(gè)hop 點(diǎn)，得到簡(jiǎn)化的圖，之后執(zhí)行算法2 后，給每個(gè)頂點(diǎn)賦予4個(gè)拓?fù)涮?hào)。

給定DAG G=(V，E)，刪除32個(gè)hop點(diǎn)的操作可在線性時(shí)間內(nèi)完成。由于函數(shù)Construct 在執(zhí)行過(guò)程中始終沒(méi)有執(zhí)行特定的排序操作，在每次執(zhí)行函數(shù)Construct時(shí)，每個(gè)頂點(diǎn)v 的處理代價(jià)是，因此函數(shù)Construct 的時(shí)間復(fù)雜度是。算法2 總共調(diào)用了4 次函數(shù)Construct，因此算法2的時(shí)間復(fù)雜度是。

5 查詢

算法3 用于判定查詢的k 步可達(dá)性。其中QU(v，u，LOUT(v)，LIN(u))表示通過(guò)標(biāo)簽求解得到的最短路徑長(zhǎng)度。算法3的第1）、2）行采用hop點(diǎn)的最短路徑索引判定該查詢是否滿足k步可達(dá)性。具體來(lái)說(shuō)：若通過(guò)最短路徑索引求得從u到v的最短路徑不大于k，說(shuō)明該查詢滿足k步可達(dá)；否則若最短路徑大于k并且查詢中的頂點(diǎn)存在hop點(diǎn)，說(shuō)明該查詢不滿足k 步可達(dá)性（第3）行）。若上述條件均不能判定查詢的k 步可達(dá)性，則在第4）、5）行采用正反互逆的拓?fù)涮?hào)判定查詢的可達(dá)性：若查詢不可達(dá)，則說(shuō)明該查詢不滿足k 步可達(dá)；否則，在第6）～13）行以遞歸的方式執(zhí)行遍歷操作。

算法3 kRH (u，v，k，G=(V，E))。

輸入 G=(V，E)；

輸出 true or false。

1） if QU(v，u，LOUT(v)，LIN(u))≤k

2） return true

4） if Xu＞Xvor Yu＞Yvor Mu＜Mvor Nu＜Nv

5） return false

6） if Out(u) ≤ In(v) then

7） for each p in Out(u)do

8） if kRH(p，v，k-1)

9） return true

10）else

11） for each p in In(v) do

12） if kRH(u，p，k-1)

13） return true

基于如下兩個(gè)啟發(fā)式來(lái)加速遍歷的過(guò)程。

規(guī)則3 給定k 步可達(dá)查詢的兩個(gè)端點(diǎn)u 和v。若u 的出度大于v 的入度，則從v 出發(fā)向上遍歷找u；否則從u 出發(fā)向下遍歷找v。

規(guī)則4 當(dāng)從v 出發(fā)遍歷時(shí)，優(yōu)先選擇與其拓?fù)鋵酉嗖畲蟮捻旤c(diǎn)w進(jìn)行遍歷。

規(guī)則4 中拓?fù)鋵酉嗖钶^大，說(shuō)明v 通過(guò)w 可能更快到達(dá)目標(biāo)點(diǎn)。

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

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

根據(jù)相關(guān)工作分析可知，在Label-Only 類(lèi)算法中，PLL 查詢效率最高；在Label+G 類(lèi)算法中，根據(jù)文獻(xiàn)［3］，BFSI-B（Breadth First Search Index-Bilateral）算法比k-reach［5］更快，是Label+G類(lèi)算法中查詢效率最高的算法。因此，本文實(shí)驗(yàn)中用于比較的算法有BFSI-B［3］和PLL［9］。對(duì)于Label+G中第一類(lèi)方法而言，例如GRAIL，因其并非專(zhuān)門(mén)處理k步可達(dá)查詢，本文不再進(jìn)行比較。所有算法都采用C++實(shí)現(xiàn)，并使用GCC7.3.0進(jìn)行編譯。所有算法使用相同的數(shù)據(jù)集和查詢集，并在相同的平臺(tái)上運(yùn)行得到實(shí)驗(yàn)數(shù)據(jù)。機(jī)器配置是4 GB RAM 的Intel Core i5-3230 CPU（8 核，2.60 GHz）和Ubuntu18.04LTS。以索引規(guī)模、索引構(gòu)建時(shí)間、查詢時(shí)間作為評(píng)價(jià)指標(biāo)來(lái)比較三種算法的性能。本文方法中的hop點(diǎn)個(gè)數(shù)是32。

6.2 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集由21 個(gè)真實(shí)的數(shù)據(jù)集組成，這些數(shù)據(jù)集都廣泛地出現(xiàn)在圖論的可達(dá)性查詢研究［14-16］中，它們的統(tǒng)計(jì)信息如表4 所示。其中arxiv、citeseer、pubmed 來(lái)自引文獻(xiàn)［14］；cit系列的數(shù)據(jù)集來(lái)自文獻(xiàn)［6］，其非葉子頂點(diǎn)的平均出度為10到30；uniprot100m、uniprot150m 來(lái)自Uniprot 數(shù)據(jù)庫(kù)的注釋聯(lián)合 圖［15］，皆 是UniProt 的 完 整 資 源 描 述 框 架（Resource Description Framework，RDF）的子集；soc-LJ（soc-LiveJournall）是來(lái)自社會(huì)網(wǎng)絡(luò)的有向無(wú)環(huán)圖；wikiTalk是來(lái)自維基百科的有向無(wú)環(huán)圖；web-Google 是來(lái)自Google 網(wǎng)頁(yè)的有向無(wú)環(huán)圖；dbpedia 為知識(shí)圖；web-uk 是文獻(xiàn)［16］收集的網(wǎng)絡(luò)有向無(wú)環(huán)圖。由表4 可知，除了前5 個(gè)數(shù)據(jù)集的規(guī)模較小之外，其余數(shù)據(jù)集規(guī)模較大；|V |表示給定有向無(wú)環(huán)圖的頂點(diǎn)數(shù)量，|E |為邊的數(shù)量，|d |表示頂點(diǎn)的平均度。對(duì)于每個(gè)數(shù)據(jù)集，本文使用隨機(jī)生成的100 萬(wàn)個(gè)查詢進(jìn)行測(cè)試，算法的運(yùn)行時(shí)間為處理100萬(wàn)個(gè)查詢的總時(shí)間。

6.3 索引大小及時(shí)間

表5 和表6 分別給出了不同方法的索引大小和索引構(gòu)建時(shí)間。從索引大小來(lái)看，如表5 所示，可以看出：1）在所有數(shù)據(jù)集上，本文方法構(gòu)建的索引規(guī)模最小。2）對(duì)于規(guī)模較小的圖而言，三種方法的索引規(guī)模相差不大。3）當(dāng)圖是稠密圖時(shí)，PLL 算法建立的索引規(guī)模最大。原因在于，PLL 要構(gòu)建所有點(diǎn)的雙向索引，而B(niǎo)FSI-B 的索引規(guī)模與圖的頂點(diǎn)個(gè)數(shù)成正比，每個(gè)頂點(diǎn)對(duì)應(yīng)8個(gè)整數(shù)。本文方法kRH為每個(gè)頂點(diǎn)設(shè)定4個(gè)拓?fù)涮?hào)。雖然建立的是32 個(gè)hop 點(diǎn)的索引，但由于使用了提前終止條件以及每個(gè)hop 點(diǎn)關(guān)聯(lián)的頂點(diǎn)有限，平均到每個(gè)點(diǎn)，hop標(biāo)簽不會(huì)超過(guò)4個(gè)數(shù)字，因此索引規(guī)模比BFSI-B小。

表4 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息Tab.4 Statistics of experimental datasets

表5 不同數(shù)據(jù)集上的索引大小 單位：MBTab.5 Index size on different datasets unit：MB

在索引時(shí)間方面，如表6 所示。相比PLL，kRH 算法的索引構(gòu)建時(shí)間更短，尤其當(dāng)圖的規(guī)模大且稠密時(shí)更加明顯；相比BFSI-B，二者索引時(shí)間相差不大。

表6 不同數(shù)據(jù)集上的索引時(shí)間 單位：msTab.6 Index time on different datasets unit：ms

6.4 查詢時(shí)間

表7 展示了三種算法當(dāng)k=3 時(shí)的查詢處理時(shí)間。由表7可知，三種方法相比，本文算法所需時(shí)間最短。原因有兩方面：一方面，和PLL 相比，本文算法可以在常量時(shí)間處理不可達(dá)查詢；另一方面，和BFSI-B相比，本文算法基于4個(gè)拓?fù)涮?hào)，可在常量時(shí)間檢測(cè)更多的不可達(dá)查詢。由于PLL不能常量時(shí)間回答查詢，因此在表8 中和BFSI-B 比較了常量時(shí)間內(nèi)可判定的查詢個(gè)數(shù)，可以看出本文算法可在常量時(shí)間內(nèi)判定更多的查詢，因而可以獲得比BFSI-B更高的查詢響應(yīng)速度。

表7 k=3時(shí)不同數(shù)據(jù)集上的查詢時(shí)間 單位：msTab.7 Query time on different datasets when k=3 unit：ms

6.5 不同k值的查詢處理性能

圖4 分別展示了三種算法在不同特征的數(shù)據(jù)集上處理100 萬(wàn)個(gè)查詢時(shí)隨k 值變化的情況。可以看出，本文方法和PLL 對(duì)k 值的變化不敏感，而B(niǎo)FSI-B 的性能受k 值影響較大，隨著k 值的增加，其所需的查詢處理時(shí)間增長(zhǎng)較多。對(duì)于稀疏數(shù)據(jù)集來(lái)說(shuō)，k 值的變化對(duì)于BFSI-B 和kRH 算法的查詢時(shí)間影響不大；而對(duì)于稠密數(shù)據(jù)集（go_uniprot）來(lái)說(shuō)，BFSI-B 和kRH 算法的查詢時(shí)間隨著k 的增大而增加，但是BFSI-B 的增加幅度更大。這是因?yàn)閗RH算法比BFSI-B覆蓋程度更高。

圖4 不同數(shù)據(jù)集上三種算法的查詢時(shí)間對(duì)比Fig.4 Query time comparison of three algorithms on different datasets

表8 k=3時(shí)常量時(shí)間內(nèi)可判定的查詢數(shù)量Tab.8 Query answers can be determined in constant time when k=3

7 結(jié)語(yǔ)

針對(duì)已有k 步可達(dá)查詢方法存在的索引規(guī)模大、查詢響應(yīng)速度慢的問(wèn)題，本文提出通過(guò)構(gòu)建大度頂點(diǎn)的雙向最短路徑來(lái)提高可達(dá)查詢的覆蓋率，同時(shí)提出基于簡(jiǎn)化圖的正反互逆拓?fù)鋪?lái)提高常量時(shí)間內(nèi)不可達(dá)查詢的處理效率。本文還提出了一系列優(yōu)化方法來(lái)減小索引規(guī)模、提高查詢處理的效率?；谡鎸?shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，本文算法具有較小的索引規(guī)模和更快的查詢響應(yīng)速度，同時(shí)具有較好的擴(kuò)展性。最好情況下，在cit-Patents數(shù)據(jù)集上，與PLL算法相比，本文算法的索引規(guī)模和索引構(gòu)建時(shí)間僅為PLL 算法3%，查詢時(shí)間僅為PLL 算法的20%；和BFSI-B 算法相比，本文算法的索引僅為BFSI-B算法索引規(guī)模、查詢時(shí)間的一半。