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.
Type de document :
Communication dans un congrès
TTATT 2013, Oct 2013, Hanoi, Vietnam. 2013, 〈10.4204/EPTCS.134.5〉
Liste complète des métadonnées

Contributeur : Tom Sebastian <>
Soumis le : mercredi 30 octobre 2013 - 17:05:21
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27

Lien texte intégral



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



Consultations de la notice