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

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

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

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

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

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

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

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

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