Processing XML streams with deterministic automata and stream indexes Export

@article{citeulike:349352, abstract = {We consider the problem of evaluating a large number of XPath expressions on a stream of XML packets. We contribute two novel techniques. The first is to use a single Deterministic Finite Automaton (DFA). The contribution here is to show that the DFA can be used effectively for this problem: in our experiments we achieve a constant throughput, independently of the number of XPath expressions. The major issue is the size of the DFA, which, in theory, can be exponential in the number of XPath expressions. We provide a series of theoretical results and experimental evaluations that show that the lazy DFA has a small number of states, for all practical purposes. These results are of general interest in XPath processing, beyond stream processing. The second technique is the Streaming IndeX (SIX), which consists of adding a small amount of binary data to each XML packet that allows the query processor to achieve significant speedups. As an application of these techniques we describe the XML Toolkit (XMLTK), a collection of command-line tools providing highly scalable XML data processing.}, address = {New York, NY, USA}, author = {Green, Todd J. and Gupta, Ashish and Miklau, Gerome and Onizuka, Makoto and Suciu, Dan}, citeulike-article-id = {349352}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1042051}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1042046.1042051}, doi = {10.1145/1042046.1042051}, issn = {0362-5915}, journal = {ACM Trans. Database Syst.}, keywords = {automata, streams, xml}, month = {December}, number = {4}, pages = {752--788}, posted-at = {2005-10-13 08:19:31}, priority = {2}, publisher = {ACM Press}, title = {Processing XML streams with deterministic automata and stream indexes}, url = {http://dx.doi.org/10.1145/1042046.1042051}, volume = {29}, year = {2004} }

TY - JOUR ID - citeulike:349352 L3 - citeulike-article-id:349352 N2 - We consider the problem of evaluating a large number of XPath expressions on a stream of XML packets. We contribute two novel techniques. The first is to use a single Deterministic Finite Automaton (DFA). The contribution here is to show that the DFA can be used effectively for this problem: in our experiments we achieve a constant throughput, independently of the number of XPath expressions. The major issue is the size of the DFA, which, in theory, can be exponential in the number of XPath expressions. We provide a series of theoretical results and experimental evaluations that show that the lazy DFA has a small number of states, for all practical purposes. These results are of general interest in XPath processing, beyond stream processing. The second technique is the Streaming IndeX (SIX), which consists of adding a small amount of binary data to each XML packet that allows the query processor to achieve significant speedups. As an application of these techniques we describe the XML Toolkit (XMLTK), a collection of command-line tools providing highly scalable XML data processing. IS - 4 JF - ACM Trans. Database Syst. SN - 0362-5915 AD - New York, NY, USA EP - 788 TI - Processing XML streams with deterministic automata and stream indexes PB - ACM Press VL - 29 SP - 752 KW - automata KW - streams KW - xml AU - Green, Todd AU - Gupta, Ashish AU - Miklau, Gerome AU - Onizuka, Makoto AU - Suciu, Dan PY - 2004/12// UR - http://dx.doi.org/10.1145/1042046.1042051 ER -