A Scalable XML Indexing Method Using MapReduce

With the advent of the era of 'big data', cloud computing technology is one of the promising solutions. Many theories and methods, which are originally designed for stand-alone, must be re-examined for the applicability in the cloud. For example, most of the XML indexing methods discussed in the literature are suitable for processing small XML files by stand-alone. When they deal with a large XML document, memory shortage problem will be encountered. In this thesis, we present an extension to an XML indexing schema called CIS-X(Compressed Indexing Schema for XML) using MapReduce implemented in Hadoop to handle the large XML documents through cloud parallel computing. The proposed method can be applied to any XML file without DTD or schema.XML已經被廣泛應用在網際網路的資料交換與儲存的文件格式，主要是XML可以定義自己的標籤，如同關聯式資料庫要可以定義欄位，但又比關聯式資料庫更有彈性，也使得有更多檔案是以XML的格式存在。面臨資料爆炸的時代，檔案勢必也會快速地增長，如何有效的讀取大型的XML檔案已經成為一個重要的議題 隨著要處理的資料量越來越大，雲端運算的技術也越來越重要，Hadoop MapReduce是一個支援雲端運算開放原始碼平台，例如文獻所探討的XML索引方法，大多適用於單機處理較小的XML檔案，若是要應用在大型的XML文件，容易造成記憶體不足的困境。本論文，提出了一個延伸CIS-X(Compressed Indexing Schema for XML)的設計，並實作於Hadoop MapReduce中，讓建立索引可以透過雲端平行運算來處理，解決單機記憶體不足以應付大型XML檔案的問題，並透過預先拆解的方式以可以處理更大的XML使其更有延展性。這個方法可以適用於任何沒有DTD或schema的XML文件。同時本研究也提供了相對應的查詢方法，讓大型XML文件的讀取更加便利。目次 第1章 緒論 8 1.1 研究背景 8 1.2 研究動機與目的 9 1.3 主要貢獻 9 1.4 論文架構 10 第2章 相關研究 11 2.1 Hadoop MapReduce 11 2.2 XML文件索引建構方法 13 2.2.1 Structural Summary 13 2.2.2 Structural Join 14 2.3 CIS-X的索引方法 15 2.3.1 建立索引結構 15 2.3.2 文件的查詢 17 2.4 相關論文比較 18 第3章 系統架構與演算法 21 3.1 系統架構 21 3.1.1 建立XML Index 21 3.1.2 XPath查詢處理 22 3.2 XML Index建構方法 23 3.2.1 XML拆解 24 3.2.2 建立Index 29 3.3 Query查詢方法 31 第4章 系統實作與實驗結果分析 35 4.1 CIS-X延展性問題探討 35 4.2 開發工具與實驗環境 36 4.3 資料集 38 4.4 索引方法 38 4.4.1 分割XML 38 4.4.2 MapReduce產生索引檔 39 4.4.3 索引方法比較 43 4.4.4 實驗結果分析 44 4.5 查詢方法 46 4.5.1 產生符合節點檔案 47 4.5.2 MapReduce產生Query結果 47 第5章 結論與未來研究方向 51 5.1 結論 51 5.2 未來研究方向 51 參考文獻 5