Processing XML Streams with Deterministic Automata Todd J. Green, Gerome Miklau, Makoto Onizuka, and Dan Suciu   View Paper (PDF)   Return to Research Papers Abstract We consider the problem of evaluating a large number of XPath expressions on an XML stream. Our main contribution consists in showing that Deterministic Finite Automata (DFA) can be used effectively for this problem: in our experiments we achieve a throughput of about 5.4MB/s, independent of the number of XPath expressions (up to 1,000,000 in our tests). The major problem we face is that of the size of the DFA. Since the number of states grows exponentially with the number of XPath expressions, it was previously believed that DFAs cannot be used to process large sets of expressions. We make a theoretical analysis of the number of states in the DFA resulting from XPath expressions, and consider both the case when it is constructed eagerly, and when it is constructed lazily. Our analysis indicates that, when the automaton is constructed lazily, and under certain assumptions about the structure of the input XML data, the number of states in the lazy DFA is manageable. We also validate experimentally our findings, on both synthetic and real XML data sets. BIBTEX  Lecture Notes in Computer Science  Publisher: Springer-Verlag Heidelberg  ISSN: 0302-9743  Subject:  Computer Science  Volume 2572 / 2003  Title:  : Database Theory - ICDT 2003: 9th International Conference Siena, Italy, January 8-10, 2003. Proceedings  Editors:  D. Calvanese, M. Lenzerini, R. Motwani (Eds.) :  Chapter: pp. 173 - 189 }, ©2005 Association for Computing Machinery