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

https://hal.inria.fr/hal-00878748
Contributor : Tom Sebastian <>
Submitted on : Wednesday, October 30, 2013 - 5:05:21 PM
Last modification on : Thursday, February 21, 2019 - 10:52:55 AM

Links full text

Identifiers

Citation

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

Share

Metrics

Record views

326