Path Index for XML Data Based on PATRICIA-TRIES
with the advent of XML as a standard for data representation and exchange on the Internet, storing and querying XML data becomes more and more important. This poses a new challenge concerning indexing and searching XML data, because conventional approaches based on relational model may not meet the processing requirements for XML data. In this paper, we propose a path index based on PATRICIA tries, namely PT index. Our PT index structure offers several novel features. First, it can support to fast search data by its structure based on PATRICIA-tries. Second, the path indexes are compressed so that they can be store in memory. Thirdly, because PT index includes structure and text of XML data, we can achieve results form the PT index without reading original XML data. We address time complexity and space complexity of PT index. Experimental results from our prototype system implementation show that the PT index can outperform some representative index approaches, such as DataGuide, B+tree index and Index Fabric.