In 14th International Conference on Extending Database Technology (EDBT), pages 45-56, March 2011.
Content-based architectures for XML data dissemination are gaining increasing attention both in academia and industry. These dissemination networks are the building blocks of selective information dissemination applications which have wide applicability such as sharing and integrating information in both scientific and corporate domains. At the heart of these dissemination services is a fast engine for matching of an incoming XML message against stored XPath expressions to determine interested consumers for the message. To achieve the ultra-low response time, predominant in financial message processing, the XPath expression matching must be done efficiently. In this paper, we develop and evaluate a novel algorithm based on a unique encoding of XPath expressions and XML messages, unlike dominating automaton-based algorithms, for efficiently solving this matching problem. We demonstrate a matching time in the millisecond range for millions of XPath expressions which significantly outperforms state-of-the-art algorithms.