隨著電腦以及網際網路的普及，越來越多各領域的資料被數位化，利用電腦幫助儲存及管理資料。有許多資料在數位化的過程中，採用tree的資料結構來表達以及儲存。也因此，如何查詢這些龐大的資料，就成為重要的課題。在本論文中，我們針對具有rooted、labeled以及ordered或unordered等特性的tree結構資料的索引問題，提出稱之為PCS-trie之全新的主記憶體資料庫(Main Memory Database)索引結構，並提出相關的增刪資料及搜尋演算法，以達成加速處理sub-tree query之目標。此索引方法的基礎，在於將tree database中的tree編碼為可完整代表其結構的PREOD code字串，之後再以我們所提出的PCS-trie加以索引。PCS-trie索引結構支援資料庫的動態增刪，且我們也提供了有效率的新增及刪除資料的演算法。本論文中也提出了多種搜尋演算法，使能夠在PCS-trie中進行exact matching、處理query tree含有don’t care部分之查詢、以及fault tolerant等不同類型的查詢。最後，我們以實驗的方法，配合人工產生的實驗資料，來對PCS-trie索引方法的時間及空間等各方面的效率加以檢驗。 / With the popularization of computer and the Internet, more and more data in various domains are digitized in order to take advantage of the power of computing and storing, and use the Internet to spread these informationz. Many data use tree structure to store them in the process of digitization. For this reason, it is a challenge to deal with these enormous data. In this paper, we present an approach to the search problem for these rooted labeled trees. We show a novel index structure, PREOD code Search trie (PCS-trie), and related algorithms for construction and search of PCS-trie, to speed up the sub-tree query to a tree database. The fundamental of this reaseach is to encode trees in tree database by PREOD code, in which the structure information of a tree can be reserved completely. Then we index these PREOD codes by PCS-trie. PCS-trie supports dynamic insertion and deleteion of PREOD codes. PCS-trie can handle three different types of query requirements: exact sub-tree query, query with don’t cares, and fault-tolerant query. Finally, we have conducted a series of experiments to evaluate the performance of PCS-trie and related algorithms. Experimental results obtained by running our techniques on synthetic data demonstrate the good performance of the proposed approach.
| Identifer | oai:union.ndltd.org:CHENGCHI/G0090753006 |
| Creators | 張詩宜, Shih-i Chang |
| Publisher | 國立政治大學 |
| Source Sets | National Chengchi University Libraries |
| Language | 中文 |
| Detected Language | English |
| Type | text |
| Rights | Copyright © nccu library on behalf of the copyright holders |
Page generated in 0.0021 seconds