XPath evaluation in linear time
Mikołaj Bojańczyk, Paweł Parys · Journal of the ACM · 2011
We consider a fragment of XPath 1.0, where attribute and text values may be compared. We show that for any unary query φ in this fragment, the set of nodes that satisfy the query in a document t can be calculated in time O (|φ| 3 | t |). We show that for a query in a bigger fragment with Kleene star allowed, the same can be done in time O (2 O (|φ|)|t|) or in time O (|φ| 3 |t|log|t|). Finally, we present algorithms for binary queries of XPath, which do a precomputation on the document and then output the selected pairs with constant delay.