Predicate-based Filtering of XPath Expressions

Shuang Huo and Hans-Arno Jacobsen.

CSRG-514, University of Toronto, 2006.
Pages 1-22, extended version of ICDE'2006 paper (with proofs).

Share

Abstract

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.

Download



Tags: content-based publish/subscribe, xml routing, xpath query, topss, x-topss


Readers who enjoyed the above work, may also like the following:
  • Predicate-based Filtering of XPath Expressions.
    Shuang Huo and Hans-Arno Jacobsen.
    In IEEE International Conference on Data Engineering (ICDE), page 53, Atlanta, GA, April 2006.
    Acceptance rate: 20%. Number of submissions: 456.
    Tags: content-based matching, content-based publish/subscribe, topss, xpath query, xml routing, x-topss
  • Routing of XML and XPath Queries in Data Dissemination Networks.
    Guoli Li, Shuang Huo, and Hans-Arno Jacobsen.
    In 28th International Conference on Distributed Computing Systems (ICDCS), pages 627-638, June 2008.
    Acceptance rate: 16%. Number of submissions: 638.
    Tags: xml routing, xpath query, content-based publish/subscribe, x-topss
  • XML Routing in Data Dissemination Networks.
    Guoli Li, Shuang Huo, and Hans-Arno Jacobsen.
    In IEEE 23rd International Conference on Data Engineering (ICDE), pages 1400-1404, April 2007.
    Acceptance rate: 28%. Number of submissions: 659.
    Tags: content-based publish/subscribe, publish/subscribe, xml routing, xpath query, x-topss