邢耕源,徐 云

1（中國(guó)科學(xué)技術(shù)大學(xué) 大數(shù)據(jù)學(xué)院,合肥 230026）

2（安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室,合肥 230026）

圖網(wǎng)絡(luò)能夠有效表達(dá)不同類型事物之間復(fù)雜的關(guān)系,在現(xiàn)實(shí)生活不同領(lǐng)域中有著廣泛的應(yīng)用[1].隨著信息技術(shù)的不斷發(fā)展和互聯(lián)網(wǎng)不斷滲入生活,各類圖數(shù)據(jù)規(guī)模發(fā)生爆炸式增長(zhǎng),以社交網(wǎng)絡(luò)為例,2011年微信月活躍用戶數(shù)有0.5億人,而2019年微信月活躍用戶數(shù)達(dá)到了11億,是中國(guó)用戶量最大的APP.面對(duì)如此大規(guī)模的數(shù)據(jù)量,傳統(tǒng)的圖搜索方案已經(jīng)無(wú)法勝任.

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

大圖上各類算法,都會(huì)通過(guò)構(gòu)建索引信息,幫助在查詢時(shí)快速求解.大圖索引的建立和利用索引的查詢策略,是算法設(shè)計(jì)的關(guān)鍵.索引的構(gòu)建是為了根據(jù)圖局部結(jié)構(gòu)歸納信息,進(jìn)行狀態(tài)壓縮; 查詢策略需要在快速求解的同時(shí)保證問(wèn)題的完備性,大圖上現(xiàn)有的查詢算法,都需要對(duì)時(shí)間效率和空間效率進(jìn)行平衡[7].現(xiàn)有的2-hop類算法通過(guò)構(gòu)建由中介頂點(diǎn)構(gòu)成的2-hop類索引,加速搜索.該算法查詢時(shí)間雖然迅速,但是受限于存儲(chǔ)空間,不適合更大規(guī)模的圖上運(yùn)算.

為此本文提出了一種基于部分索引與局部搜索結(jié)合的跳數(shù)受限可達(dá)查詢算法.通過(guò)改變?cè)饕Y(jié)構(gòu),提高索引利用率,從而在減少空間占用同時(shí)保持查詢時(shí)間盡量低.本方法首先構(gòu)建了基礎(chǔ)的2-hop可達(dá)索引;然后采用了近鄰節(jié)點(diǎn)和大度數(shù)熱點(diǎn)頂點(diǎn)對(duì)索引進(jìn)行約簡(jiǎn); 最后采用索引表和局部搜索結(jié)合的方法進(jìn)行可達(dá)性查詢,能夠節(jié)省更多的索引空間,從而適用于解決更大規(guī)模的圖可達(dá)查詢問(wèn)題.

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

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

1.1 一般可達(dá)性查詢算法

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

（1）傳遞閉包類算法

該類算法利用設(shè)計(jì)的索引結(jié)構(gòu)對(duì)大圖可達(dá)性信息進(jìn)行預(yù)計(jì)錄,利用自身設(shè)計(jì)的各類索引結(jié)構(gòu)能夠快速查找頂點(diǎn)間的可達(dá)性關(guān)系.在索引設(shè)計(jì)上,這類算法利用了圖上局部結(jié)構(gòu)（如樹(shù)[11]、鏈[12]）的拓?fù)湫赃M(jìn)行剪枝并記錄,這一類算法在響應(yīng)時(shí)間上是最快的,如圖1所示.但是其自身的索引結(jié)構(gòu)會(huì)隨著圖規(guī)模的增大而快速增大,因此存儲(chǔ)空間是這類問(wèn)題的桎梏.隨著圖規(guī)模達(dá)到百萬(wàn)甚至千萬(wàn)頂點(diǎn)級(jí)別,這類算法已經(jīng)不能完成求解.

圖1 簡(jiǎn)單圖網(wǎng)絡(luò)

（2）hop索引類算法

該類算法利用一些選定的中繼節(jié)點(diǎn)作為中介,進(jìn)而考慮目標(biāo)頂點(diǎn)與中繼頂點(diǎn)間的可達(dá)性.隨著研究的不斷深入,該類算法利用的中繼結(jié)構(gòu)不再限于單頂點(diǎn),開(kāi)始利用鏈路、樹(shù)等圖結(jié)構(gòu)作為中間結(jié)構(gòu); 演化出了2-hop[13]類,演化成3-hop[14]、path-hop[15]類算法,如圖2所示,為簡(jiǎn)單圖網(wǎng)絡(luò)對(duì)應(yīng)的2-hop索引.

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

這一類算法在回答可達(dá)性查詢時(shí),只需要在對(duì)應(yīng)行索引上進(jìn)行搜索,尋找公共中介頂點(diǎn)的表項(xiàng).該類方法的關(guān)鍵是hop索引的建立,即選取合適的中介結(jié)構(gòu)輔助索引建立.

（3）索引+類算法

該類算法發(fā)現(xiàn)在實(shí)際搜索中,有向圖點(diǎn)對(duì)間的不可達(dá)查詢占了絕大多數(shù)[16]; 相比于發(fā)現(xiàn)可達(dá)性,他們更期望快速發(fā)現(xiàn)點(diǎn)對(duì)間的不可達(dá)關(guān)系,因此他們利用自身索引對(duì)可達(dá)性進(jìn)行快速篩選.

如果憑借索引不足以證明點(diǎn)對(duì)間的不可達(dá)關(guān)系,這類算法利用在線搜索用于判定頂點(diǎn)間的可達(dá)性.這類算法的空間占用是最小的,但相應(yīng)其查詢時(shí)間最長(zhǎng).

1.2 路徑查詢算法

路徑查詢算法按照索引規(guī)模、索引種類可以分為在線搜索[17]、地標(biāo)算法[18]、樹(shù)分解算法[19]等.

（1）在線搜索算法

在線搜索算法不利用索引信息,在圖上直接搜索兩點(diǎn)之間的路徑信息,在線搜索包括經(jīng)典的Dijkstra算法和Floyd-Warshall算法等.在后續(xù)發(fā)展中有了A*算法、蟻群算法等改進(jìn)的算法,該類算法在圖頂點(diǎn)規(guī)模達(dá)到百萬(wàn)及以上時(shí),即使在并行下,算法時(shí)間效率仍舊較為低下.

（2）地標(biāo)算法

地標(biāo)搜索是搜索最短路徑的一類近似算法.這類算法事先選定一些地標(biāo)點(diǎn),以地標(biāo)點(diǎn)作為中介,依次計(jì)算所有經(jīng)過(guò)地標(biāo)下的最短路徑信息; 將其中最短的路徑作為備選路徑[20].這類算法的效果取決于最短路徑是否經(jīng)過(guò)一個(gè)真實(shí)的地標(biāo)點(diǎn),因此合適的地標(biāo)點(diǎn)選取策略是這類算法的關(guān)鍵.目前常見(jiàn)的地標(biāo)選取策略通常是基于平均頂點(diǎn)度數(shù)和中心距離的啟發(fā)式算法.

樹(shù)分解類算法構(gòu)建了一棵新的索引樹(shù)[21],利用構(gòu)建的索引樹(shù),樹(shù)分解算法可以按級(jí)對(duì)小規(guī)模節(jié)點(diǎn)團(tuán)進(jìn)行搜索,最終構(gòu)建出最短路徑.該類算法將原圖中的一團(tuán)臨近節(jié)點(diǎn)縮為索引樹(shù)中的一個(gè)節(jié)點(diǎn),真實(shí)圖中的一條路徑對(duì)應(yīng)團(tuán)內(nèi)路徑和團(tuán)間路徑,利用搜索節(jié)點(diǎn)對(duì)的最小共同祖先和局部最短路徑搜索算法可以分別解決兩個(gè)子問(wèn)題,該類策略的關(guān)鍵是在樹(shù)高和團(tuán)內(nèi)節(jié)點(diǎn)數(shù)間平衡,并構(gòu)建出一棵合適的搜索樹(shù).

1.3 k跳可達(dá)性查詢

關(guān)于k跳可達(dá)算法,學(xué)術(shù)界已有算法相對(duì)較少,已有的k跳可達(dá)算法大多是有向圖上算法.基于頂點(diǎn)覆蓋集的k跳可達(dá)查詢算法通過(guò)求解原圖上的一個(gè)頂點(diǎn)覆蓋集,然后在頂點(diǎn)覆蓋集之上根據(jù)頂點(diǎn)之間的距離關(guān)系構(gòu)建關(guān)系閉包作為圖索引,在查詢時(shí)可以通過(guò)查詢頂點(diǎn)所在閉包索引,直接得到頂點(diǎn)間k跳可達(dá)關(guān)系.但是這個(gè)方法的空間復(fù)雜度較高,因?yàn)轫旤c(diǎn)覆蓋集中的頂點(diǎn)之間的關(guān)系越稠密,帶來(lái)的索引開(kāi)銷越大,k-reach 的索引空間和索引時(shí)間都隨著圖規(guī)模的增長(zhǎng)呈指數(shù)上漲.

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

近年國(guó)內(nèi)也有k跳可達(dá)查詢相關(guān)研究,基于雙向搜索的k跳查詢算法通過(guò)優(yōu)化雙向搜索過(guò)程提高了k跳可達(dá)性查詢的時(shí)間效率[23].基于圖壓縮的 k跳可達(dá)性查詢方法[24],通過(guò)對(duì)原圖進(jìn)行等價(jià)類的壓縮來(lái)降低圖的規(guī)模,提高算法的可拓展性.基于BFS樹(shù)的k跳查詢算法通過(guò)計(jì)算索引交集的計(jì)算方法,提高了算法的時(shí)間效率.

2 基于hop索引的k跳可達(dá)算法

k跳可達(dá)性查詢相較于一般的可達(dá)性查詢約束更為嚴(yán)格,因?yàn)橐话憧蛇_(dá)性查詢可以視為k=∞下的情況;k跳可達(dá)相較于最短路徑查詢約束較為寬松,因?yàn)閗跳可達(dá)在求解到一條跳數(shù)不大于k的路徑后,不關(guān)心點(diǎn)對(duì)間的最短路徑.

我們解決索引空間和查詢時(shí)間之間平衡的主要方法是:首先對(duì)于原索引中不常被利用缺占據(jù)大量空間的小度數(shù)頂點(diǎn)索引項(xiàng),按一定比率選取其中部分進(jìn)行“約簡(jiǎn)”操作.“約簡(jiǎn)”操作指:保留其近鄰頂點(diǎn)索引和經(jīng)過(guò)的大度數(shù)頂點(diǎn)索引,剔除其他索引項(xiàng).對(duì)于優(yōu)化后的索引表無(wú)法確定的查詢,轉(zhuǎn)用使用與索引表相結(jié)合使用LRU策略的局部搜索進(jìn)行補(bǔ)充搜索.

為了求解k跳可達(dá)問(wèn)題并優(yōu)化原索引結(jié)構(gòu),設(shè)計(jì)了算法1.

2.1 圖索引的建立

為了求解距離限制的可達(dá)查詢問(wèn)題,選用帶有距離信息的2-hop類索引,2-hop類索引維護(hù)著所有頂點(diǎn)對(duì)應(yīng)的2-hop表.當(dāng)兩個(gè)不同的頂點(diǎn)存在著一個(gè)公共的中介節(jié)點(diǎn)時(shí),說(shuō)明兩者可達(dá).此時(shí)查詢兩者對(duì)應(yīng)的距離標(biāo)簽,如果所有距離標(biāo)簽中最小的在限制范圍內(nèi),則說(shuō)明這兩個(gè)頂點(diǎn)是在限制范圍內(nèi)可達(dá)的.

構(gòu)建完整表的方法,依賴于頂點(diǎn)對(duì)間的距離信息.算法最開(kāi)始將每個(gè)頂點(diǎn)距自身距離為0的頂點(diǎn)加入自己對(duì)應(yīng)的表單中（自身）; 然后檢索所有的邊,構(gòu)建距離為1的項(xiàng),按照優(yōu)先度,將每條邊加入優(yōu)先度較高的頂點(diǎn)表單中,然后依照距離信息,遞歸的依次構(gòu)建基于距離的索引,直到構(gòu)建到距離為k的索引.

2.2 索引結(jié)構(gòu)的約簡(jiǎn)

2-hop類索引構(gòu)建時(shí),表單中索引項(xiàng)的選取都是單條最短路徑上優(yōu)先度最高的頂點(diǎn); 因此大度數(shù)頂點(diǎn)的索引項(xiàng)會(huì)較短,而小度數(shù)頂點(diǎn)的完整索引項(xiàng)會(huì)較繁瑣.回答完整性的可達(dá)性查詢,因保存這些邊緣頂點(diǎn)全部的信息犧牲掉了很大的存儲(chǔ)空間; 而真正查詢時(shí)針對(duì)這些邊緣頂點(diǎn)的查詢頻度也較低.這也造成了因存儲(chǔ)不能被及時(shí)利用的信息所造成的存儲(chǔ)空間浪費(fèi),此需要調(diào)整存儲(chǔ)空間和查詢時(shí)間之間的平衡.

為了彌補(bǔ)保留部分索引造成的信息丟失,在查詢時(shí)需要進(jìn)行局部搜索,檢測(cè)限制距離內(nèi)兩個(gè)目標(biāo)頂點(diǎn)之間的可達(dá)性關(guān)系,在社交圖中,除了邊緣頂點(diǎn)臨近的頂點(diǎn)外,利用其他高度數(shù)的頂點(diǎn)作為索引可以加速搜索.針對(duì)小度數(shù)邊緣頂點(diǎn)采用保留近鄰節(jié)點(diǎn)信息以及高度數(shù)代表頂點(diǎn)作為索引的策略,因社交圖上的頂點(diǎn)傾向于發(fā)現(xiàn)與自身相近的頂點(diǎn)或與熱點(diǎn)頂點(diǎn)間關(guān)系,所以保留兩種不同類型的頂點(diǎn)作為部分索引,使其加速整體索引搜索過(guò)程.

2.3 基于約簡(jiǎn)后索引表的查詢算法

2.3.1 可達(dá)性查詢算法

針對(duì)社交圖上2-hop索引信息不平衡的情況,本文通過(guò)保留近鄰節(jié)點(diǎn)和大度數(shù)代表頂點(diǎn)的手段約簡(jiǎn)了索引結(jié)構(gòu),整體查詢流程如圖3所示.

圖3 可達(dá)查詢算法流程圖

在查詢點(diǎn)對(duì)間可達(dá)性時(shí),首先在約簡(jiǎn)后的部分索引上進(jìn)行查詢,若查詢頂點(diǎn)并非小度數(shù)頂點(diǎn),則其對(duì)應(yīng)的表項(xiàng)是完整的,基于索引表的可達(dá)性查詢結(jié)果是完備的.若待查詢的頂點(diǎn)是小度數(shù)頂點(diǎn),則優(yōu)先在其約簡(jiǎn)后的部分索引上進(jìn)行2-hop索引查詢; 若經(jīng)過(guò)查詢后存在著k跳關(guān)系,則可以直接回答可達(dá)性,若未搜索到k跳可達(dá)關(guān)系,則需在LRU索引上查詢已有的可達(dá)性索引,查看是否近期已經(jīng)補(bǔ)全過(guò)對(duì)應(yīng)行索引.

若LRU索引上仍未有對(duì)應(yīng)的結(jié)果,則需在索引表上進(jìn)行對(duì)應(yīng)行的局部搜索; 并將補(bǔ)全后的行索引存入LRU索引,并將LRU索引進(jìn)行更新,在原索引表上的局部搜索過(guò)程與建立2-hop索引時(shí)的檢索過(guò)程一致,依據(jù)距離信息從小到大依次檢查約簡(jiǎn)的小度數(shù)頂點(diǎn)不同跳數(shù)下的2-hop關(guān)系,將其依次補(bǔ)全.

2.3.2 基于約簡(jiǎn)后索引表的查詢算法優(yōu)劣勢(shì)分析

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

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)分別測(cè)定了不同約簡(jiǎn)比率下、不同局部搜索方法、不同跳數(shù)下索引空間與查詢時(shí)間之間的關(guān)系.

3.1 數(shù)據(jù)集介紹與實(shí)驗(yàn)配置

本文選用的數(shù)據(jù)集來(lái)自斯坦福網(wǎng)絡(luò)分析項(xiàng)目提供的開(kāi)源數(shù)據(jù)集,YouTube[25]和Orkut數(shù)據(jù)集均為社交網(wǎng)絡(luò)數(shù)據(jù)集.其中YouTube數(shù)據(jù)集規(guī)模較小,該數(shù)據(jù)集頂點(diǎn)數(shù)為1134 890個(gè),邊數(shù)為2987 624條; Orkut數(shù)據(jù)集規(guī)模較大,該數(shù)據(jù)集頂點(diǎn)數(shù)為3072 441個(gè),邊數(shù)為117 185 083條,所有的實(shí)驗(yàn)都在單機(jī)Ubuntu 18.04.5 LTS環(huán)境下運(yùn)行.內(nèi)存為512 GB,實(shí)驗(yàn)環(huán)境的線程數(shù)最高為56個(gè).

3.2 評(píng)估標(biāo)準(zhǔn)與結(jié)果分析

由于本文提出的基于方法是基于hop類算法的k跳可達(dá)查詢算法,主要貢獻(xiàn)在于優(yōu)化hop類索引結(jié)構(gòu),能夠勝任規(guī)模更大的圖上快速查詢的任務(wù).因此在實(shí)驗(yàn)評(píng)估標(biāo)準(zhǔn)的選擇上,本文主要選擇索引空間、查詢時(shí)間兩個(gè)評(píng)估標(biāo)準(zhǔn).同時(shí)在對(duì)比方法選取上,本文選擇了2019年SIGMOD會(huì)議上提出的PSL索引算法[26],該算法已是最先進(jìn)的hop類算法.

整體實(shí)驗(yàn)方法分為兩部分:確定局部搜索策略和選用某一實(shí)驗(yàn)參數(shù).其中,不同局部搜索算法實(shí)驗(yàn)部分用于確定局部搜索算法,優(yōu)化比率實(shí)驗(yàn)部分用于確定實(shí)驗(yàn)的一個(gè)可變參數(shù):低度數(shù)頂點(diǎn)索引優(yōu)化比率.索引優(yōu)化實(shí)驗(yàn)部分用于測(cè)定在選用參數(shù)下索引空間和查詢時(shí)間之間的關(guān)系.

3.2.1 不同局部搜索算法實(shí)驗(yàn)

本文設(shè)計(jì)了多種不同的局部搜索算法,實(shí)驗(yàn)表中展示的是優(yōu)化后的基于啟發(fā)式搜索的雙向局部搜索與基于索引表的搜索方法間對(duì)比,本實(shí)驗(yàn)數(shù)據(jù)集采用YouTube數(shù)據(jù)集,對(duì)比了不同跳數(shù)（k）下兩種采納不同局部搜索算法與原算法（PSL）間索引空間和查詢時(shí)間的關(guān)系.

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

表1 不同跳數(shù)下搜索策略的索引空間和跳數(shù)間關(guān)系（B）

表2 不同跳數(shù)下搜索策略的查詢時(shí)間和跳數(shù)間關(guān)系（ms）

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

圖5 不同搜索算法時(shí)間性能比較

3.2.2 優(yōu)化比率實(shí)驗(yàn)

在確定了局部搜索算法的種類后,為了得到更好的空間優(yōu)化效果,同時(shí)保證時(shí)間性能在同一數(shù)量級(jí)下我們測(cè)試了不同優(yōu)化比率下查詢時(shí)間和索引空間的關(guān)系.優(yōu)化比率作為平衡索引時(shí)的一個(gè)重要參數(shù),影響的是約簡(jiǎn)小度數(shù)頂點(diǎn)的比例,優(yōu)化比率越低,被選中修改的小度數(shù)頂點(diǎn)項(xiàng)越少,實(shí)驗(yàn)測(cè)試數(shù)據(jù)集為YouTube數(shù)據(jù)集,測(cè)試了不同跳數(shù)下,不同優(yōu)化比率下的索引空間和查詢時(shí)間.

此處的優(yōu)化比率作為實(shí)驗(yàn)的一個(gè)參數(shù),可以根據(jù)實(shí)際需求人工配置.該比率越高保留的頂點(diǎn)數(shù)目越少,算法空間優(yōu)化比率越高; 比率越低,保留的原索引項(xiàng)越多,算法查詢時(shí)間消耗越低.本實(shí)驗(yàn)為了突出空間優(yōu)化效果,選用了查詢時(shí)間不發(fā)生顯著改變下的并有著較優(yōu)空間優(yōu)化效果的比率進(jìn)行測(cè)定.實(shí)際應(yīng)用時(shí),可以根據(jù)需求選取適當(dāng)?shù)膮?shù)配置.

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

表3 不同優(yōu)化比率下查詢時(shí)間與索引空間關(guān)系

3.2.3 索引優(yōu)化實(shí)驗(yàn)

確定了局部搜索算法和優(yōu)化比率后,我們?cè)谝?guī)模更大的社交網(wǎng)絡(luò)數(shù)據(jù)集下進(jìn)行了與原算法相比較新的對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)的性能評(píng)估指標(biāo),我們?nèi)耘f選定為索引空間和查詢時(shí)間.測(cè)定了不同跳數(shù)變化下,我們的算法與原算法相比性能的優(yōu)劣,

通過(guò)實(shí)驗(yàn)結(jié)果,由圖6和圖7可見(jiàn),從跳數(shù)為4開(kāi)始,本文的算法空間性能開(kāi)始逐步優(yōu)化,同時(shí)保證了時(shí)間效率上略高于原算法.具體實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表4,表5.其中索引空間可以優(yōu)化為原算法的68.18%,同時(shí)保證查詢時(shí)間為原算法1.38倍,保證了時(shí)間性能在原算法同一數(shù)量級(jí)下.

圖6 索引優(yōu)化前后空間性能比較

圖7 索引優(yōu)化前后時(shí)間性能比較

表4 索引優(yōu)化前后空間性能比較（B）

表5 索引優(yōu)化前后時(shí)間性能比較（ms）

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

4 結(jié)論與展望

本文針對(duì)2-hop類索引在k跳可達(dá)問(wèn)題上出現(xiàn)的因索引分布不均勻造成的空間浪費(fèi)的現(xiàn)象,提出了人工可控的平衡索引空間與查詢時(shí)間的優(yōu)化算法.該算法首先構(gòu)筑一般的2-hop類索引表,再根據(jù)約簡(jiǎn)比率對(duì)原索引表進(jìn)行平衡處理,并記錄下被處理過(guò)的小度數(shù)頂點(diǎn)標(biāo)號(hào).同時(shí),我們?cè)O(shè)計(jì)了與約簡(jiǎn)算法相應(yīng)的查詢算法,保證查詢的完備性,同時(shí)利用LRU機(jī)制加速查詢階段.在查詢可達(dá)性關(guān)系時(shí),首先在約簡(jiǎn)后的索引表上進(jìn)行查找,若查詢不到對(duì)應(yīng)頂點(diǎn)信息,則轉(zhuǎn)入LRU索引上查詢,若仍得不到肯定結(jié)果,再轉(zhuǎn)入局部搜索,并將結(jié)果更新至LRU索引上.

實(shí)驗(yàn)表明,我們的方法相比于已有的最先進(jìn)的索引方法,能夠有效地減小索引占用的空間,同時(shí)保證查詢時(shí)間增加的幅度可控.下一步的工作重點(diǎn),是設(shè)計(jì)針對(duì)不同圖類型和圖半徑等信息的參數(shù)自動(dòng)優(yōu)化算法,增強(qiáng)算法對(duì)不同類型的圖網(wǎng)絡(luò)的適應(yīng)性,同時(shí)設(shè)計(jì)新的機(jī)制,在優(yōu)化查詢時(shí)間上得到進(jìn)一步的發(fā)展.