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

◆宋亞青

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

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

◆宋亞青

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

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

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

0 前言

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

1 索引介紹

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

1.1 基于圖遍歷的查詢方法

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

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

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

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

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

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

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

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

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

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

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

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

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

2 結(jié)束語

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