XPath Node Selection over Grammar-Compressed Trees

Sebastian Maneth
(University of Edinburgh)
Tom Sebastian
(Innovimax and INRIA)

XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees in PTIME: the query is translated into an automaton which is executed in one pass over the grammar. This result is well-known and has been mentioned before. Here we present precise bounds on the time complexity of this problem, in terms of big-O notation. For a given grammar and XPath query, we consider three different tasks: (1) to count the number of nodes selected by the query, (2) to materialize the pre-order numbers of the selected nodes, and (3) to serialize the subtrees at the selected nodes.

In Sebastian Maneth: Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2013), Hanoi, Vietnam, 19/10/2013, Electronic Proceedings in Theoretical Computer Science 134, pp. 38–48.
Published: 20th November 2013.

ArXived at: http://dx.doi.org/10.4204/EPTCS.134.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org