XML filtering systems aim to provide fast, on-the-fly matching of XML-encoded data to large numbers of query specifications containing constraints on both structure and content. It is now well accepted that approaches using event-based parsing and Finite State Machines (FSMs) can provide the basis for highly scalable structure-oriented XML filtering systems. The XFilter system [Altinel and Franklin 2000] was the first published FSM-based XML filtering approach. XFilter used a separate FSM per path query and a novel indexing mechanism to allow all of the FSMs to be executed simultaneously during the processing of a document. Building on the insights of the XFilter work, we describe a new method, called "YFilter" that combines all of the path queries into a single Nondeterministic Finite Automaton (NFA). YFilter exploits commonality among queries by merging common prefixes of the query paths such that they are processed at most once. The resulting shared processing provides tremendous improvements in structure matching performance but complicates the handling of value-based predicates. In this article, we first describe the XFilter and YFilter approaches and present results of a detailed performance comparison of structure matching for these algorithms as well as a hybrid approach. The results show that the path sharing employed by YFilter can provide order-of-magnitude performance benefits. We then propose two alternative techniques for extending YFilter's shared This work has been supported in part by the National Science Foundation under the ITR grants IIS0086057 and SI0122599, and CAREER grant IRI-9501353; by Rome Labs agreement no. F30602-97-2-0241 under DARPA order number F078, and by Boeing, IBM, Intel, Microsoft, Siemens, and the UC MICRO program. Authors' addresses: Y. Diao, M. J. Franklin, and H. Zhang, Department of EECS University of California, Berkeley, 421 Soda Hall, Berkeley, CA 94720; email: {diaoyl,franklin,nhz}@cs. berkeley.edu; M. Altinel, IBM Almaden Research Center, San Jose, CA 95120; email: maltinel@us. ibm.com; P. Fischer, Institute of Computer Science, University of Heidelberg, Heidelberg, Germany; email: peter.fischer@informatik.uni-heidelberg.de. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 1515 Broadway, New York, NY 10036 USA, fax: +1 (212) 869-0481, or permissions@acm.org. structure matching with support for value-based predicates, and compare the performance of these two techniques. The results of this latter study demonstrate some key differences between shared XML filtering and traditional database query processing. Finally, we describe how the YFilter approach is extended to handle more complicated queries containing nested path expressions.
Based on XFilter, a new system was proposed in REF termed YFilter that combined all of the path queries into a single Nondeterministic Finite Automaton (NFA) and exploited commonality among user profiles by merging common prefixes of the user profile paths such that they were processed at most once.
Path sharing and predicate evaluation for high-performance XML filtering
TODS
Computer Science