Skip to Main content Skip to Navigation
Conference papers

XPath Node Selection over Grammar-Compressed Trees

Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Tom Sebastian Connect in order to contact the contributor
Submitted on : Wednesday, October 30, 2013 - 5:05:21 PM
Last modification on : Wednesday, April 6, 2022 - 3:48:16 PM

Links full text



Tom Sebastian, Sebastian Maneth. XPath Node Selection over Grammar-Compressed Trees. TTATT 2013, Oct 2013, Hanoi, Vietnam. ⟨10.4204/EPTCS.134.5⟩. ⟨hal-00878748⟩



Record views