Signature-based filtering techniques for structural joins of XML data

Queries on XML documents typically combine selections on element contents, and, via path expressions, the structural relationships between tagged elements. Efficient support for structural joins is thus the key to efficient implementation of XML queries. With a stack to keep ancestordescendant structural relationships, stack-tree join algorithm enhances the performance of structural joins by reducing deducible unnecessary comparisons. However, stack-tree join cannot prevent "unwanted" comparisons between elements that do no participate in the join. To solve this problem, we propose a signature filter, which takes advantage of encoding schemes proposed for XML and occupies a little space. Then we present an pointer-based signature filter to skip the "unwanted" elements. In order to further improve the filtering efficiency, we finally propose an optimized pointer-based filter with the conjunction of two signatures. Performance study shows that our signature-based filters have excellent filtering performance and significantly improve the performance of structural joins.