◆宋亞青

（河北工業(yè)大學(xué)計算機科學(xué)與軟件學(xué)院 天津 300401）

基于大規(guī)模圖數(shù)據(jù)k步可達(dá)性索引技術(shù)研究現(xiàn)狀

◆宋亞青

（河北工業(yè)大學(xué)計算機科學(xué)與軟件學(xué)院 天津 300401）

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

圖數(shù)據(jù); k步可達(dá)性查詢; 索引

0 前言

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

1 索引介紹

現(xiàn)階段k步可達(dá)性查詢研究中的查詢方法主要包括：基于圖遍歷的查詢方法、基于區(qū)間標(biāo)簽的查詢方法、基于最短路徑的查詢方法、基于k步索引的查詢方法、基于雙向搜索的查詢方法。其中第一類方法不需要構(gòu)建索引來實現(xiàn)，后四種算法是基于構(gòu)建的索引實現(xiàn)的。

1.1 基于圖遍歷的查詢方法

圖的遍歷指的是從圖中某一頂點出發(fā)訪問遍圖中其余所有頂點，且使每一個頂點僅被訪問一次，通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索?；谶@兩種遍歷方式，可以解決k步可達(dá)性查詢問題。

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

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

1.2 基于區(qū)間標(biāo)簽的查詢方法

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

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

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

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

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

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

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

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

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

2 結(jié)束語

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

[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.