遲賀宇，秦小麟，李 瑭，費(fèi) 珂

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106)

1 引 言

在計(jì)算機(jī)領(lǐng)域，圖查詢算法是圖論算法的重要組成部分，如今各種應(yīng)用程序領(lǐng)域都存在大規(guī)模圖形數(shù)據(jù)，如何對(duì)它們進(jìn)行高效的查詢，是一個(gè)巨大的挑戰(zhàn)，并且具有重要的價(jià)值和意義.

由于第二代互聯(lián)網(wǎng)的興起，特別是超大規(guī)模和高并發(fā)的社交網(wǎng)絡(luò)服務(wù)(Social Networking Services，SNS)類型的純動(dòng)態(tài)網(wǎng)站的出現(xiàn)，誕生了非關(guān)系型數(shù)據(jù)庫(kù)(Not only Structured Query Language，NoSQL)，其中圖數(shù)據(jù)庫(kù)(Graph Database)支持將數(shù)據(jù)的實(shí)體抽象為頂點(diǎn)，實(shí)體之間的關(guān)系抽象為邊，將數(shù)據(jù)以圖的形式進(jìn)行存儲(chǔ).對(duì)圖數(shù)據(jù)的操作不僅涉及數(shù)據(jù)頂點(diǎn)自身的信息，而且涉及數(shù)據(jù)頂點(diǎn)之間的結(jié)構(gòu)關(guān)系.可以將對(duì)圖數(shù)據(jù)的操作抽象為獲取特定頂點(diǎn)、獲取特定路徑、獲取特定子圖等，通過實(shí)現(xiàn)這些通用操作，實(shí)現(xiàn)圖數(shù)據(jù)的相關(guān)應(yīng)用.

根據(jù)2021年最新相關(guān)數(shù)據(jù)，新浪微博的注冊(cè)人數(shù)已經(jīng)超過5.23億，因此新浪微博的社交圖有超過5.23億個(gè)頂點(diǎn)，若以關(guān)注關(guān)系作為邊進(jìn)行存儲(chǔ)，大約會(huì)有500億條邊.而如此大規(guī)模的數(shù)據(jù)，隨著新用戶的增加，關(guān)系的建立與解除、圖結(jié)構(gòu)變換等現(xiàn)象時(shí)有發(fā)生.另一方面第五代通信技術(shù)與全球定位系統(tǒng)飛速發(fā)展，私家車數(shù)量增多，使得人們?cè)诔鲂星盎蛟诔鲂袝r(shí)習(xí)慣進(jìn)行路線規(guī)劃.以私家車為頂點(diǎn)，道路為邊的交通網(wǎng)絡(luò)中，往往需要發(fā)現(xiàn)兩點(diǎn)間滿足不同標(biāo)準(zhǔn)的路徑，如紅綠燈最少的道路、同行車輛最少的道路，用來使客戶規(guī)劃自己的行程.由實(shí)際數(shù)據(jù)抽象成的結(jié)構(gòu)復(fù)雜的大圖數(shù)據(jù)和實(shí)際問題衍生出的圖查詢問題，為圖的可達(dá)性查詢算法帶來了挑戰(zhàn)，也一直是圖論算法中的研究熱點(diǎn).

此外，隨著硬件技術(shù)的發(fā)展，高性能的CPU已經(jīng)降低了由圖大小和其復(fù)雜性導(dǎo)致的計(jì)算時(shí)間消耗，整個(gè)計(jì)算機(jī)行業(yè)正在向并行計(jì)算過渡[1].高度并行的多核系統(tǒng)為新型高效、可擴(kuò)展的圖處理算法提供了機(jī)會(huì).

目前，許多關(guān)于圖數(shù)據(jù)傳統(tǒng)串行可達(dá)性查詢算法的技術(shù)和相關(guān)應(yīng)用被提出[2-6].圖數(shù)據(jù)的可達(dá)性查詢方法有很多種，其核心思想是創(chuàng)建一個(gè)索引結(jié)構(gòu)輔助查詢，從而縮短查詢的時(shí)間，按照類別可以劃分為以下3種[4]：1)基于減枝的深度優(yōu)先搜索法(Pruned Depth-first Search)[7-13]，用減枝法優(yōu)化傳統(tǒng)深度優(yōu)先搜索算法進(jìn)行查詢；2)傳遞閉包法(Transitive Closure Retrieval)[14-18]，計(jì)算所有頂點(diǎn)的傳遞閉包并回答查詢；3)標(biāo)簽匹配法(2-Hop Label Matching)[19-21]，根據(jù)索引結(jié)構(gòu)中的標(biāo)簽信息進(jìn)行查詢.

雖然目前存在著許多對(duì)圖可達(dá)性查詢的高效算法，但是它們也存在各種各樣的問題.對(duì)大圖查詢算法而言，問題的關(guān)鍵是對(duì)空間消耗和時(shí)間消耗的平衡，在預(yù)處理階段進(jìn)行大量的準(zhǔn)備工作，生成龐大的索引會(huì)導(dǎo)致大量的空間消耗，但是這會(huì)為查詢工作帶來極大的便利.上述第二類傳遞閉包法，在預(yù)處理階段將所有頂點(diǎn)的傳遞閉包存儲(chǔ)下來，極大的提高了單次查詢應(yīng)答的效率，但是這造成了大量的空間浪費(fèi).如果生成較為簡(jiǎn)單的索引，雖然會(huì)減少空間消耗，但是在查詢過程中會(huì)產(chǎn)生過多的時(shí)間浪費(fèi).隨著多核服務(wù)器的出現(xiàn)，這些串行的算法無法更好的利用硬件發(fā)展帶來的計(jì)算優(yōu)勢(shì)，造成了極大的資源浪費(fèi).目前，有許多對(duì)并行深度優(yōu)先搜索算法的技術(shù)和研究成果[22-24]，但是這些研究工作只針對(duì)某種算法，單一的追尋算法效率，沒有結(jié)合適當(dāng)?shù)乃饕ソ鉀Q實(shí)際的問題，無法保證算法對(duì)不同索引結(jié)構(gòu)的適用性，即無法解決需要索引的結(jié)構(gòu)復(fù)雜的網(wǎng)圖上的查詢問題.

在圖的可達(dá)性查詢算法中，構(gòu)建一個(gè)能夠平衡空間消耗和查詢效率的索引結(jié)構(gòu)是一個(gè)有挑戰(zhàn)性的問題，且現(xiàn)有工作的索引與算法不適用于并行系統(tǒng)，因此本文提出了一種2-lists索引.該索引由頂點(diǎn)表和邊表組成，頂點(diǎn)表存儲(chǔ)頂點(diǎn)和邊的信息，考慮到線性表線性查找的局限性，加入了邊表進(jìn)行輔助查詢使其做到隨機(jī)訪問的同時(shí)，還可以進(jìn)行反向查詢，占用的內(nèi)存空間和構(gòu)建該索引需要的時(shí)間均是隨圖數(shù)據(jù)規(guī)模的變化而線性變化.基于該種索引提出了一種并行化深度優(yōu)先搜索算法，2-lists-PDFS算法，該算法高效且具有通用性，充分的利用多核服務(wù)器的硬件優(yōu)勢(shì).將雙表索引和并行化算法結(jié)合，提升了針對(duì)復(fù)雜圖數(shù)據(jù)查詢的效率.最后在斯坦福大學(xué)SNAP實(shí)驗(yàn)室收集的真實(shí)公開數(shù)據(jù)集進(jìn)行了大量的實(shí)驗(yàn).

本文第2節(jié)介紹現(xiàn)有圖可達(dá)性查詢算法和并行圖搜索算法的一些相關(guān)工作；第3節(jié)對(duì)2-lists索引結(jié)構(gòu)和2-lists-PDFS算法進(jìn)行詳細(xì)的介紹；第4節(jié)詳細(xì)介紹索引結(jié)構(gòu)與算法實(shí)驗(yàn)的結(jié)果，并進(jìn)行分析；在文章最后，總結(jié)全文，并提出下一步的工作方向.

2 相關(guān)工作

隨著社交網(wǎng)絡(luò)分析、Web語義分析、生物信息網(wǎng)絡(luò)分析以及交通導(dǎo)航等新興應(yīng)用的快速增長(zhǎng)，不同領(lǐng)域出現(xiàn)了規(guī)模龐大、內(nèi)部結(jié)構(gòu)復(fù)雜、查詢需求多樣的大圖數(shù)據(jù)，同時(shí)帶來了許多圖查詢算法的相關(guān)應(yīng)用，如道路網(wǎng)中的路線規(guī)劃[7]、社交網(wǎng)上的好友推薦[8]、時(shí)空軌跡數(shù)據(jù)的可達(dá)區(qū)域預(yù)測(cè)[9]，如何對(duì)這些數(shù)據(jù)進(jìn)行高效且正確的查詢，受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注.

2.1 減枝優(yōu)化法

此分類中的技術(shù)使用圖上的深度優(yōu)先搜索算法(Depth-First-Search，DFS)進(jìn)行每個(gè)可達(dá)性查詢，它們預(yù)先計(jì)算了圖上的某些輔助信息以修剪搜索的空間，從而提高查詢效率.Yildirim等人[10]提出了一個(gè)稱為Grail的簡(jiǎn)單且可擴(kuò)展的索引，該索引基于隨機(jī)間隔的思想，可以有效的處理非常大的圖形，索引構(gòu)建時(shí)間和空間都是線性的，在回答圖查詢問題時(shí)，可以通過頂點(diǎn)的標(biāo)簽，對(duì)不可達(dá)的查詢頂點(diǎn)進(jìn)行快速消除，這也是此類算法中的代表性算法.Zhou等人[11]針對(duì)傳統(tǒng)圖查詢算法無法放大到大圖的問題，提出了一種自下而上的算法buTR，該算法刪除圖數(shù)據(jù)所有冗余邊，以獲得唯一的最小無向圖，從而降低了時(shí)間消耗和空間消耗帶來的成本.Xie等人[12]提出了一種復(fù)合型索引BFSI-B，它使用特殊索引來提升k-hop查詢方法的修剪效率，從而降低可達(dá)性查詢所需的時(shí)間.Du等人[13]提出了一種標(biāo)記方案，有效地構(gòu)建一個(gè)緊湊的索引來捕獲頂點(diǎn)之間最短的距離，從而進(jìn)一步增加頂點(diǎn)標(biāo)簽的覆蓋范圍，使得無需進(jìn)行圖遍歷就可以回答許多查詢.

上述方法在預(yù)處理計(jì)算和空間消耗方面開銷較小，但是相應(yīng)的查詢效率不佳.本文提出的2-lists-PDFS算法可以歸納為此類，2-lists索引結(jié)構(gòu)采用雙鏈表索引結(jié)構(gòu)，占用空間較小，相比于傳統(tǒng)串行算法，使用并行計(jì)算的2-lists-PDFS解決了查詢效率不佳這一問題.

2.2 傳遞閉包法

頂點(diǎn)的傳遞閉包是圖中該頂點(diǎn)可達(dá)頂點(diǎn)的集合.此類算法通過一些手段，來加快計(jì)算傳遞閉包的效率.Schaik等人[16]提出了PWAH方案，使用壓縮位向量來緊湊地表示傳遞閉包，降低存儲(chǔ)傳遞閉包所需的空間.Chen等人[17，18]提出了兩種新的圖分解方法，分別將圖分解成最小的不相交鏈集和一系列可能具有相同邊的生成樹，將圖上的傳遞閉包壓縮到更小結(jié)構(gòu)上的傳遞閉包，以提高查詢效率和降低存儲(chǔ)消耗.

給定一些頂點(diǎn)，上述方法只要查詢指定頂點(diǎn)所存儲(chǔ)的傳遞閉包，即可完成查詢，但是由于派生和存儲(chǔ)傳遞閉包中產(chǎn)生的大量預(yù)計(jì)算和空間開銷，使得它們無法適用于大圖數(shù)據(jù).基于并行計(jì)算的2-lists-PDFS算法要比基于串行深度優(yōu)先搜索算法求解傳遞閉包的算法有更高的查詢效率，從而減少預(yù)計(jì)算開銷.但存儲(chǔ)傳遞閉包帶來的空間消耗仍然沒有得到有效的解決.

2.3 標(biāo)記匹配法

此類算法將某些特定標(biāo)記記錄在索引結(jié)構(gòu)中，通過標(biāo)記信息，來回答圖的可達(dá)性查詢.這類方法以Cohen等人[19]提出的2-hop標(biāo)記為代表，它將每個(gè)頂點(diǎn)所到其它頂點(diǎn)的最短距離或距離總和記錄在索引結(jié)構(gòu)中，并提出了一種有效的算法，用于查找某條指定路徑.Bramandia等人[20]對(duì)2-hop標(biāo)記法進(jìn)行了更新，使得新方法可以適用于由圖數(shù)據(jù)頂點(diǎn)的更新而產(chǎn)生的連通性變化.Jiang等人[21]提出了3-hop標(biāo)記法，首先提取出誘導(dǎo)子圖，基于上限密度啟發(fā)式算法和早停跳選擇策略，以較小的索引大小對(duì)剩余的傳遞信息進(jìn)行編碼，完成標(biāo)記.

此類算法的主體思想是對(duì)頂點(diǎn)標(biāo)簽進(jìn)行并集計(jì)算，當(dāng)標(biāo)簽集較小時(shí)，此類算法有很高的查詢效率.但是當(dāng)標(biāo)簽集較大時(shí)，容易產(chǎn)生冗余的數(shù)據(jù)，從而導(dǎo)致查詢效率降低.2-lists索引結(jié)構(gòu)只存儲(chǔ)邊，不存距離、路徑等附加信息，因此索引結(jié)構(gòu)占用空間小，對(duì)圖進(jìn)行查詢不會(huì)產(chǎn)生冗余操作.

2.4 并行圖查詢算法

目前，有許多并行深度優(yōu)先搜索算法的相關(guān)工作.Acar等人[22]提出了一個(gè)用于表示深度優(yōu)先搜索中頂點(diǎn)邊界的新數(shù)據(jù)結(jié)構(gòu)，每個(gè)線程根據(jù)當(dāng)前數(shù)據(jù)結(jié)構(gòu)是否為空和當(dāng)前線程的工作狀態(tài)利用線程通信技術(shù)來完成負(fù)載平衡，從而實(shí)現(xiàn)深度優(yōu)先搜索算法的并行化.Aleksandrov等人[23]用圖分割技術(shù)，為每個(gè)線程分配不同的圖分區(qū)，在預(yù)處理階段分別計(jì)算距離信息并存儲(chǔ)，根據(jù)這些信息，在查詢階段在不同的線程上完成查詢.Naumov等人[24]提出了一個(gè)基于路徑比較與單源最短路徑(Single Source Shortest Path，SSSP)的技術(shù)，將有向無環(huán)圖壓縮成有向樹，然后對(duì)有向樹使用并行化廣度優(yōu)先搜索，完成查詢.但是這種方法，在GPU上更有效率.

上述方法全部采用鄰接表，但是在實(shí)際應(yīng)用中，往往需要功能性更強(qiáng)的索引結(jié)構(gòu)，因此以上幾種方法的應(yīng)用不能夠擴(kuò)展到可達(dá)性查詢等實(shí)際問題，2-lists-PDFS算法基于2-lists索引結(jié)構(gòu)，可以有效地解決可達(dá)性查詢等實(shí)際問題.同時(shí)上述工作將圖按字典序并行化查詢，但在可達(dá)性查詢、圖查詢等問題中并非關(guān)鍵要素，2-lists-PDFS算法采用無序查詢，從而加快可達(dá)查詢的響應(yīng)速度.

3 基于索引的并行圖查詢算法

為了便于說明問題，現(xiàn)定義如下符號(hào)：V={v1，v2，…，vm-1，vm}，為m個(gè)頂點(diǎn)的集合.E={ev1，v2，ev1，v3，…evm，vm-2，evm，vm-1}，為頂點(diǎn)之間的邊組成的集合，其中evn，vm表示頂點(diǎn)vn有一條指向頂點(diǎn)vm的邊.令G =(V，E)是一個(gè)頂點(diǎn)集為V，邊集為E的有向圖，用|V|來表示頂點(diǎn)集的大小，|E|來表示邊集的大小.NL為索引結(jié)構(gòu)中的頂點(diǎn)表，EL為索引結(jié)構(gòu)中的邊表.AD(v)為邊表中每個(gè)頂點(diǎn)的數(shù)據(jù)塊的地址的集合，共|V|個(gè).P是線程的集合，M是緩沖區(qū)的集合.本文所使用的符號(hào)如表1所示.

定義1.對(duì)于屬于頂點(diǎn)集V的任意兩點(diǎn)vs和vt，如果存在一條定向路徑以vs為起點(diǎn)vt為終點(diǎn)，那么可表示為vs可達(dá)vt(記作vs→vt).給定任意起始頂點(diǎn)vs和終止頂點(diǎn)vt，如果存在vs→vt，則返回True否則將返回False.如圖1所示，存在一條有向路徑使得va可達(dá)ve，記作va→ve.

圖1 有向無環(huán)圖

3.1 雙表索引

索引對(duì)數(shù)據(jù)庫(kù)具有十分重要的意義.如上文所述，在對(duì)大圖數(shù)據(jù)進(jìn)行查詢時(shí)，應(yīng)基于一個(gè)合適的索引，來平衡空間消耗和計(jì)算時(shí)間消耗.傳遞閉包法是將圖內(nèi)所有頂點(diǎn)的傳遞閉包均求解后將其存儲(chǔ)，以便于進(jìn)行查詢?cè)L問時(shí)，能夠有極快的響應(yīng)時(shí)間.但是對(duì)于前文所述的社交網(wǎng)絡(luò)圖而言并不現(xiàn)實(shí)，因?yàn)檫@個(gè)方法造成的空間消耗是巨大的.

以前的工作在建立索引結(jié)構(gòu)后，會(huì)對(duì)圖進(jìn)行預(yù)處理，并將一些輔助信息存放在索引中，但是在建立索引的過程中，會(huì)反復(fù)對(duì)圖進(jìn)行遍歷，在大圖數(shù)據(jù)中，圖的復(fù)雜性隨頂點(diǎn)數(shù)目的增多而增加，這意味著每一次對(duì)圖進(jìn)行遍歷都將造成大量的時(shí)間浪費(fèi)，而且存儲(chǔ)過多輔助信息會(huì)造成極大的空間浪費(fèi).為了解決上述問題，本文提出了一個(gè)新的索引結(jié)構(gòu).

3.1.1 2-lists索引的基本結(jié)構(gòu)

定義2.給定一個(gè)有向圖G=(V，E)，對(duì)于該圖構(gòu)建2-lists索引結(jié)構(gòu)，即頂點(diǎn)表NL和邊表EL，二者均具有指針域，其中NL具有節(jié)點(diǎn)指針域，LN，EL具有正向指針域，Lfor和反向指針域，Lre.任意evi，vj∈E，EL(vj)∈LN(vi)，NL(vi)∈Lfor(vi)，NL(vi)∈Lre(vj).

圖2是根據(jù)圖1部分頂點(diǎn)構(gòu)造的2-lists索引的基本結(jié)構(gòu)，邊表中的vc的反向指針指向頂點(diǎn)表中的a點(diǎn)，因?yàn)閳D1中存在一條邊ea，c，vc的正向指針指向頂點(diǎn)表中的vc的數(shù)據(jù)塊.這樣做的好處是，在進(jìn)行可達(dá)性查詢中的祖先查詢問題時(shí)，遍歷反向指針可直接求得頂點(diǎn)的祖先.

在建立2-lists時(shí)，首先創(chuàng)建邊表EL并將EL中每個(gè)頂點(diǎn)的地址記錄在AD中，以便后續(xù)進(jìn)行隨機(jī)訪問，如步驟3、步驟4.創(chuàng)建頂點(diǎn)表時(shí)，根據(jù)定義2，會(huì)將邊表和頂點(diǎn)表對(duì)應(yīng)的頂點(diǎn)連接起來，如步驟8～步驟11.

構(gòu)建本索引結(jié)構(gòu)的算法如下：

算法1.2-lists索引構(gòu)建算法

輸入：有向圖G=(V，E)，頂點(diǎn)集V的大小|V|.

輸出：2-lists索引表.

1.set AD←{}，NL←{}，EL←{}

2.foreach v in Vdo

3. add v into EL //構(gòu)建邊表

4. add &(EL(v))into AD //將邊表中每個(gè)數(shù)據(jù)塊的地址用頂點(diǎn)為關(guān)鍵字存放

5.endfor

6.foreach evi，vjin Edo

7.ifNL(vi)=0then//如果該頂點(diǎn)尚未被加入到頂點(diǎn)表中

8. add viinto NL //構(gòu)建頂點(diǎn)表

9. NL(vi).Keypointer←AD(vj)//頂點(diǎn)表指針域指向邊表對(duì)應(yīng)數(shù)據(jù)塊

10. EL(vi).Forpointer←NL(vi)//邊表正向指針域指向頂點(diǎn)表對(duì)應(yīng)數(shù)據(jù)塊

11. EL(vj).Reporinter←NL(vi)//邊表反向指針域指向起始頂點(diǎn)數(shù)據(jù)塊

12.endif

13.endfor

根據(jù)算法1和圖2進(jìn)行相關(guān)說明.創(chuàng)建索引時(shí)，首先根據(jù)頂點(diǎn)數(shù)量建立邊表，而后根據(jù)存在的邊ea，c，建立頂點(diǎn)表，將va存入數(shù)據(jù)塊中的數(shù)據(jù)域內(nèi)，使用前面記錄下的邊表中vc數(shù)據(jù)塊的地址ad(c)，將邊表中vc數(shù)據(jù)塊的地址記錄在頂點(diǎn)表va數(shù)據(jù)塊中的指針域中，而后將頂點(diǎn)表中va數(shù)據(jù)塊的地址分別記錄在邊表va數(shù)據(jù)塊的正向指針域和vc數(shù)據(jù)塊的反向指針域中.值得一提的是，算法只給出了插入新頂點(diǎn)的偽代碼，而對(duì)于已存在頂點(diǎn)，通過邊表指針域中存放的地址，可以快速地定位到該頂點(diǎn)所在頂點(diǎn)表中的位置.

在使用2-lists索引進(jìn)行圖的搜索時(shí)，會(huì)先定位到某個(gè)頂點(diǎn)所在的頂點(diǎn)表數(shù)據(jù)塊，然后根據(jù)該數(shù)據(jù)塊指針域所存放的指針列表定位到邊表中的相應(yīng)數(shù)據(jù)塊，再根據(jù)塊中的正向指針，定位到頂點(diǎn)表，進(jìn)行深度優(yōu)先搜索.如果想要查詢某個(gè)頂點(diǎn)的祖先，只需要從它的反向指針出發(fā)，進(jìn)行搜索即可.如圖2，遍歷vc時(shí)，會(huì)先定位到vc所在的數(shù)據(jù)塊，然后根據(jù)vc指針域的指針，分別指向了邊表的ve和vf，再?gòu)乃麄兊闹羔樣虺霭l(fā)，進(jìn)行遍歷，直到遍歷完成.如果想要查詢vc的祖先，只需要先定位到vc，然后遍歷vc反向指針指向的頂點(diǎn)，即可查詢出vc的所有祖先.

圖2 2-lists索引結(jié)構(gòu)圖

3.1.2 2-lists索引大小及創(chuàng)建所需時(shí)間復(fù)雜度

上一節(jié)介紹2-lists索引結(jié)構(gòu)以及構(gòu)建索引的算法，本節(jié)將對(duì)索引的大小以及創(chuàng)建所需的時(shí)間復(fù)雜度進(jìn)行分析.

對(duì)于一個(gè)有向無環(huán)圖G=(V，E)，頂點(diǎn)集大小和邊集大小分別表示為|V|和|E|，設(shè)邊表的指針域大小為l，數(shù)據(jù)域大小為u.在構(gòu)建邊表時(shí)，還創(chuàng)建了存儲(chǔ)邊表中每個(gè)數(shù)據(jù)塊地址的表AD，該表與|V|成正相關(guān)，假設(shè)每個(gè)數(shù)據(jù)塊地址的大小為k，那么邊表占用的總空間為:

S(EL)=(2l+u+k)×|V|

(1)

在創(chuàng)建頂點(diǎn)表時(shí)，頂點(diǎn)表每個(gè)數(shù)據(jù)塊存儲(chǔ)的數(shù)據(jù)域、指針域占用空間均與邊表相同，但頂點(diǎn)表的指針域存放指針的數(shù)量是邊集E的大小|E|，所以頂點(diǎn)表的大小為:

S(NL)=u×|V|+l×|E|

(2)

根據(jù)公式(1)和公式(2)，可以得出，2-lists索引總大小為:

S=(2l+2u+k)×|V|+l×|E|

(3)

根據(jù)公式(3)可以看出，2-lists的總大小隨著|V|和|E|的大小而變化，即圖數(shù)據(jù)頂點(diǎn)的數(shù)量和邊的數(shù)量進(jìn)行線性的變化.

對(duì)于第2步～第5步邊表的建立，由于是順序連續(xù)存儲(chǔ)頂點(diǎn)信息，其所需時(shí)間只與頂點(diǎn)數(shù)有關(guān)，即時(shí)間復(fù)雜度為O(|V|)，對(duì)于第6步到第12步頂點(diǎn)表的建立，它會(huì)將圖數(shù)據(jù)所有邊的信息讀取到內(nèi)存中，逐條存儲(chǔ)在頂點(diǎn)表中，而在確定某一個(gè)頂點(diǎn)對(duì)時(shí)，也可以根據(jù)存儲(chǔ)邊表數(shù)據(jù)塊地址的AD集合來以O(shè)(1)的時(shí)間復(fù)雜度來查詢每個(gè)頂點(diǎn)的位置，所以頂點(diǎn)表的建立所需時(shí)間與邊數(shù)有關(guān)，即O(|E|)，所以2-lists索引結(jié)構(gòu)所需的時(shí)間復(fù)雜度為O(|V|)+O(|E|)=O(|V|+|E|).

3.2 基于2-lists的并行化深度優(yōu)先搜索算法

圖的可達(dá)性查詢可以用深度優(yōu)先搜索算法來回答.并行化深度優(yōu)先搜索算法(Parallel Depth First Search，PDFS)需要執(zhí)行負(fù)載平衡以使所有線程繁忙，最簡(jiǎn)單的辦法就是生成若干個(gè)線程，然后用負(fù)載均衡算法將數(shù)據(jù)分配給每個(gè)線程.

根據(jù)2-lists索引的特點(diǎn)，對(duì)一個(gè)頂點(diǎn)進(jìn)行深度優(yōu)先搜索時(shí)，從頂點(diǎn)表的指針域出發(fā)，對(duì)每個(gè)指針指向的頂點(diǎn)進(jìn)行搜索，本文提出的2-lists-PDFS算法的基本思想在于，將頂點(diǎn)表的指針域中的每個(gè)指針指向的頂點(diǎn)，加載到不同的線程，分別進(jìn)行深度優(yōu)先搜索.負(fù)載平衡方法有很多，如工作竊取算法[25]，但是每個(gè)頂點(diǎn)所帶來的工作量并不相同，產(chǎn)生工作量小的頂點(diǎn)會(huì)頻繁的進(jìn)行負(fù)載平衡，這會(huì)導(dǎo)致帶來的收益會(huì)遠(yuǎn)小于負(fù)載平衡的消耗.因此，我們提出了一個(gè)負(fù)載平衡方法，使每個(gè)線程在工作狀態(tài)和負(fù)載平衡階段相互轉(zhuǎn)化.

定義3.給定任意查詢點(diǎn)vi，每個(gè)線程對(duì)應(yīng)查詢過程如下：

1)對(duì)所有vj滿足evi，vj∈E，vj∈m.

2)對(duì)任意vk∈m，若vk沒有被訪問過，對(duì)所有vq滿足evk，vq∈E，vq∈m，m為根據(jù)負(fù)載平衡指定的線程緩沖區(qū).

3.2.1 并行化深度優(yōu)先搜索算法

算法2. 2-lists-PDFS算法

輸入：頂點(diǎn)集V，線程每次加載數(shù)據(jù)的數(shù)量T.

輸出：遍歷后的visit集合.

1.set visit←{}，K←{}，m←{}，p←{}，pm←{}

2.whiletruedo

3. p←m[1-T]//將緩沖區(qū)中的數(shù)據(jù)加載到線程中

4.foreach v in pdo

5.ifvisit[p.pointer]=falsethen

6. visit[p.pointer]=true

7. pm←p.pointer

8.ifpm.size=Tthen

9. writein(findmin(K)，pm)//將遍歷得到的數(shù)據(jù)寫入指定的線程中

10. K++

11.endif

12.endfor

13.endwhile

算法2表示了參與2-lists-PDFS算法的所有線程都需要執(zhí)行的偽代碼.每個(gè)線程維護(hù)自身的緩沖區(qū)m，從m中加載T個(gè)數(shù)據(jù)，如步驟3.在對(duì)頂點(diǎn)遍歷時(shí)，根據(jù)訪問數(shù)組visit判斷頂點(diǎn)是否被訪問過，未被訪問的頂點(diǎn)使用原子操作將訪問數(shù)組標(biāo)記為已訪問，如步驟5、步驟6，同時(shí)，將該頂點(diǎn)的子頂點(diǎn)加載至線程輔助緩沖區(qū)pm，然后根據(jù)負(fù)載平衡策略，將頂點(diǎn)按規(guī)則加載到緩沖區(qū)中，如步驟7～步驟9.

3.2.2 2-lists-PDFS的緩沖區(qū)

每個(gè)線程創(chuàng)建一個(gè)隊(duì)列做緩沖區(qū)，隊(duì)列的特點(diǎn)是先進(jìn)先出(FIFO)，保證了先進(jìn)入緩沖區(qū)的頂點(diǎn)優(yōu)先進(jìn)行遍歷，防止造成因頂點(diǎn)積壓，部分頂點(diǎn)長(zhǎng)時(shí)間處于未被訪問狀態(tài).為了減少訪問沖突，每個(gè)線程除了進(jìn)行讀寫時(shí)，不會(huì)占用任何緩沖區(qū).在對(duì)當(dāng)前數(shù)據(jù)塊存儲(chǔ)的頂點(diǎn)進(jìn)行遍歷時(shí)，緩沖區(qū)會(huì)存儲(chǔ)該數(shù)據(jù)塊指針域所指向的地址，也就是邊表的數(shù)據(jù)塊的地址，邊表數(shù)據(jù)塊中存儲(chǔ)的數(shù)據(jù)域是當(dāng)前被遍歷頂點(diǎn)的子節(jié)點(diǎn).

當(dāng)線程開始工作時(shí)，會(huì)從緩沖區(qū)中讀取并刪除一些頂點(diǎn)，對(duì)其進(jìn)行訪問.刪除的頂點(diǎn)數(shù)量由T決定，T表示每個(gè)線程每輪應(yīng)遍歷的頂點(diǎn)數(shù)目.T越大，線程每輪讀的數(shù)據(jù)越多，每個(gè)線程每輪做的工作也就越多，從而減緩從緩沖區(qū)讀數(shù)據(jù)的頻率；T越小，每輪線程讀的數(shù)據(jù)越少，每個(gè)線程工作越少，從而加快從緩沖區(qū)讀數(shù)據(jù)的頻率.同時(shí)，T還決定了輔助緩沖區(qū)pm一次性根據(jù)負(fù)載均衡策略向其他線程緩沖區(qū)寫入數(shù)據(jù)的數(shù)量.

在線程工作時(shí)，記錄下每個(gè)線程的工作量，記作K.K值越大，則代表該線程在單次查詢工作中所做的工作越多，在負(fù)載均衡時(shí)，該線程被分配數(shù)據(jù)的優(yōu)先級(jí)更低.K值同時(shí)也是評(píng)價(jià)負(fù)載平衡工作效果的標(biāo)準(zhǔn)，如果所有線程的K值相近，則說明負(fù)載均衡算法的效果良好.如果K值相差懸殊，說明算法負(fù)載均衡并沒有有效的執(zhí)行.值得一提的是，在進(jìn)行圖遍歷的過程中，一定會(huì)遍歷到已經(jīng)遍歷過的頂點(diǎn)，這些頂點(diǎn)作為已經(jīng)實(shí)現(xiàn)的工作，屬于無效工作量，也應(yīng)該計(jì)入K值，從另一角度上看，無效工作相當(dāng)于數(shù)據(jù)塊的指針域內(nèi)沒有指針，只是工作量為1的正常頂點(diǎn).所以，K值與線程每次從緩沖區(qū)讀取的頂點(diǎn)數(shù)量T值成正相關(guān).

3.2.3 2-lists-PDFS的負(fù)載平衡

上文提到，2-lists-PDFS算法是將當(dāng)前訪問節(jié)點(diǎn)的指針域中的指針加載到不同的線程中，在進(jìn)行這個(gè)工作時(shí)，需要按照負(fù)載平衡策略將頂點(diǎn)加載特定的緩沖區(qū)中，平衡每個(gè)線程處理頂點(diǎn)的數(shù)量，使每個(gè)線程都處于工作狀態(tài).每次在將節(jié)點(diǎn)寫入緩沖區(qū)前進(jìn)行掃描，選出工作量最小的線程，即K值最小的線程，后再將節(jié)點(diǎn)加載到對(duì)應(yīng)線程的緩沖區(qū)中.如圖3所示，線程p3正在加載緩沖區(qū)m3的數(shù)據(jù)，而p1此時(shí)要將自己的數(shù)據(jù)寫入到緩沖區(qū)，m2的K值為4，代表了對(duì)應(yīng)線程工作量為4，是3個(gè)線程中工作量最少的線程，所以p1會(huì)將數(shù)據(jù)寫入到m2當(dāng)中.

圖3 負(fù)載平衡示意圖

需要注意的是，為了防止臟數(shù)據(jù)的產(chǎn)生，對(duì)緩沖區(qū)應(yīng)進(jìn)行存儲(chǔ)訪問控制.在將數(shù)據(jù)寫入緩沖區(qū)時(shí)，如果發(fā)現(xiàn)相應(yīng)緩沖區(qū)正處于使用狀態(tài)，可能對(duì)應(yīng)兩種情況：1)有另一個(gè)線程正在向該緩沖區(qū)寫入數(shù)據(jù)；2)有線程正從該緩沖區(qū)加載數(shù)據(jù)，準(zhǔn)備進(jìn)行它的工作.以上兩種情況的發(fā)生會(huì)使準(zhǔn)備進(jìn)行寫操作的線程進(jìn)入等待狀態(tài)，這會(huì)造成該線程無法進(jìn)行數(shù)據(jù)的寫入，造成長(zhǎng)時(shí)間的等待狀態(tài).而為了應(yīng)對(duì)這一種情況，線程應(yīng)將準(zhǔn)備寫入的數(shù)據(jù)寫入到按K值降序排列的另一線程的緩沖區(qū)中.如圖4所示，線程p1正在向緩沖區(qū)m2中寫入數(shù)據(jù)，此時(shí)，線程p3也需要向緩沖區(qū)寫入數(shù)據(jù)，K值最小的是緩沖區(qū)m2，而這時(shí)，m2處于無法訪問狀態(tài)，所以p3需要向k值第2小的m1緩沖區(qū)寫入數(shù)據(jù)，此時(shí)，m1處于可訪問狀態(tài)，數(shù)據(jù)順利寫入.

圖4 訪問控制示意圖

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文提出的索引及相關(guān)算法的有效性與實(shí)用性，采用斯坦福網(wǎng)絡(luò)分析平臺(tái)實(shí)驗(yàn)室SNAP公開的數(shù)據(jù)集進(jìn)行測(cè)試.自2004年起，SNAP實(shí)驗(yàn)室在分析大型社會(huì)網(wǎng)絡(luò)和信息網(wǎng)絡(luò)方面的研究蓬勃發(fā)展，到目前為止，該網(wǎng)站的最大圖是具有2.4億節(jié)點(diǎn)和13億條邊的Microsoft Instant Messenger網(wǎng)絡(luò).本文所使用的是如下5組公開數(shù)據(jù)集，如表2所示.

表2 數(shù)據(jù)集說明

1)CA-GrQc與CA-HepTh.這兩組數(shù)據(jù)集分別為廣義相對(duì)論和量子宇宙學(xué)協(xié)作網(wǎng)和高能物理理論協(xié)作網(wǎng)，取自電子版arXiv.前者有5242個(gè)頂點(diǎn)和28980條邊而后者有9877個(gè)頂點(diǎn)和51971條邊.

2)soc-sign-bitcoinotc.這是在一個(gè)比特幣OTC的平臺(tái)上使用比特幣進(jìn)行交易的人的信任網(wǎng).我們只關(guān)注于交易關(guān)系，對(duì)數(shù)據(jù)進(jìn)行了處理.該圖有5881個(gè)頂點(diǎn)和35592條邊.

3)Brightkite是一個(gè)基于位置的社交網(wǎng)絡(luò)服務(wù)提供商，用戶可以通過簽到共享他們的位置.該數(shù)據(jù)集有58228個(gè)頂點(diǎn)和428156條邊.

4)soc-Epinions1是一般消費(fèi)者的“誰信任誰”的在線社交網(wǎng)絡(luò)，以信任關(guān)系為邊.該數(shù)據(jù)集有75879個(gè)頂點(diǎn)和508837條邊.

實(shí)驗(yàn)在PC機(jī)上進(jìn)行，本次實(shí)驗(yàn)的運(yùn)行環(huán)境為：Windows10(64bit)，Intel Core i7-7700 4核心CPU，16GB RAM，NVIDIA GTX1060 GPU.

4.1.2 對(duì)比方法

基于本文提出的2-lists索引結(jié)構(gòu)及2-lists-PDFS算法，需要對(duì)索引占用內(nèi)存大小和算法查詢時(shí)間進(jìn)行比較.由于現(xiàn)有的工作中沒有專門用來對(duì)可達(dá)性查詢算法并行化的方法，現(xiàn)用以下幾種方法對(duì)比：

1)DFS：傳統(tǒng)的深度優(yōu)先搜索算法.

2)PDFS[22]：一個(gè)基于多核的深度優(yōu)先搜索算法，使用傳統(tǒng)的鄰接表作為索引.

3)GRAIL[26]：一個(gè)基于可擴(kuò)展標(biāo)簽索引的串行可達(dá)性查詢算法.

為了進(jìn)一步驗(yàn)證存儲(chǔ)效率和預(yù)處理效率的提升，將對(duì)DFS、Grail和2-lists 3種索引結(jié)構(gòu)的構(gòu)造時(shí)間和所耗內(nèi)存大小作比較；為了驗(yàn)證可達(dá)性查詢的效率，對(duì)DFS、PDFS、Grail和基于2-lists-PDFS分別計(jì)算一個(gè)頂點(diǎn)的可達(dá)頂點(diǎn)，和兩個(gè)頂點(diǎn)的共同可達(dá)頂點(diǎn)，將查詢效率進(jìn)行比較；最后，對(duì)4種算法的總計(jì)時(shí)間進(jìn)行比較.

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

本小節(jié)將對(duì)上一小節(jié)提出的幾種比較方法的結(jié)果進(jìn)行闡述.首先是DFS、Grail和2-lists這3種算法構(gòu)建索引結(jié)構(gòu)所耗時(shí)間的對(duì)比.

表3為3種方法構(gòu)建索引需要的時(shí)間的對(duì)比，PDFS算法和DFS算法用的均是鄰接表，在此表中只對(duì)后者進(jìn)行列舉.可以看到，本文提出的2-lists索引的構(gòu)建的時(shí)間消耗最小，因?yàn)樵跇?gòu)建2-lists索引時(shí)，通過邊表可以用時(shí)間復(fù)雜度O(1)的隨機(jī)訪問來查找到對(duì)應(yīng)的頂點(diǎn)，構(gòu)建索引的時(shí)間復(fù)雜度為O(|V|+|E|)，而構(gòu)建鄰接表時(shí)，每次都需要查找頂點(diǎn)所在的位置，構(gòu)建索引的時(shí)間復(fù)雜度為O(|V|×|E|)，而在Grail算法中，計(jì)算強(qiáng)連通分量和標(biāo)簽集為構(gòu)建索引帶來了不少的時(shí)間消耗.

表3 不同數(shù)據(jù)集上3種方法的構(gòu)建索引的時(shí)間(s)

如表4所示，由3種算法根據(jù)不同種類的輸入圖所構(gòu)建的索引結(jié)構(gòu)所占內(nèi)存大小不同，本文提出的2-lists索引結(jié)構(gòu)空間消耗小于Grail但是卻高于傳統(tǒng)的鄰接表.如公式(3)所示，2-lists所占內(nèi)存空間大小根據(jù)圖頂點(diǎn)和邊的數(shù)量呈線性變化，而Grail算法需要計(jì)算圖中的強(qiáng)連通分量進(jìn)行圖壓縮后，再生成相應(yīng)的標(biāo)簽，但壓縮圖只對(duì)圖進(jìn)行搜索時(shí)起到減枝的作用，實(shí)際上并沒有將圖的規(guī)模變小，所以生成的標(biāo)簽集會(huì)直接導(dǎo)致索引空間消耗增加.傳統(tǒng)鄰接表由于其只存儲(chǔ)了最基本的邊和頂點(diǎn)的相關(guān)信息，所以在空間消耗方面有著較大的優(yōu)勢(shì).

表4 不同數(shù)據(jù)集上3種索引所占內(nèi)存大小(KB)

圖5為4種方法在5種數(shù)據(jù)集上查詢效率的比較.如圖5(a)所示，為對(duì)某一個(gè)頂點(diǎn)的所有可達(dá)頂點(diǎn)的查詢，本文提出的并行化深度優(yōu)先搜索算法的效率最高，其中，傳統(tǒng)的深度優(yōu)先搜索算法效率最低，本文提出的算法要高出其35%至70%的效率.相較于Grail算法，本文提出的算法要高出13%到43%的效率.相較于PDFS算法，本文提出的算法要高出11%到21%的效率.如圖5(b)所示，為對(duì)兩個(gè)頂點(diǎn)的共同可達(dá)頂點(diǎn)的查詢，每組數(shù)據(jù)集都任意選出兩個(gè)頂點(diǎn)，首先確保它們之間存在共同可達(dá)頂點(diǎn)，再進(jìn)行查詢.從圖中看出，與單個(gè)頂點(diǎn)可達(dá)頂點(diǎn)查詢相同，2-lists-PDFS算法的效率優(yōu)于其他3種算法.

圖5 不同數(shù)據(jù)集上4種方法的查詢時(shí)間

表5和表6為5組數(shù)據(jù)集上4種方法測(cè)試的總耗時(shí)，包括構(gòu)建索引的時(shí)間和查詢的時(shí)間.可以看出，PDFS算法由于在構(gòu)建索引效率過低，導(dǎo)致其總時(shí)間與傳統(tǒng)DFS算法差距并不明顯.而Grail算法和2-lists-PDFS算法的效率因?yàn)檫x擇適當(dāng)?shù)乃饕龥]受太大影響.上述所有實(shí)驗(yàn)可以得出，我們的算法在存儲(chǔ)開銷和查詢時(shí)間方面優(yōu)于其他幾種方法.

表5 不同數(shù)據(jù)集上4種方法的可達(dá)頂點(diǎn)查詢總時(shí)間(s)

表6 不同數(shù)據(jù)集上4種方法的共同可達(dá)頂點(diǎn)查詢總時(shí)間(s)

5 結(jié)束語

通過表5和表6可以得知，在對(duì)圖數(shù)據(jù)進(jìn)行研究時(shí)，構(gòu)建一個(gè)合適的索引，與研究算法一樣重要，平衡空間消耗與算法的時(shí)間消耗，依然是對(duì)圖查詢算法研究的重點(diǎn).針對(duì)已有的圖查詢算法其索引結(jié)構(gòu)過于復(fù)雜，傳統(tǒng)串行算法不能適用于多核處理器的問題，本文提出了基于2-lists索引的并行化圖查詢算法，并在5組真實(shí)的數(shù)據(jù)集上進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，本文的工作比其他算法的表現(xiàn)更好.但本文仍有不足，對(duì)社交網(wǎng)等數(shù)據(jù)在實(shí)際應(yīng)用場(chǎng)景的實(shí)時(shí)變化并未過多考慮，在未來的工作中將重點(diǎn)關(guān)注增量或減量帶來的圖查詢問題.