With the rapidly increasing popularity of XML as a data format, there is a large demand for efficient techniques in structural matching of XML data. We propose a novel filtering technique to speed up the structural matching of XML data, which is based on an auxiliary data structure called  suffix bitmap . The suffix bitmap captures in a packed format the suffix tag name list of the nodes in an XML document. By comparing the respective suffix bitmaps, most of the unmatched subtrees of a document can be skipped efficiently in the course of structural matching process. Using the suffix bitmap filtering, we extend two state-of-the-art structural matching algorithms: namely the  traversal matching  algorithm and the  structural join matching algorithm . The experimental results show that the extended algorithms considerably outperform the original ones.
['Feng Shao', 'Gang Chen', 'Jinxiang Dong']
Accelerating XML Structural Matching Using Suffix Bitmaps