XAOS: An Algorithm for Streaming XPath Processing with Forward and Backward Axes

XAOS (pronounced "chaos") is an algorithm for streaming XPath processing which allows expressions that use both forward and backward axes. Currently, XAOS handles four major axes present in XPath (ancestor, parent, child, and descendent), and allows predicates in expressions using the 'and' operator. The techniques, however, are extensible to handle all thirteen axes in XPath.

In traditional XPath processing, an XML parser parses the XML document to be searched, creating an in-memory DOM tree representation of the dcoument. The XPath engine then searches the DOM tree for portions of the document which match the specification. This approach is shown in Figure 1. As mentioned above, memory overhead may be extensive for large documents. Additionally, the time bounds for traditional XPath implementations may be non-optimal as they may unnecessarily traverse the input XML document several times.

In the streaming XPath processing approach of XAOS, an XPath expression is converted into an XPath specific automaton. The XML document is parsed using an XML parser, which notifies the XAOS processor of parsing events as they occur. The XPath processor performs the online matching of elements from the XML document with the expression specified in the XPath query. The processor outputs XML fragments that match the XPath expression. This approach is illustrated in Figure 2.
Figure 2.

Comparative Results: Xalan vs. XAOS

Xalan is an XPath processor which supporbts forward and backward axes using the whole document approach. In a comparative analysis between Xalan and XAOS, XAOS performed significantly better than Xalan when comparing parsing + XPath evaluation times. For a 7 MB document, Xalan required just over 50 seconds to complete the evaluation, while XAOS performed the task in less than 40 seconds. This represents a gain of more than 20% in processing time.

When comparing XPath evaluation time alone, XAOS outperfromed Xalan by more than 100%, requiring less than 6 seconds for evaluation of a 6.67 MB document versus more than 12 seconds for Xalan. Furthermore, XAOS is much more scalable. For a 100 MB document, Xalan requires almost 1200 seconds to process the document, while XAOS requires approximatley 100 seconds. XAOS has been shown to scale linearly for documents over 1GB in size.