Web數據管理中的分布式圖數據存儲和查詢.pdf

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

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

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

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

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