Schema-Conscious Filtering of XML Documents

In a publish-subscribe system based on filtering of XML doc-uments, subscribers specify their interests with profiles ex-pressed in the XPath language. The system processes a stream of XML documents and delivers to subscribers a no-tification or content of documents that match the profiles. For filtering with profiles expressed as linear XPath queries, automaton-based approaches exist where the intractable size growth of a preconstructed deterministic finite automaton is avoided by using a nondeterministic automaton. In this arti-cle we examine how these general approaches, which do not assume the existence of any specific schema or document type definition (DTD), might benefit from the knowledge that all the XML documents to be filtered obey a given DTD. We present an algorithm that utilizes the DTD in the preprocessing phase of the filtering automaton to prune out descendant operators (//) and wildcards (∗) from the lin-ear XPath filters. Experiments with data obtained from the XML Data Repository of the Univ. of Washington indi-cate that filter pruning can increase the throughput of the nondeterministic YFilter automaton by Diao et al. by a fac-tor of 2 to 20. We also present a new filtering algorithm that is based on a backtracking deterministic finite automa-ton derived from the classic Aho–Corasick pattern-matching automaton. This automaton has a size linear in the sum of the sizes of the filters. For our algorithm, we obtained a throughput of 15 MB/sec for filters pruned from one million original filters (with all wildcards and non-leading descen-dant operators eliminated), representing an improvement by a factor of 2 to 3 upon the throughput of YFilter. 1