Shuang Huo and Hans-Arno Jacobsen.
CSRG-514, University of Toronto, 2006.
Pages 1-22, extended version of ICDE'2006 paper (with proofs).
The XML/XPath filtering problem has found wide-spread interest. In this paper, we propose a novel algorithm for solving it. Our approach encodes XPath expressions (XPEs) as ordered sets of predicates and translates XML documents into sets of tuples, which are evaluated over these predicates. Predicates representing overlapping portions of XPEs are stored and processed once, thus fully exploiting potential overlap in XPEs. We experimentally evaluate the performance of our algorithm, demonstrating its scalability to millions of XPEs, with matching performance in the millisecond range. We show interesting trade-offs to alternative approaches.
Tags: content-based publish/subscribe, xml routing, xpath query, topss, x-topss
Readers who enjoyed the above work, may also like the following:
|