An Efficient XML Keyword Search Indexing Method Based on Modified UCIS-X Index

The UCIS-X (An Updatable Compressing and Indexing Scheme for XML) indexing method uses the Dewey encoding to record the parent-child relationship of nodes in an XML file, and the branch information between XML nodes are encoded in Branch maps. UCIS-X outperforms other XML indexing schemes in terms of index space and query response time. But its performance will be downgraded in case of keyword search in XML file with large contents due to linear list used the content-index. In this thesis, we modified the Content-Index of UCIS-X by designing a hashed content-index using content keywords as hash keys to improve the performance on keyword search. The experimental results show that the proposed method has about 44% performance improvement over UCIS-X on the content-rich benchmark dataset XMark, and it also has about 65.5% performance improvement over UCIS-X on structure-duplicated dataset DBLP.UCIS-X (An Updatable Compressing and Indexing Scheme for XML)利用杜威編碼紀錄XML中節點間的關係，將每個節點在文件中的實例位置以Branch Map表示並記錄其分支情況，此方法在很小的索引空間下，仍能達到快速的查詢。然而，要在資料的結構極為相似，且有很多內容值的文件中，進行關鍵字搜尋時，UCIS-X需走訪所有對應節點的完整內容值，在查詢時將需花費大量的比對時間，造成速度上的低落。 本論文以內文關鍵字為導向建立內文索引檔，採用由下而上的比對方式改進此問題，以關鍵字為導向避免走訪原始內文索引檔，並沿用原UCIS-X的Level-Tag-Index，加速Query查詢時的路徑比對，從Branch Map比對實例結果，並將內容回傳給使用者。實驗結果顯示在針對內文豐富的資料集XMark，於查詢效能上平均較原UCIS-X的方法可提升44%的效能，而在結構相似的資料集DBLP上可提升65.5%的效能，能有效加速關鍵字查詢時的效率。目錄 摘要 i 目錄 ii 表目錄 iii 圖目錄 iv 第1章 緒論 - 1 - 1.1 研究背景及動機 - 1 - 1.2 主要貢獻 - 2 - 1.3 論文架構 - 3 - 第2章 相關研究 - 4 - 2.1 XML關鍵字查詢 - 4 - 2.2 UCIS-X的索引方法 - 9 - 第3章 前備知識及問題定義 - 15 - 3.1 資料模型與查詢型態 - 15 - 3.2 問題定義 - 17 - 第4章 內文索引檔建置與內文查詢改善方法 - 18 - 4.1 索引檔 - 18 - 4.2 查詢流程 - 25 - 第5章 系統實作與實驗結果 - 29 - 5.1 開發工具與實驗環境 - 29 - 5.2 測試資料集及查詢組合 - 30 - 5.3 系統效能 - 31 - 5.3.1 索引空間的比較 - 31 - 5.3.2 時間效能的比較 - 33 - 5.3.3 不同內容索引方法的時間比較 - 42 - 第6章 結論與未來研究方向 - 44 - 6.1 結論 - 44 - 6.2 未來研究方向 - 45 - 參考文獻 - 46