大規(guī)模圖數(shù)據(jù)可達(dá)查詢技術(shù)的研究.pdf

1、可達(dá)查詢是圖數(shù)據(jù)挖掘和管理中的重要基礎(chǔ)操作，被廣泛應(yīng)用于相關(guān)領(lǐng)域中，例如社會網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、以及語義Web等。針對可達(dá)查詢的研究已有幾十年的歷史，從早期的實時在線查詢到現(xiàn)在的各種索引技術(shù)的應(yīng)用，人們已經(jīng)取得了非常多研究成果。給定源點和終點，可達(dá)查詢的目標(biāo)主要是在圖中發(fā)現(xiàn)兩個結(jié)點間的連接狀態(tài)，具體可以包括判斷它們之間是否存在路徑、獲取它們之間的最短距離以及判斷它們之間的路徑上的標(biāo)簽是否符合某種特定規(guī)律。由于這個操作是很多其它

2、應(yīng)用的重要基礎(chǔ)，它的效率也會直接影響了其它應(yīng)用的性能，所以雖然簡單，可達(dá)查詢?nèi)匀皇菆D數(shù)據(jù)領(lǐng)域的一個研究熱點。目前雖然在這方面已經(jīng)出現(xiàn)了很多優(yōu)秀的算法，但是隨著信息技術(shù)的不斷發(fā)展，尤其是隨著大數(shù)據(jù)時代的來臨，使得圖數(shù)據(jù)的規(guī)模每年都呈幾何級數(shù)增長，這導(dǎo)致目前大部分經(jīng)典算法都面臨著可擴展性的問題。因此，為進(jìn)一步提高可達(dá)查詢的效率，人們?nèi)孕枰嗟年P(guān)于這方面的研究。
　　本文分析了現(xiàn)實世界中各類圖數(shù)據(jù)的特性，從中發(fā)現(xiàn)有益的規(guī)律，以此為基礎(chǔ)

3、，將目前的可達(dá)查詢相關(guān)研究成果分為三類，即無約束可達(dá)查詢、距離約束查詢和基于正則表達(dá)式查詢，并分別針對它們各自的操作特點提出索引的創(chuàng)建及改進(jìn)算法，具體研究工作如下:
　　(1)利用可達(dá)主干實現(xiàn)無約束可達(dá)查詢
　　傳統(tǒng)的方法都是在原圖的基礎(chǔ)之上利用所有結(jié)點創(chuàng)建索引，這使得這些方法的可擴展性很差，只能處理結(jié)點數(shù)量在幾萬以下的小規(guī)模圖數(shù)據(jù)。為此本文提出了一種“可達(dá)主干”的索引框架，該方法的主要理論來源是現(xiàn)實世界中大多數(shù)圖數(shù)據(jù)結(jié)點間

4、的關(guān)系不是均勻分布的，即各結(jié)點間在局部范圍內(nèi)聯(lián)系緊密，而在全局范圍內(nèi)聯(lián)系比較松散。利用了這一發(fā)現(xiàn)，本文首先將原圖按照社區(qū)劃分的方法分成若干個小的集合，然后從每個集合中選擇具有中心性質(zhì)的結(jié)點，該結(jié)點與本集合內(nèi)的所有其它結(jié)點都存在可達(dá)關(guān)系，利用這些結(jié)點可以建立一個能夠保留原圖全部拓?fù)湫畔⒌牟樵冏訄D。這個查詢子圖不是最終索引，但是它的規(guī)模遠(yuǎn)遠(yuǎn)小于原圖，而且結(jié)構(gòu)稀疏，可以非常方便地利用其它傳統(tǒng)的算法在該結(jié)構(gòu)的基礎(chǔ)上繼續(xù)建立索引。實驗結(jié)果表明，該

5、方法與類似的高效算法相比，在保證查詢效率的同時，在索引創(chuàng)建時間和索引規(guī)模方面明顯優(yōu)于其它算法。
　　(2)利用最短路徑主干和多級社區(qū)中心實現(xiàn)距離約束查詢
　　最短路徑主干與可達(dá)主干原理基本一樣，只是在創(chuàng)建主干的時候為邊集附上權(quán)值，成為一個帶權(quán)查詢子圖，與可達(dá)主干一樣，該方法可以有效地壓縮原圖的規(guī)模，形成一個結(jié)構(gòu)稀疏的小規(guī)模圖，非常有利于利用其它算法繼續(xù)在其上創(chuàng)建索引，實驗表明該結(jié)構(gòu)可以將其它算法處理的數(shù)據(jù)規(guī)模大幅度提高。但是

6、由于可達(dá)/最短路徑主干還需要借助于其它算法繼續(xù)建立索引，所以當(dāng)圖數(shù)據(jù)規(guī)模繼續(xù)增大后，該算法本身又會面臨著可擴展性的問題。為此，本文還提出了另外一種索引策略，即多級社區(qū)中心標(biāo)簽機制，該方法的主要思想是，在為原圖建立了可達(dá)/最短路徑主干后，不再借助于其它算法繼續(xù)建立索引，而是直接遞歸地使用該主干框架繼續(xù)為每一級主干建立查詢子圖。在操作的過程中，根據(jù)每次操作結(jié)果為圖中的每個結(jié)點計算標(biāo)簽，該多級社區(qū)中心標(biāo)簽可以很方便地應(yīng)用于可達(dá)或距離查詢，本文

7、主要研究如何將該算法應(yīng)用于目前普遍處理效率較低的無向復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的處理，實驗表明，該算法可以處理的數(shù)據(jù)規(guī)模和效率明顯優(yōu)于其它現(xiàn)存算法。
　　(3)利用索引實現(xiàn)基于正則表達(dá)式查詢
　　本文對邊上帶有標(biāo)簽的圖數(shù)據(jù)的可達(dá)查詢操作，即所謂的基于正則表達(dá)式的查詢也進(jìn)行了分析和研究，為這類查詢提出了兩種索引結(jié)構(gòu):第一種是利用了基于廣義表存儲結(jié)構(gòu)的壓縮的寬度優(yōu)先遍歷鄰接表，該方法首先為原圖建立了一個寬度優(yōu)先遍歷鄰接表，然后盡可能地將每個具

8、有相同邊標(biāo)簽的鄰接結(jié)點壓縮成為一個虛結(jié)點，最終形成了一個以廣義表形式存儲的壓縮的鄰接表，該結(jié)構(gòu)可以保留原圖的全部路徑信息，所以可以實現(xiàn)近似常數(shù)時間的查詢;第二種方法是為了解決第一種方法直接在原圖上建立索引從而使得索引存儲代價過大問題，該方法首先利用頂點集合覆蓋的原理，通過一個“2-近似”算法生成一個近似最小頂點集合覆蓋，并在它的基礎(chǔ)上按照路徑標(biāo)簽為原圖建立一個索引，由于該方法只選擇部分結(jié)點，所以索引規(guī)模得到有效壓縮。實驗結(jié)果表明，這兩種