基于大規模圖數據k步可達性索引技術研究現狀

◆宋亞青

（河北工業大學計算機科學與軟件學院 天津 300401）

基于大規模圖數據k步可達性索引技術研究現狀

◆宋亞青

（河北工業大學計算機科學與軟件學院 天津 300401）

隨著大數據時代的來臨，數據規模呈指數級速度增長，越來越多的復雜結構數據需要用圖數據結構模型來表示。如何高效而快速地檢索大圖數據成為研究的熱點。現階段，大部分k步可達性查詢都是通過構建索引來實現的。研究發現，構建索引的時間、空間消耗和查詢時間之間存在瓶頸，如何合理地構建索引成為研究的熱點問題。

圖數據; k步可達性查詢; 索引

0 前言

隨著互聯網技術的高速發展，大量數據每天不斷涌現，“大數據”這個名詞已經逐步融入我們的日常生活，伴隨著海量數據出現的是數據結構的多樣化。圖[1]做為一種特殊的數據結構，在處理大規模數據的時候有著廣泛的應用。由于往日研究的可達性查詢存在著很大的局限性，因此能夠為用戶提供更多信息的k步可達性查詢將成為研究的重點和難點問題[2]。在許多實際問題中，k步可達性查詢具有更加重要的研究意義[3]。所有的查詢都是通過構建索引來實現的。研究發現，構建索引的時間、空間消耗和查詢時間之間存在瓶頸。但是隨著科學技術的進步，計算機的配置變得越來越高，存儲容量也變得越來越大，空間消耗不再是制約算法查詢效率的首要考慮因素，因此本著空間換取時間的原則，通過創建索引可以有效地提高算法的查詢效率，下面主要介紹了5類基于不同索引的查詢算法。

1 索引介紹

現階段k步可達性查詢研究中的查詢方法主要包括：基于圖遍歷的查詢方法、基于區間標簽的查詢方法、基于最短路徑的查詢方法、基于k步索引的查詢方法、基于雙向搜索的查詢方法。其中第一類方法不需要構建索引來實現，后四種算法是基于構建的索引實現的。

1.1 基于圖遍歷的查詢方法

圖的遍歷指的是從圖中某一頂點出發訪問遍圖中其余所有頂點，且使每一個頂點僅被訪問一次，通常有兩條遍歷圖的路徑：深度優先搜索和廣度優先搜索。基于這兩種遍歷方式，可以解決k步可達性查詢問題。

深度優先搜索算法的核心思想是：判斷頂點u到頂點v是否k步可達，從u出發，訪問u的任意一個未被訪問過的鄰接點v0，即判斷頂點v0是否k-1步可達頂點v，此時需要遍歷v0的任意一個未被訪問過的鄰接點，依次類推，直至走完k步為止，若一直沒有判斷出結果，則回溯到上一個訪問過的頂點，對該頂點未訪問過的其他鄰接點繼續進行遍歷，直至遍歷完所有鄰接點為止。若中途，判斷出頂點u是k步可達頂點v的，則直接返回; 否則要遍歷與頂點u相連接長度為k的所有路徑。

廣度優先搜索算法的核心思想是：判斷頂點u到頂點v是否k步可達，需要訪問和頂點u相連接的所有鄰接點qi，然后從這些鄰接點qi出發，依次判斷qi是否k-1步可達頂點v，重復上述操作，直至遍歷完所有鄰接點。若中途，判斷出頂點u是k步可達頂點v的，則直接返回; 否則需要遍歷完與頂點u相連接的長度為k的所有路徑。

1.2 基于區間標簽的查詢方法

該類查詢算法主要包括GRAIL、GRIPP和PathTree，典型算法是2010年Jin等人提出的GRAIL索引方法，該方法的基本思想是:為了降低判斷過程中的誤判率，該算法按照從左到右和從右到左兩種不同的深度優先遍歷方式為每個頂點w構建雙區間標簽，記為Lw1和Lw2。給定有向無環圖G，判斷u→kv是否成立，只有滿足條件時，則得出結論頂點u不可達頂點v，對于所有沒有通過區間標簽判斷出可達性的頂點需要通過遞歸判斷u的孩子頂點是否（k-1）步可達頂點v。

該算法的缺點是大量的遞歸操作帶來的時間開銷和空間開銷會嚴重影響系統的查詢效率。

1.3 基于最短路徑的查詢方法

該類方法的算法主要有PLL、TEDI和IS-LABEL，而典型的算法是Akiba等人提出的PLL算法，這個算法需要為每個頂點構建兩個區間標簽分別記為Lin（u）和Lout（u），判斷w→ku是否成立，首先需要得到頂點w的出度標簽Lout（w）和頂點u的入度標簽Lin（u）標簽，然后將Lout（w）與Lin（u）兩個標簽取交集，將取交運算的結果相加得到從頂點w到頂點u的路徑值，最后從這些路徑值中取最小值作為兩頂點之間的最短路徑值d。如果d≤k，則說明頂點w在k 步之內到達頂點u; 否則不可達。該方法的缺點是兩頂點對不可達時，求解代價比較高，嚴重影響系統的查詢性能。

1.4 基于k步索引的查詢方法

該方法是Cheng等人首次提出專門用于解決k步可達性查詢問題的，基本思想是:求出給定圖的一個頂點覆蓋集，根據覆蓋集來建立k步索引，基于建立的索引實現k步可達性查詢。

k步可達性查詢處理的核心思想:假設判斷頂點u到頂點v是否k步可達，可以分為以下三種情況:（1）要查詢的兩個頂點u和v都是最小頂點覆蓋集S中的頂點，則需要判斷在覆蓋集中，兩頂點之間是否存在邊連接; （2）起始頂點u和終止頂點v只有一個在頂點在覆蓋集中，假設頂點u（或v）在覆蓋集中，則要求出頂點v的入度頂點集（或u的出度頂點集），之后判斷在頂點覆蓋集S中，頂點u（或v）和頂點v的入度頂點集（或是頂點u的出度頂點集）中是否存在路徑長度d≤ k-1，若存在，則頂點u到頂點v是k步可達的，否則k步不可達; （3）兩頂點都不在頂點覆蓋集S中。計算出頂點u的出度頂點集中到頂點v的入度頂點集中是否存在路徑長度d≤ k-2。若存在，則u→kv成立，否則不成立，該方法的缺點在于:只適合小規模的圖數據。

1.5 基于雙向搜索的查詢方法

2015年，周等人在GRAIL算法的基礎上提出了BiRch算法，該算法的核心思想是:判斷兩頂點是否k步可達時，首先根據GRAIL算法中的雙區間標簽，快速判斷出不可達頂點對，然后比較起始頂點u的出度和目標頂點v的入度，始終從度小的一方開始查詢，周等人在BiRch算法的基礎上進一步提出了BiRch-BTL算法，BiRch-BTL算法的特點是通過四種剪枝策略過濾掉部分不可達頂點對，提高了算法的查詢效率，但這兩種算法存在問題是:無法記錄已查詢過的不可達頂點對，出現大量冗余頂點對的重復判斷現象，因此嚴重影響系統的查詢性能。

2 結束語

伴隨著海量數據出現的是數據結構的多樣化，如何在種類繁多的數據中獲得有用信息是急需解決的問題。盡管目前針對大規模圖數據提出了一些有效的索引方法，但在實際應用中仍存在許多亟待解決的問題，本文討論了k步可達性索引技術的應用前景，對研究者改進k步可達性查詢算法有著重要的意義。

[1]Fan Wen-fei，Wang Xin，Wu Ying-hui.Querying big graphs within bounded resources[C].In:Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.Utah，USA，2014.

[2]Cheng J，Shang Z，Cheng H.Efficient processing of k-hop reachability queries.VLDB Journal，2014.

[3]Hua Wen，Zheng Kai，Zhou Xiao-feng.Microblog entity linking with social temporal context[C].In:Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data.Melbourne，Australia，2015.