Clustered Chain Path Index for XML Document: Efficiently Processing Branch Queries |
| |
Authors: | Hongqiang Wang Jianzhong Li Hongzhi Wang |
| |
Affiliation: | (1) School of Computer Science and Technology, Harbin Institute of Technology, Harbin, 150001, China |
| |
Abstract: | Branch query processing is a core operation of XML query processing. In recent years, a number of stack based twig join algorithms
have been proposed to process twig queries based on tag stream index. However, in tag stream index, each element is labeled
separately without considering the similarity among elements. Besides, algorithms based on tag stream index perform inefficiently
on large document. This paper proposes a novel index, named Clustered Chain Path Index, based on a novel labeling scheme.
This index provides efficient support for processing branch queries. It also has the same cardinality as 1-index against tree
structured XML document. Based on CCPI, efficient algorithms, KMP-Match-Path and Related-Path-Segment-Join, are proposed to
process queries efficiently. Analysis and experimental results show that proposed query processing algorithms based on CCPI
outperform other algorithms and have good scalability.
This paper is partially supported by Natural Science Foundation of Heilongjiang Province, Grant No. zjg03-05 and National
Natural Science Foundation of China, Grant No. 60473075 and Key Program of the National Natural Science Foundation of China,
Grant No. 60533110. |
| |
Keywords: | XML index clustered chain path CCPI TwigStack 1-index |
本文献已被 SpringerLink 等数据库收录! |
|