Ctree: A Compact Two-level Bidirectional Tree for Indexing XML Data
Qinghua Zou, Shaorong Liu, Wesley W. Chu · 2004
Indexing XML data to facilitate query processing has been a popular subject of study in recent years. Most of previous studies can be classified into three categories: path indexing, node indexing and sequence-based indexing. Many of them cannot answer both single-path and branching queries with various value predicates very efficiently. In this paper, we propose a novel compact tree (Ctree) structure, which provides not only concise path summaries but also detailed element relationships, and a configurable index scheme based on data statistics. We develop an efficient Ctree-based method for processing a tree structure query with various value constraints. Efficiency of our method is achieved by: (1) summarizing a large database into a condensed structure view to prune irrelevant search space; (2) evaluating a tree structure query directly without expensive join operations; (3) using Ctree properties such as trivial groups and bi-direction to reduce query processing time; (4) using a new element-referring schema to avoid expensive join operations between the matches for value constraints and those for structure constraints. Our experiments reveal that Ctree is efficient in evaluating XML queries. It is about an order of magnitude faster than most previous methods. 1.