{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:44:16Z","timestamp":1762505056757},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>We have implemented and released the XSQ system for evaluating XPath queries on streaming XML data. XSQ supports XPath features such as multiple predicates, closures, and aggregation, which pose interesting challenges for streaming evaluation. Our implementation is based on using a hierarchical arrangement of augmented finite state automata. A design goal of XSQ is buffering data for the least amount of time possible. We present a detailed experimental study that characterizes the performance of XSQ and related systems, and that illustrates the performance implications of XPath features such as closures.<\/jats:p>","DOI":"10.1145\/1071610.1071617","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"577-623","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["XSQ"],"prefix":"10.1145","volume":"30","author":[{"given":"Feng","family":"Peng","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}]},{"given":"Sudarshan S.","family":"Chawathe","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"The Lorel query language for semistructured data","volume":"1","author":"Abiteboul S.","year":"1996","unstructured":"Abiteboul , S. , Quass , D. , McHugh , J. , Widom , J. , and Wiener , J. 1996 . The Lorel query language for semistructured data . J. Dig. Lib. 1 , 1 (Nov.), 68--88. Abiteboul, S., Quass, D., McHugh, J., Widom, J., and Wiener, J. 1996. The Lorel query language for semistructured data. J. Dig. Lib. 1, 1 (Nov.), 68--88.","journal-title":"J. Dig. Lib."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB)","author":"Altinel M.","unstructured":"Altinel , M. and Franklin , M. J . 2000. Efficient filtering of XML documents for selective dissemination of information . In Proceedings of the International Conference on Very Large Data Bases (VLDB) ( Cairo, Egypt), 53--64. Altinel, M. and Franklin, M. J. 2000. Efficient filtering of XML documents for selective dissemination of information. In Proceedings of the International Conference on Very Large Data Bases (VLDB) (Cairo, Egypt), 53--64."},{"key":"e_1_2_1_3_1","unstructured":"Avila-Campillo I. Raven D. Green T. Gupta A. Kadiyska Y. Onizuka M. and Suciu D. 2002. An XML toolkit for light-weight XML stream processing. http:\/\/www.cs.washington.edu\/homes\/suciu\/XMLTK\/.  Avila-Campillo I. Raven D. Green T. Gupta A. Kadiyska Y. Onizuka M. and Suciu D. 2002. An XML toolkit for light-weight XML stream processing. http:\/\/www.cs.washington.edu\/homes\/suciu\/XMLTK\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564769"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the PLAN-X Workshop on Programming Language Technologies for XML","author":"Barton C.","unstructured":"Barton , C. , Charles , P. , Fontoura , M. , Goyal , D. , Josifovski , V. , and Raghavachari , M . 2002. An algorithm for streaming XPath processing with forward and backward axes . In Proceedings of the PLAN-X Workshop on Programming Language Technologies for XML ( Pittsburgh, Pa). Barton, C., Charles, P., Fontoura, M., Goyal, D., Josifovski, V., and Raghavachari, M. 2002. An algorithm for streaming XPath processing with forward and backward axes. In Proceedings of the PLAN-X Workshop on Programming Language Technologies for XML (Pittsburgh, Pa)."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE)","author":"Barton C. M.","unstructured":"Barton , C. M. , Charles , P. G. , Goyal , D. , Raghavachari , M. , Josifovski , V. , and Fontoura , M. F . 2003. Streaming XPath processing with forward and backward axes . In Proceedings of the International Conference on Data Engineering (ICDE) ( Bangalore, India). 455--466. Barton, C. M., Charles, P. G., Goyal, D., Raghavachari, M., Josifovski, V., and Fontoura, M. F. 2003. Streaming XPath processing with forward and backward axes. In Proceedings of the International Conference on Data Engineering (ICDE) (Bangalore, India). 455--466."},{"key":"e_1_2_1_8_1","unstructured":"Becker O. 2002. Joost is ollie's original streaming transformer. http:\/\/joost.sourceforge.net\/.  Becker O. 2002. Joost is ollie's original streaming transformer. http:\/\/joost.sourceforge.net\/."},{"key":"e_1_2_1_9_1","unstructured":"Becker O. Cimprich P. and Nentwich C. 2002. Streaming transformations for XML. http:\/\/www.gingerall.cz\/stx.  Becker O. Cimprich P. and Nentwich C. 2002. Streaming transformations for XML. http:\/\/www.gingerall.cz\/stx."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT)","author":"Benedikt M.","unstructured":"Benedikt , M. , Fan , W. , and Kuper , G . 2003. Structural properties of XPath fragments . In Proceedings of the International Conference on Database Theory (ICDT) ( Siena, Italy). Benedikt, M., Fan, W., and Kuper, G. 2003. Structural properties of XPath fragments. In Proceedings of the International Conference on Database Theory (ICDT) (Siena, Italy)."},{"key":"e_1_2_1_11_1","unstructured":"Boag S. Chamberlin D. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2003. XQuery 1.0: An XML query language 1.0. W3C Working Draft W3C http:\/\/www.w3.org\/TR\/xquery\/. August.  Boag S. Chamberlin D. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2003. XQuery 1.0: An XML query language 1.0. W3C Working Draft W3C http:\/\/www.w3.org\/TR\/xquery\/. August."},{"key":"e_1_2_1_12_1","unstructured":"Borne K. D. 2002. ADC dataset GSFC\/NASA XML project. http:\/\/xml.gsfc.nasa.gov\/archive\/.  Borne K. D. 2002. ADC dataset GSFC\/NASA XML project. http:\/\/xml.gsfc.nasa.gov\/archive\/."},{"key":"e_1_2_1_13_1","unstructured":"Bray T. Paoli J. Sperberg-McQueen C. and Maler E. 2000. Extensible markup language (XML) 1.0 (2nd Edition). World Wide Web Consortium Recommendation. |http:\/\/www.w3.org\/TR\/REC-xml|.  Bray T. Paoli J. Sperberg-McQueen C. and Maler E. 2000. Extensible markup language (XML) 1.0 (2nd Edition). World Wide Web Consortium Recommendation. |http:\/\/www.w3.org\/TR\/REC-xml|."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233368"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE)","author":"Chan C. Y.","unstructured":"Chan , C. Y. , Felber , P. , Garofalakis , M. N. , and Rastogi , R . 2002. Efficient filtering of XML documents with XPath expressions . In Proceedings of the International Conference on Data Engineering (ICDE) ( San Jose, Calif.). 235--244. Chan, C. Y., Felber, P., Garofalakis, M. N., and Rastogi, R. 2002. Efficient filtering of XML documents with XPath expressions. In Proceedings of the International Conference on Data Engineering (ICDE) (San Jose, Calif.). 235--244."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE)","author":"Chen Z.","unstructured":"Chen , Z. , Jagadish , H. V. , Korn , F. , Koudas , N. , Muthukrishnan , S. , Ng , R. T. , and Srivastava , D . 2001. Counting twig matches in a tree . In Proceedings of the International Conference on Data Engineering (ICDE) ( Heidelberg, Germany). 595--604. Chen, Z., Jagadish, H. V., Korn, F., Koudas, N., Muthukrishnan, S., Ng, R. T., and Srivastava, D. 2001. Counting twig matches in a tree. In Proceedings of the International Conference on Data Engineering (ICDE) (Heidelberg, Germany). 595--604."},{"key":"e_1_2_1_18_1","unstructured":"Clark J. and DeRose S. 1999. XML path language (XPath) version 1.0. W3C Recommedation W3C http:\/\/www.w3.org\/TR\/xpath. Nov.  Clark J. and DeRose S. 1999. XML path language (XPath) version 1.0. W3C Recommedation W3C http:\/\/www.w3.org\/TR\/xpath. Nov."},{"key":"e_1_2_1_19_1","unstructured":"Deutsch A. Fern\u00e1ndez M. F. Florescu D. Levy A. and Suciu D. 1998. XML-QL: A query language for XML. http:\/\/www.w3.org\/xml\/.  Deutsch A. Fern\u00e1ndez M. F. Florescu D. Levy A. and Suciu D. 1998. XML-QL: A query language for XML. http:\/\/www.w3.org\/xml\/."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE)","author":"Diao Y.","unstructured":"Diao , Y. , Fischer , P. , and Franklin , M. J . 2002. YFilter: Efficient and scalable filtering of XML documents . In Proceedings of the International Conference on Data Engineering (ICDE) ( San Jose, Calif.). 341--344. Diao, Y., Fischer, P., and Franklin, M. J. 2002. YFilter: Efficient and scalable filtering of XML documents. In Proceedings of the International Conference on Data Engineering (ICDE) (San Jose, Calif.). 341--344."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253403"},{"key":"e_1_2_1_22_1","unstructured":"Fern\u00e1ndez M. F. and Sim\u00e9on J. 2002. Galax. http:\/\/db.bell-labs.com\/galax\/.  Fern\u00e1ndez M. F. and Sim\u00e9on J. 2002. Galax. http:\/\/db.bell-labs.com\/galax\/."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB)","author":"Gottlob G.","unstructured":"Gottlob , G. , Koch , C. , and Pichler , R . 2002. Efficient algorithms for processing XPath queries . In Proceedings of the International Conference on Very Large Data Bases (VLDB) ( Hong Kong, China). Gottlob, G., Koch, C., and Pichler, R. 2002. Efficient algorithms for processing XPath queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB) (Hong Kong, China)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773171"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT)","author":"Green T. J.","unstructured":"Green , T. J. , Miklau , G. , Onizuka , M. , and Suciu , D . 2003. Processing XML streams with deterministic automata . In Proceedings of the International Conference on Database Theory (ICDT) ( Siena, Italy). 173--189. Green, T. J., Miklau, G., Onizuka, M., and Suciu, D. 2003. Processing XML streams with deterministic automata. In Proceedings of the International Conference on Database Theory (ICDT) (Siena, Italy). 173--189."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872809"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322295"},{"key":"e_1_2_1_28_1","volume-title":"P. L., Wood, L., Nicol, G., Robie, J., Champion, M.","author":"Hors A. L.","year":"2000","unstructured":"Hors , A. L. , Hg aret , P. L., Wood, L., Nicol, G., Robie, J., Champion, M. , and Byrne, S. 2000 . Document object model level 2 core specification. W3C Recommendation, W3C, http:\/\/www.w3.org\/TR\/2000\/REC-DOM-Level-2-Core-20001113. November. Hors, A. L., Hgaret, P. L., Wood, L., Nicol, G., Robie, J., Champion, M., and Byrne, S. 2000. Document object model level 2 core specification. W3C Recommendation, W3C, http:\/\/www.w3.org\/TR\/2000\/REC-DOM-Level-2-Core-20001113. November."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Katz H. 2002. XQEngine. http:\/\/www.fatdog.com.  Katz H. 2002. XQEngine. http:\/\/www.fatdog.com.","DOI":"10.1145\/504689.504690"},{"key":"e_1_2_1_30_1","volume-title":"SAXON: An XSLT processor","author":"Kay M. H.","year":"2002","unstructured":"Kay , M. H. 2002 . SAXON: An XSLT processor . http:\/\/saxon.sourceforge.net\/. Kay, M. H. 2002. SAXON: An XSLT processor. http:\/\/saxon.sourceforge.net\/."},{"key":"e_1_2_1_31_1","unstructured":"Kay M. 2003. XSL transformations (XSLT) version 2.0. W3C Working Draft W3C http:\/\/www.w3.org\/TR\/xslt20\/. November.  Kay M. 2003. XSL transformations (XSLT) version 2.0. W3C Working Draft W3C http:\/\/www.w3.org\/TR\/xslt20\/. November."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 8th International Conference on Extending Database Technology (Prague, Czech Republic). 142--160","author":"Lakshmanan L. V.","unstructured":"Lakshmanan , L. V. and Sailaja , P . 2002. On efficient matching of streaming XML documents and queries . In Proceedings of the 8th International Conference on Extending Database Technology (Prague, Czech Republic). 142--160 . Lakshmanan, L. V. and Sailaja, P. 2002. On efficient matching of streaming XML documents and queries. In Proceedings of the 8th International Conference on Extending Database Technology (Prague, Czech Republic). 142--160."},{"key":"e_1_2_1_34_1","unstructured":"Ley M. 2003. Computer science bibliography. http:\/\/dblp.uni-trier.de\/xml\/.  Ley M. 2003. Computer science bibliography. http:\/\/dblp.uni-trier.de\/xml\/."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB)","author":"Ludascher B.","unstructured":"Ludascher , B. , Mukhopadhayn , P. , and Papakonstantinou , Y . 2002. A transducer-based XML query processor . In Proceedings of the International Conference on Very Large Data Bases (VLDB) ( Hong Kong, China). 227--238. Ludascher, B., Mukhopadhayn, P., and Papakonstantinou, Y. 2002. A transducer-based XML query processor. In Proceedings of the International Conference on Very Large Data Bases (VLDB) (Hong Kong, China). 227--238."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543623"},{"key":"e_1_2_1_37_1","volume-title":"Tech. Rep. PMS-FB-2002-12","author":"Olteanu D.","year":"2002","unstructured":"Olteanu , D. , Kiesling , T. , and Bry , F . 2002 . An evaluation of regular path expressions with qualifiers against XML streams. Tech. Rep. PMS-FB-2002-12 , Institute for Computer Science, Ludwig-Maximilians University , Munich, Germany, May. Olteanu, D., Kiesling, T., and Bry, F. 2002. An evaluation of regular path expressions with qualifiers against XML streams. Tech. Rep. PMS-FB-2002-12, Institute for Computer Science, Ludwig-Maximilians University, Munich, Germany, May."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872810"},{"key":"e_1_2_1_39_1","volume-title":"Tech. Rep. CS-TR-4565 (UMIACS-TR-2004-10), Department of Computer Science","author":"Peng F.","year":"2004","unstructured":"Peng , F. and Chawathe , S. S . 2004 . XPaSS: A multi-query streaming XPath engine. Tech. Rep. CS-TR-4565 (UMIACS-TR-2004-10), Department of Computer Science , University of Maryland. May . Peng, F. and Chawathe, S. S. 2004. XPaSS: A multi-query streaming XPath engine. Tech. Rep. CS-TR-4565 (UMIACS-TR-2004-10), Department of Computer Science, University of Maryland. May."},{"key":"e_1_2_1_40_1","volume-title":"SAX: Simple API for XML","author":"Sax Project Organization","year":"2001","unstructured":"Sax Project Organization . 2001 . SAX: Simple API for XML . http:\/\/www.saxproject.org\/. Sax Project Organization. 2001. SAX: Simple API for XML. http:\/\/www.saxproject.org\/."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543622"},{"key":"e_1_2_1_42_1","first-page":"1","article-title":"Applying punctuation schemes to queries over continuous data streams","volume":"26","author":"Tucker P. A.","year":"2003","unstructured":"Tucker , P. A. , Maier , D. , and Sheard , T. 2003 . Applying punctuation schemes to queries over continuous data streams . Bull. Tech. Comm. Data Eng. 26 , 1 (Mar.), 33--40. Tucker, P. A., Maier, D., and Sheard, T. 2003. Applying punctuation schemes to queries over continuous data streams. Bull. Tech. Comm. Data Eng. 26, 1 (Mar.), 33--40.","journal-title":"Bull. Tech. Comm. Data Eng."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/30.1.35"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071610.1071617","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:25:52Z","timestamp":1672244752000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071610.1071617"}},"subtitle":["A streaming XPath engine"],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071610.1071617"],"URL":"https:\/\/doi.org\/10.1145\/1071610.1071617","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}