An Efficient Bottom-up Filtering of XML Messages by Exploiting the Postfix Commonality of XPath Queries

Jaehoon KIM  Youngsoo KIM  Seog PARK  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.8   pp.2124-2133
Publication Date: 2008/08/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.8.2124
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Contents Technology and Web Information Systems
XML data filtering,  bottom-up approach,  postfix sharing,  nondeterministic finite automaton,  

Full Text: PDF>>
Buy this Article

 | Errata[Uploaded on September 1,2008]

Recently, for more efficient filtering of XML data, YFilter system has been suggested to exploit the prefix commonalities that exist among path expressions. Sharing the prefix commonality gives the benefit of improving filtering performance through the tremendous reduction in filtering machine size. However, exploiting the postfix commonality can also be useful for an XML filtering situation. For example, when a stream of XML messages does not have any defined schema, or users cannot remember the defined schema exactly, users often use the partial matching path queries which begins with the descendant axis ("//"), e.g., '//science/article/title', '//entertainment/article/title', and '//title'. If so, the registered XPath queries are most likely to have the postfix commonality, e.g., the sample queries share the partial path expressions 'article/title' and 'title'. Therefore, in this paper, we introduce a bottom-up filtering approach exploiting the postfix commonality against the top-down approach of YFilter exploiting the prefix commonality. Some experimental results show that our method has better filtering performance when registered XPath queries mainly consist of the partial matching path queries with the postfix commonality.