Web數(shù)據(jù)管理中的分布式圖數(shù)據(jù)存儲和查詢.pdf

1、隨著萬維網(wǎng)(WorldWideWeb,WEB或WWW)規(guī)模和應(yīng)用的飛速發(fā)展,Web數(shù)據(jù)爆炸式增長,Web數(shù)據(jù)已經(jīng)形成了世界上最龐大的數(shù)據(jù)庫。此外,Web數(shù)據(jù)的相關(guān)數(shù)據(jù)如搜索記錄、各種Web服務(wù)使用記錄數(shù)據(jù)等都在迅速增長。與傳統(tǒng)的數(shù)據(jù)相比,Web數(shù)據(jù)具有非結(jié)構(gòu)化,增長速度快以及數(shù)據(jù)類型多樣的特點,這使得Web數(shù)據(jù)的處理方式和現(xiàn)有的數(shù)據(jù)處理方式存在著較大的區(qū)別。在現(xiàn)實的各個領(lǐng)域中,Web數(shù)據(jù)處理技術(shù)有著廣泛的需求和應(yīng)用,因此對于Web數(shù)據(jù)的

2、研究已經(jīng)成為當(dāng)今計算機科學(xué)的一個重點。
　　 為此,我們介紹了CWI[1],一種新的海量數(shù)據(jù)查詢和存儲工具。在CWI的實際應(yīng)用中,需要對大量的Web數(shù)據(jù)進行存儲和索引,并且在此基礎(chǔ)上實現(xiàn)關(guān)鍵字和結(jié)構(gòu)信息的查詢。TLGM[2]和TLGM-QL[3]作為CWI的一部分,滿足了上述要求。本文主要著重于在分布式的環(huán)境下實現(xiàn)TLGM數(shù)據(jù)模型的存儲,并且實現(xiàn)了TLGM-QL的四個基本算子。在設(shè)計和實現(xiàn)過程中,我們發(fā)現(xiàn)真實環(huán)境數(shù)據(jù)的不均衡性會

3、導(dǎo)致存儲和查詢算法的退化,從而降低效率。針對這些問題,本文提出了一系列均衡措施,保證各節(jié)點的運算和存儲負載差異保持在一個合理的范圍之內(nèi)。在此基礎(chǔ)上,本文提出了新的子圖重構(gòu)的算法,以支持對于圖結(jié)構(gòu)的查詢,并通過均衡措施保證算法的效率。本文通過對虛擬數(shù)據(jù)和真實環(huán)境數(shù)據(jù)的實驗驗證了系統(tǒng)的有效性。
　　 本文的貢獻和創(chuàng)新之處總結(jié)如下:
　　 1.本文分析了Web數(shù)據(jù)的特性,并引入了TLGM模型來說明圖數(shù)據(jù)在存儲、索引和查詢方面和

4、傳統(tǒng)數(shù)據(jù)的區(qū)別。本文首先在集中式的環(huán)境下分析了使用關(guān)系數(shù)據(jù)庫存儲圖數(shù)據(jù)的可能性,收集整理了若干圖數(shù)據(jù),并且設(shè)計了一系列的查詢,通過實驗來驗證該條件下圖數(shù)據(jù)存儲和查詢的效率,由此說明集中式存儲的不足和局限性。
　　 2.分析了TLGM的特性,從而闡述在分布式環(huán)境下實現(xiàn)該數(shù)據(jù)模型存儲和查詢的實現(xiàn)方法。在此基礎(chǔ)上,我們概括了TLGM圖數(shù)據(jù)模型可以滿足的各類查詢條件,并在此基礎(chǔ)上提出了四個基本的算子,并舉例說明這些算子具有良好的擴展性。

5、同時我們給出在分布式環(huán)境下這些算子的實現(xiàn)方法以及具體算法。
　　 3.提出了新的圖重構(gòu)的算法,介紹了如何使用該算法來實現(xiàn)對于圖結(jié)構(gòu)的查詢。本文通過MapReduce[4]框架來實現(xiàn)該算法,該算法具有良好的可擴展性,并允許我們緩存重構(gòu)的結(jié)果從而提高效率。在實現(xiàn)過程中,我們發(fā)現(xiàn)不同數(shù)據(jù)節(jié)點負載差異較大,從而通過對原算法進行若干修改從而達到負載均衡。同時我們生成并收集了若干圖數(shù)據(jù),并且通過一系列的實驗來驗證該方法的有效性。