Evaluating an XPath Query on a Streaming XML Document
Prakash V. Ramanan · 2005
We present an efficient algorithm for evaluating an XPath query Q (involving only child and descendant axes) on a streaming XML document D. Previously known in-memory algorithms for XPath evaluation use O(|D|) space and O(|Q||D|) time. Several previous al-gorithms for the streaming version use Θ(dn+c) space and Θ(dn|D|) time in the worst case; d is the depth of D, n is the number of location steps in Q, and c is the maximum number of candidate elements for output at any one time. In the worst case, the exponential Θ(dn) space alone could well exceed the O(|D|) space used by the in-memory algorithms. Our algorithm uses O(d|Q|+cn) space and O((|Q|+d+n2)|D|) time in the worst case. So, our algorithm is runtime competitive with the in-memory algorithms, while using much less memory space. 1