Path sharing and predicate evaluation for high-performance XML filtering

ABSTRACT

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 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.

REFERENCES

• 1: Demet Aksoy , Mehmet Altinel , Rahul Bose , Ugur Çetintemel , Michael J. Franklin , Jane Wang , Stanley B. Zdonik, Research in Data Broadcast and Dissemination, Proceedings of the First International Conference on Advanced Multimedia Content Processing, p.194-207, November 09-11, 1998
• 2: Mehmet Altinel , Demet Aksoy , Thomas Baby , Michael Franklin , William Shapiro , Stan Zdonik, DBIS-toolkit: adaptable middleware for large scale data delivery, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.544-546, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 4: Apache XML Project. 1999. Xerces Java parser 1.2.3 Release. http://xml.apache.org/xerces-j/index.html.
• 5: Nicholas J. Belkin , W. Bruce Croft, Information filtering and information retrieval: two sides of the same coin?, Communications of the ACM, v.35 n.12, p.29-38, Dec. 1992 [doi>10.1145/138859.138861]
• 6: Bruno, N., Gravano, L., Koudas, N., and Srivastava, D. 2003. Navigation- vs. index-based XML multi-query processing. In Proceedings of ICDE 2003. IEEE Computer Society Press, Los Alamitos, Calif.
• 7: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 8: Busse, R., Carey, M., Florescu, D., Kersten, M., Manolescu, I., Schmidt, A., and Waas, F. 2001. Xmark: An XML benchmark project. http://monetdb.cwi.nl/xml/index.html.
• 9: Self-Adaptive User Profiles for Large-Scale Data Delivery, Proceedings of the 16th International Conference on Data Engineering, p.622, February 28-March 03, 2000
• 10: Chamberlin, D., Fankhauser, P., Florescu, D., Marchiori, M., and Robie, J. 2002. XML query use cases. W3C Working Draft. http://www.w3.org/TR/2002/WD-xmlquery-use-cases-20020430.
• 11: Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
• 12: Design and Evaluation of Alternative Selection Placement Strategies in Optimizing Continuous Queries, Proceedings of the 18th International Conference on Data Engineering, p.345, February 26-March 01, 2002
• 13: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 14: Clark, J. 1999. XSL transformations (XSLT)---version 1.0. http://www.w3.org/TR/xslt.
• 15: Clark, J., and DeRose, S. 1999. XML path language (XPath)---version 1.0. http://www.w3.org/TR/xpath.
• 16: Cover, R. 1999. The SGML/XML Web Page. http://www.w3.org/TR/xslt.
• 17: DeRose, S., Daniel Jr., R., and Maler, E. 1999. XML pointer language (XPointer). http://www.w3.org/TR/WD-xptr.
• 18: Diaz, A. L., and Lovell, D. 1999. XML generator. http://www.alphaworks.ibm.com/tech/xmlgenerator.
• 19: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 20: Peter W. Foltz , Susan T. Dumais, Personalized information delivery: an analysis of information filtering methods, Communications of the ACM, v.35 n.12, p.51-60, Dec. 1992 [doi>10.1145/138859.138866]
• 21: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 22: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
• 23: Chris Carnes , J. B. Park , Albert Vernon, Scalable Trigger Processing, Proceedings of the 15th International Conference on Data Engineering, p.266, March 23-26, 1999
• 24: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 25: Ives, Z., Levy, A., and Weld, D. 2000. Efficient evaluation of regular path expressions on streaming XML data. Technical Report, University of Washington, Seattle, Wash.
• 26: Kay, M. 2001. Saxon: the XSLT processor. http://users.iclway.co.uk/mhkay/saxon/.
• 27: Laks V. S. Lakshmanan , Sailaja Parthasarathy, On Efficient Matching of Streaming XML Documents and Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.142-160, March 25-27, 2002
• 28: Ley, M. 2001. DBLP DTD. http://www.acm.org/sigmod/dblp/db/about/dblp.dtd.
• 29: Ling Liu , Calton Pu , Wei Tang, Continual Queries for Internet Scale Event-Driven Information Delivery, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.610-628, July 1999 [doi>10.1109/69.790816]
• 30: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 31: Svetlozar Nestorov , Jeffrey D. Ullman , Janet L. Wiener , Sudarshan S. Chawathe, Representative Objects: Concise Representations of Semistructured, Hierarchial Data, Proceedings of the Thirteenth International Conference on Data Engineering, p.79-90, April 07-11, 1997
• 32: Benjamin Nguyen , Serge Abiteboul , Grégory Cobena , Mihaí Preda, Monitoring XML data on the Web, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.437-448, May 21-24, 2001, Santa Barbara, California, United States
• 33: Bahattin Ozen , Ozgur Kilic , Mehmet Altinel , Asuman Dogac, Highly personalized information delivery to mobile clients, Proceedings of the 2nd ACM international workshop on Data engineering for wireless and mobile access, p.35-42, May 2001, Santa Barbara, California, United States [doi>10.1145/376868.376891]
• 34: João Pereira , Françoise Fabret , Hans-Arno Jacobsen , François Llirbat , Dennis Shasha, WebFilter: A High-throughput XML-based Publish and Subscribe System, Proceedings of the 27th International Conference on Very Large Data Bases, p.723-724, September 11-14, 2001
• 35: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 36: Sax Project Organization. 2001. SAX: Simple API for XML. http://www. saxproject.org.
• 37: Ulf Schreier , Hamid Pirahesh , Rakesh Agrawal , C. Mohan, Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS, Proceedings of the 17th International Conference on Very Large Data Bases, p.469-478, September 03-06, 1991
• 38: Michael Stonebraker , Anant Jhingran , Jeffrey Goh , Spyros Potamianos, On rules, procedure, caching and views in data base systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.281-290, May 23-26, 1990, Atlantic City, New Jersey, United States
• 39: Sun Microsystems, Inc. 2001. Java XML pack. Winter 01 update release. http://java.sun.com/xml/downloads/javaxmlpack.html.
• 40: Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States
• 41: Bruce W. Watson, Practical Optimizations for Automata, Revised Papers from the Second International Workshop on Implementing Automata, p.232-240, September 18-20, 1997
• 42: Jennifer Widom , S. J. Finkelstein, Set-oriented production rules in relational database systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.259-270, May 23-26, 1990, Atlantic City, New Jersey, United States
• 43: Wutka. 2000. DTD parser. http://www.wutka.com/dtdparser.html.
• 44: Tak W. Yan , Héctor García-Molina, Index structures for selective dissemination of information under the Boolean model, ACM Transactions on Database Systems (TODS), v.19 n.2, p.332-364, June 1994 [doi>10.1145/176567.176573]
• 45: Tak W. Yan , Hector Garcia-Molina, The SIFT information dissemination system, ACM Transactions on Database Systems (TODS), v.24 n.4, p.529-565, Dec. 1999 [doi>10.1145/331983.331992]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering
      H.3.4 Systems and Software

General Terms:
Algorithms, Performance

Keywords:
Nondeterministic Finite Automaton, XML filtering, content-based matching, nested path expressions., path sharing, predicate evaluation, structure matching