大圖上跳數受限的可達查詢算法研究與優化①

邢耕源,徐 云

1（中國科學技術大學 大數據學院,合肥 230026）

2（安徽省高性能計算重點實驗室,合肥 230026）

圖網絡能夠有效表達不同類型事物之間復雜的關系,在現實生活不同領域中有著廣泛的應用[1].隨著信息技術的不斷發展和互聯網不斷滲入生活,各類圖數據規模發生爆炸式增長,以社交網絡為例,2011年微信月活躍用戶數有0.5億人,而2019年微信月活躍用戶數達到了11億,是中國用戶量最大的APP.面對如此大規模的數據量,傳統的圖搜索方案已經無法勝任.

圖可達查詢是圖數據管理領域的研究熱點問題,然而在現實生活中還需要對可達頂點間的距離加以限制[2].例如在社交網絡中,根據小世界理論[3],任意兩個人之間總存在著6跳的通路,單純的可達性查詢失去了意義.用戶節點間的距離反映著用戶之間聯系的緊密程度,限定距離下的可達性查詢可以幫助分析用戶社區間的關系或搜索與自身相近的其他用戶[4]; 在數據中心網絡中,設計部署整體網絡結構時,網絡圖中服務器間的距離信息反映著信息傳遞的時效性[5].對于限定距離下的可達性查詢,在學術界被稱為k跳可達問題[6].

大圖上各類算法,都會通過構建索引信息,幫助在查詢時快速求解.大圖索引的建立和利用索引的查詢策略,是算法設計的關鍵.索引的構建是為了根據圖局部結構歸納信息,進行狀態壓縮; 查詢策略需要在快速求解的同時保證問題的完備性,大圖上現有的查詢算法,都需要對時間效率和空間效率進行平衡[7].現有的2-hop類算法通過構建由中介頂點構成的2-hop類索引,加速搜索.該算法查詢時間雖然迅速,但是受限于存儲空間,不適合更大規模的圖上運算.

為此本文提出了一種基于部分索引與局部搜索結合的跳數受限可達查詢算法.通過改變原索引結構,提高索引利用率,從而在減少空間占用同時保持查詢時間盡量低.本方法首先構建了基礎的2-hop可達索引;然后采用了近鄰節點和大度數熱點頂點對索引進行約簡; 最后采用索引表和局部搜索結合的方法進行可達性查詢,能夠節省更多的索引空間,從而適用于解決更大規模的圖可達查詢問題.

1 已有大圖查詢類算法分析

目前,已有的圖查詢算法包括一般可達性查詢、最短路徑查詢、k跳可達性查詢等.

1.1 一般可達性查詢算法

大圖上的可達性查詢算法可以根據索引完整的程度和對在線搜索的依賴性,分為傳遞閉包類[8]、hop索引類[9]、索引+類算法[10].

（1）傳遞閉包類算法

該類算法利用設計的索引結構對大圖可達性信息進行預計錄,利用自身設計的各類索引結構能夠快速查找頂點間的可達性關系.在索引設計上,這類算法利用了圖上局部結構（如樹[11]、鏈[12]）的拓撲性進行剪枝并記錄,這一類算法在響應時間上是最快的,如圖1所示.但是其自身的索引結構會隨著圖規模的增大而快速增大,因此存儲空間是這類問題的桎梏.隨著圖規模達到百萬甚至千萬頂點級別,這類算法已經不能完成求解.

圖1 簡單圖網絡

（2）hop索引類算法

該類算法利用一些選定的中繼節點作為中介,進而考慮目標頂點與中繼頂點間的可達性.隨著研究的不斷深入,該類算法利用的中繼結構不再限于單頂點,開始利用鏈路、樹等圖結構作為中間結構; 演化出了2-hop[13]類,演化成3-hop[14]、path-hop[15]類算法,如圖2所示,為簡單圖網絡對應的2-hop索引.

圖2 2-hop索引結構

這一類算法在回答可達性查詢時,只需要在對應行索引上進行搜索,尋找公共中介頂點的表項.該類方法的關鍵是hop索引的建立,即選取合適的中介結構輔助索引建立.

（3）索引+類算法

該類算法發現在實際搜索中,有向圖點對間的不可達查詢占了絕大多數[16]; 相比于發現可達性,他們更期望快速發現點對間的不可達關系,因此他們利用自身索引對可達性進行快速篩選.

如果憑借索引不足以證明點對間的不可達關系,這類算法利用在線搜索用于判定頂點間的可達性.這類算法的空間占用是最小的,但相應其查詢時間最長.

1.2 路徑查詢算法

路徑查詢算法按照索引規模、索引種類可以分為在線搜索[17]、地標算法[18]、樹分解算法[19]等.

（1）在線搜索算法

在線搜索算法不利用索引信息,在圖上直接搜索兩點之間的路徑信息,在線搜索包括經典的Dijkstra算法和Floyd-Warshall算法等.在后續發展中有了A*算法、蟻群算法等改進的算法,該類算法在圖頂點規模達到百萬及以上時,即使在并行下,算法時間效率仍舊較為低下.

（2）地標算法

地標搜索是搜索最短路徑的一類近似算法.這類算法事先選定一些地標點,以地標點作為中介,依次計算所有經過地標下的最短路徑信息; 將其中最短的路徑作為備選路徑[20].這類算法的效果取決于最短路徑是否經過一個真實的地標點,因此合適的地標點選取策略是這類算法的關鍵.目前常見的地標選取策略通常是基于平均頂點度數和中心距離的啟發式算法.

樹分解類算法構建了一棵新的索引樹[21],利用構建的索引樹,樹分解算法可以按級對小規模節點團進行搜索,最終構建出最短路徑.該類算法將原圖中的一團臨近節點縮為索引樹中的一個節點,真實圖中的一條路徑對應團內路徑和團間路徑,利用搜索節點對的最小共同祖先和局部最短路徑搜索算法可以分別解決兩個子問題,該類策略的關鍵是在樹高和團內節點數間平衡,并構建出一棵合適的搜索樹.

1.3 k跳可達性查詢

關于k跳可達算法,學術界已有算法相對較少,已有的k跳可達算法大多是有向圖上算法.基于頂點覆蓋集的k跳可達查詢算法通過求解原圖上的一個頂點覆蓋集,然后在頂點覆蓋集之上根據頂點之間的距離關系構建關系閉包作為圖索引,在查詢時可以通過查詢頂點所在閉包索引,直接得到頂點間k跳可達關系.但是這個方法的空間復雜度較高,因為頂點覆蓋集中的頂點之間的關系越稠密,帶來的索引開銷越大,k-reach 的索引空間和索引時間都隨著圖規模的增長呈指數上漲.

為了改善k跳可達性的擴展性問題,Cheng等給出了一種基于控制集的索引方法[22],并且將索引組織成兩級索引的結構,一定程度上提高了算法的擴展性,但在擴展性得到了提高的同時,卻犧牲了查詢的時間效率.

近年國內也有k跳可達查詢相關研究,基于雙向搜索的k跳查詢算法通過優化雙向搜索過程提高了k跳可達性查詢的時間效率[23].基于圖壓縮的 k跳可達性查詢方法[24],通過對原圖進行等價類的壓縮來降低圖的規模,提高算法的可拓展性.基于BFS樹的k跳查詢算法通過計算索引交集的計算方法,提高了算法的時間效率.

2 基于hop索引的k跳可達算法

k跳可達性查詢相較于一般的可達性查詢約束更為嚴格,因為一般可達性查詢可以視為k=∞下的情況;k跳可達相較于最短路徑查詢約束較為寬松,因為k跳可達在求解到一條跳數不大于k的路徑后,不關心點對間的最短路徑.

我們解決索引空間和查詢時間之間平衡的主要方法是:首先對于原索引中不常被利用缺占據大量空間的小度數頂點索引項,按一定比率選取其中部分進行“約簡”操作.“約簡”操作指:保留其近鄰頂點索引和經過的大度數頂點索引,剔除其他索引項.對于優化后的索引表無法確定的查詢,轉用使用與索引表相結合使用LRU策略的局部搜索進行補充搜索.

為了求解k跳可達問題并優化原索引結構,設計了算法1.

2.1 圖索引的建立

為了求解距離限制的可達查詢問題,選用帶有距離信息的2-hop類索引,2-hop類索引維護著所有頂點對應的2-hop表.當兩個不同的頂點存在著一個公共的中介節點時,說明兩者可達.此時查詢兩者對應的距離標簽,如果所有距離標簽中最小的在限制范圍內,則說明這兩個頂點是在限制范圍內可達的.

構建完整表的方法,依賴于頂點對間的距離信息.算法最開始將每個頂點距自身距離為0的頂點加入自己對應的表單中（自身）; 然后檢索所有的邊,構建距離為1的項,按照優先度,將每條邊加入優先度較高的頂點表單中,然后依照距離信息,遞歸的依次構建基于距離的索引,直到構建到距離為k的索引.

2.2 索引結構的約簡

2-hop類索引構建時,表單中索引項的選取都是單條最短路徑上優先度最高的頂點; 因此大度數頂點的索引項會較短,而小度數頂點的完整索引項會較繁瑣.回答完整性的可達性查詢,因保存這些邊緣頂點全部的信息犧牲掉了很大的存儲空間; 而真正查詢時針對這些邊緣頂點的查詢頻度也較低.這也造成了因存儲不能被及時利用的信息所造成的存儲空間浪費,此需要調整存儲空間和查詢時間之間的平衡.

為了彌補保留部分索引造成的信息丟失,在查詢時需要進行局部搜索,檢測限制距離內兩個目標頂點之間的可達性關系,在社交圖中,除了邊緣頂點臨近的頂點外,利用其他高度數的頂點作為索引可以加速搜索.針對小度數邊緣頂點采用保留近鄰節點信息以及高度數代表頂點作為索引的策略,因社交圖上的頂點傾向于發現與自身相近的頂點或與熱點頂點間關系,所以保留兩種不同類型的頂點作為部分索引,使其加速整體索引搜索過程.

2.3 基于約簡后索引表的查詢算法

2.3.1 可達性查詢算法

針對社交圖上2-hop索引信息不平衡的情況,本文通過保留近鄰節點和大度數代表頂點的手段約簡了索引結構,整體查詢流程如圖3所示.

圖3 可達查詢算法流程圖

在查詢點對間可達性時,首先在約簡后的部分索引上進行查詢,若查詢頂點并非小度數頂點,則其對應的表項是完整的,基于索引表的可達性查詢結果是完備的.若待查詢的頂點是小度數頂點,則優先在其約簡后的部分索引上進行2-hop索引查詢; 若經過查詢后存在著k跳關系,則可以直接回答可達性,若未搜索到k跳可達關系,則需在LRU索引上查詢已有的可達性索引,查看是否近期已經補全過對應行索引.

若LRU索引上仍未有對應的結果,則需在索引表上進行對應行的局部搜索; 并將補全后的行索引存入LRU索引,并將LRU索引進行更新,在原索引表上的局部搜索過程與建立2-hop索引時的檢索過程一致,依據距離信息從小到大依次檢查約簡的小度數頂點不同跳數下的2-hop關系,將其依次補全.

2.3.2 基于約簡后索引表的查詢算法優劣勢分析

使用約簡的2-hop索引可以有效地減小索引空間,并保持可達性查詢時間與完備索引上的查詢時間在同一數量級下,保持時間性能并優化空間性能的關鍵在于代表索引,即近鄰頂點和高度數頂點的選取.但本文的約簡方法對原圖類型有較強要求,對于非社交圖處理效果較差,因其不再具有選取近鄰頂點和高度數頂點作為代表點的特征,同時對于待查詢點對也有一定要求,對于完全隨機的點對間查詢效果也不明顯.

3 實驗結果與分析

實驗分別測定了不同約簡比率下、不同局部搜索方法、不同跳數下索引空間與查詢時間之間的關系.

3.1 數據集介紹與實驗配置

本文選用的數據集來自斯坦福網絡分析項目提供的開源數據集,YouTube[25]和Orkut數據集均為社交網絡數據集.其中YouTube數據集規模較小,該數據集頂點數為1134 890個,邊數為2987 624條; Orkut數據集規模較大,該數據集頂點數為3072 441個,邊數為117 185 083條,所有的實驗都在單機Ubuntu 18.04.5 LTS環境下運行.內存為512 GB,實驗環境的線程數最高為56個.

3.2 評估標準與結果分析

由于本文提出的基于方法是基于hop類算法的k跳可達查詢算法,主要貢獻在于優化hop類索引結構,能夠勝任規模更大的圖上快速查詢的任務.因此在實驗評估標準的選擇上,本文主要選擇索引空間、查詢時間兩個評估標準.同時在對比方法選取上,本文選擇了2019年SIGMOD會議上提出的PSL索引算法[26],該算法已是最先進的hop類算法.

整體實驗方法分為兩部分:確定局部搜索策略和選用某一實驗參數.其中,不同局部搜索算法實驗部分用于確定局部搜索算法,優化比率實驗部分用于確定實驗的一個可變參數:低度數頂點索引優化比率.索引優化實驗部分用于測定在選用參數下索引空間和查詢時間之間的關系.

3.2.1 不同局部搜索算法實驗

本文設計了多種不同的局部搜索算法,實驗表中展示的是優化后的基于啟發式搜索的雙向局部搜索與基于索引表的搜索方法間對比,本實驗數據集采用YouTube數據集,對比了不同跳數（k）下兩種采納不同局部搜索算法與原算法（PSL）間索引空間和查詢時間的關系.

圖4和圖5中PSL算法為對比算法,PSL_pru為雙向啟發式搜索算法,PSL*算法為索引表局部搜索算法.實驗具體數據見表1,表2.由圖可見,兩種改進的索引優化算法均在索引空間上效率超過了原算法,而在查詢時間上高于原算法.其中基于索引的局部搜索算法,由于采用了LRU機制,因此其索引空間略高于雙向搜索查詢算法; 但其對應的查詢時間則大大減少,與未經優化的PSL算法更為相近.保證了查詢時間在同一數量級下,同時索引空間得到了優化.

表1 不同跳數下搜索策略的索引空間和跳數間關系（B）

表2 不同跳數下搜索策略的查詢時間和跳數間關系（ms）

圖4 不同搜索算法空間性能比較

圖5 不同搜索算法時間性能比較

3.2.2 優化比率實驗

在確定了局部搜索算法的種類后,為了得到更好的空間優化效果,同時保證時間性能在同一數量級下我們測試了不同優化比率下查詢時間和索引空間的關系.優化比率作為平衡索引時的一個重要參數,影響的是約簡小度數頂點的比例,優化比率越低,被選中修改的小度數頂點項越少,實驗測試數據集為YouTube數據集,測試了不同跳數下,不同優化比率下的索引空間和查詢時間.

此處的優化比率作為實驗的一個參數,可以根據實際需求人工配置.該比率越高保留的頂點數目越少,算法空間優化比率越高; 比率越低,保留的原索引項越多,算法查詢時間消耗越低.本實驗為了突出空間優化效果,選用了查詢時間不發生顯著改變下的并有著較優空間優化效果的比率進行測定.實際應用時,可以根據需求選取適當的參數配置.

由表3可見,30%至70%的比率下,索引空間減小的速度較為均勻,但查詢時間方面,50%至60%的優化比率出現了較為明顯的查詢時間上升.60%至70%的優化比率下出現了更為劇烈的時間上升,因此考慮到使查詢時間保持在原數量級,本文后續實驗選用50%下的約簡比率進行實驗.

表3 不同優化比率下查詢時間與索引空間關系

3.2.3 索引優化實驗

確定了局部搜索算法和優化比率后,我們在規模更大的社交網絡數據集下進行了與原算法相比較新的對比實驗,實驗的性能評估指標,我們仍舊選定為索引空間和查詢時間.測定了不同跳數變化下,我們的算法與原算法相比性能的優劣,

通過實驗結果,由圖6和圖7可見,從跳數為4開始,本文的算法空間性能開始逐步優化,同時保證了時間效率上略高于原算法.具體實驗數據見表4,表5.其中索引空間可以優化為原算法的68.18%,同時保證查詢時間為原算法1.38倍,保證了時間性能在原算法同一數量級下.

圖6 索引優化前后空間性能比較

圖7 索引優化前后時間性能比較

表4 索引優化前后空間性能比較（B）

表5 索引優化前后時間性能比較（ms）

該實驗結果中,可見空間性能隨跳數k有明顯的變化,但查詢時間上出現了PSL*整體查詢時間先上升后下降的現象.引發這樣的現象的原因是:當限制的跳數k較小時,頂點間的k跳關系較難達成,因此需要借助除原索引外的局部搜索進行測定; 而當跳數k上升至一定程度后,頂點間的k跳約束得到了松弛,此時僅憑借索引表可以得到肯定結果的頂點對比率得到了上升.得到肯定查詢后的頂點對不再需要借助局部搜索進一步查詢,因此算法的查詢時間得到了下降.

4 結論與展望

本文針對2-hop類索引在k跳可達問題上出現的因索引分布不均勻造成的空間浪費的現象,提出了人工可控的平衡索引空間與查詢時間的優化算法.該算法首先構筑一般的2-hop類索引表,再根據約簡比率對原索引表進行平衡處理,并記錄下被處理過的小度數頂點標號.同時,我們設計了與約簡算法相應的查詢算法,保證查詢的完備性,同時利用LRU機制加速查詢階段.在查詢可達性關系時,首先在約簡后的索引表上進行查找,若查詢不到對應頂點信息,則轉入LRU索引上查詢,若仍得不到肯定結果,再轉入局部搜索,并將結果更新至LRU索引上.

實驗表明,我們的方法相比于已有的最先進的索引方法,能夠有效地減小索引占用的空間,同時保證查詢時間增加的幅度可控.下一步的工作重點,是設計針對不同圖類型和圖半徑等信息的參數自動優化算法,增強算法對不同類型的圖網絡的適應性,同時設計新的機制,在優化查詢時間上得到進一步的發展.