Efficient Algorithm for Evaluating Multiple XPath Expressions

The need for efficient algorithms for evaluating a large number of XPath expressions is increasing mostly because XPath is gaining acceptance as a language for specifying filters that select XML documents. However, existing algorithms have limitations in that (1) they cannot handle the full XPath language because their execution models are event-based, (2) they require time proportional to the number of XPath expressions and (3) they do not allow us to add or remove XPath expressions incrementally. We present an algorithm that solves all of these problems. The main idea of the algorithm is (1) to construct a data structure that represents multiple XPath expressions in order to evaluate shared subexpressions only once and (2) to repeatedly apply a conventional XPath processor to the data structure. We show that our algorithm is efficient by evaluating the performance of a prototype implementation.