Accelerating Parent-Child Path Matching in XML

With the rapidly increasing popularity of XML as a data format, there is a large demand for efficient XML structural matching techniques. Normally, data in XML are stored in a tree-like structure where nodes (with data) are located using the path relations in the tree. This paper proposes a coding policy named path code to accelerate an important category of structure matching in XML, namely the Parent-Child paths. A Parent-Child path is the path expression that contains only parent-child relationships. The proposed path code employs a partial prefix Path of XML elements using a special compression technique. Based on the path code, we present a Boosting algorithm, which has low-linear time complexity and little I/O cost, to match Parent-Child paths. In addition, we propose two heuristic policies to optimize the Boosting algorithm further by reducing the memory consumption. Our experiments show that the Boosting algorithm considerably outperforms previous algorithms in run-time Parent-Child path matching.