|
Published Articles >> Table of Contents >> Abstract
19th International Conference on Data Engineering (ICDE'03)
p. 391
PBiTree Coding and Efficient Processing of Containment Joins
Wei Wang, The Hong Kong University of Sci. & Tech.
Haifeng Jiang, The Hong Kong University of Sci. & Tech.
Hongjun Lu, The Hong Kong University of Sci. & Tech.
Jeffrey Xu Yu, The Chinese University of Hong Kong
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2003.1260808
Send link to a friend
| Abstract |
|
This paper addresses issues related to containment join processing in tree-structured data such as XML documents. A containment join takes two sets of XML node elements as input and returns pairs of elements such that the containment relationship holds between them. While there are previous algorithms for processing containments joins, they require both element sets either sorted or indexed. This paper proposes a novel and complete containment query processing framework based on a new coding scheme, PBiTree code. The PBiTree code allows us to determine the ancestor-descendant relationship between two elements from their PBiTree-based codes efficiently. We present algorithms in the framework that are optimized for various combinations of settings. In particular, the newly proposed partitioning based algorithms can process containment joins efficiently without sorting or indexes. Experimental results indicate that the containment join processing algorithms based on the proposed coding scheme outperform existing algorithms significantly.
|
 Additional Information
|
Citation:
Wei Wang, Haifeng Jiang, Hongjun Lu, Jeffrey Xu Yu,
"PBiTree Coding and Efficient Processing of Containment Joins,"
icde,
p. 391,
19th International Conference on Data Engineering (ICDE'03),
2003
|
|
