{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:48:35Z","timestamp":1773193715591,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>In online social networking, network monitoring and financial applications, there is a need to query high rate streams of XML data, but methods for executing individual XPath queries on streaming XML data have not kept pace with multicore CPUs. For data-parallel processing, a single XML stream is typically split into well-formed fragments, which are then processed independently. Such an approach, however, introduces a sequential bottleneck and suffers from low cache locality, limiting its scalability across CPU cores.<\/jats:p>\n          <jats:p>We describe a data-parallel approach for the processing of streaming XPath queries based on pushdown transducers. Our approach permits XML data to be split into arbitrarilysized chunks, with each chunk processed by a parallel automaton instance. Since chunks may be malformed, our automata consider all possible starting states for XML elements and build mappings from starting to finishing states. These mappings can be constructed independently for each chunk by different CPU cores. For streaming queries from the XPathMark benchmark, we show a processing throughput of 2.5 GB\/s, with near linear scaling up to 64 CPU cores.<\/jats:p>","DOI":"10.14778\/2556549.2556558","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1738-1749","source":"Crossref","is-referenced-by-count":15,"title":["Scalable XML query processing using parallel pushdown transducers"],"prefix":"10.14778","volume":"6","author":[{"given":"Peter","family":"Ogden","sequence":"first","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Thomas","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Pietzuch","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Faster FAST: Multicore acceleration of streaming financial data. CS - Research and Development, 23(3-4):249-257","author":"Agarwal V.","year":"2009","unstructured":"V. Agarwal, D. Bader, et al. Faster FAST: Multicore acceleration of streaming financial data. CS - Research and Development, 23(3-4):249-257, 2009."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"e_1_2_1_3_1","volume-title":"PlanX","author":"Avila-Campillo I.","year":"2002","unstructured":"I. Avila-Campillo, T. J. Green, et al. XMLTK: An XML toolkit for scalable XML stream processing. Technical report, PlanX, 2002."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142527"},{"key":"e_1_2_1_5_1","unstructured":"Boost Library. http:\/\/boost.org\/libs\/regex."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739063"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920873"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164153"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879010"},{"key":"e_1_2_1_10_1","first-page":"45","volume-title":"SCPL","author":"El-Hassan F.","year":"2009","unstructured":"F. El-Hassan and D. Ionescu. SCBXP: An efficient hardware-based XML parsing techn. In SCPL, pages 45-50, 2009."},{"key":"e_1_2_1_11_1","unstructured":"Expat Parser. http:\/\/expat.sourceforge.net."},{"key":"e_1_2_1_12_1","volume-title":"WebDB","author":"Fegaras L.","year":"2011","unstructured":"L. Fegaras, C. Li, U. Gupta, and J. Philip. XML query optimization in map-reduce. In WebDB, 2011."},{"key":"e_1_2_1_13_1","unstructured":"P. Fischer et al. XQuery: A lightweight full-featured XQuery engine. http:\/\/mxquery.org 2013."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11611257_25"},{"key":"e_1_2_1_15_1","volume-title":"XQuery Implementation Paradigms. Dagstuhl","author":"Franceschet M.","year":"2007","unstructured":"M. Franceschet. XPathMark: Functional and performance tests for XPath. In XQuery Implementation Paradigms. Dagstuhl, 2007."},{"key":"e_1_2_1_16_1","first-page":"350","volume-title":"Workshop on Foundations of Data Management","author":"Francis N.","year":"2011","unstructured":"N. Francis, C. David, and L. Libkin. A direct transation from XPath to nondet. automata. In Workshop on Foundations of Data Management, pages 350-361, 2011."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656444"},{"key":"e_1_2_1_18_1","unstructured":"D. Halstead. What sort of network and storage setup will be required to ingest the entire Twitter Firehose for 1 year. http:\/\/goo.gl\/kFXDH."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879007"},{"key":"e_1_2_1_20_1","first-page":"1315","volume-title":"ICDE","author":"Johnson T.","year":"2007","unstructured":"T. Johnson, S. Muthukrishnan, and I. Rozenbaum. Monitoring regular expressions on out-of-order streams. In ICDE, pages 1315-1319, 2007."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0123-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/WAIM.2008.11"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICGRID.2006.311019"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11515-8_12"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/646146.678868"},{"key":"e_1_2_1_26_1","volume-title":"XML best practices for Microsoft SQL Server","author":"Pal S.","year":"2005","unstructured":"S. Pal, V. Parikh, et al. XML best practices for Microsoft SQL Server 2005. Technical report, Microsoft, 2004."},{"key":"e_1_2_1_27_1","first-page":"1","volume-title":"IPDS","author":"Pan Y.","year":"2008","unstructured":"Y. Pan, Z. Zhang, and K. Chiu. Simul. transducers for data-parallel XML parsing. In IPDS, pages 1-12, 2008."},{"key":"e_1_2_1_28_1","unstructured":"PugiXML. http:\/\/pugixml.org\/benchmark\/."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287455"},{"key":"e_1_2_1_30_1","volume-title":"http:\/\/goo.gl\/c6O3X","year":"2013","unstructured":"Treebank dataset. http:\/\/goo.gl\/c6O3X, 2013."},{"key":"e_1_2_1_31_1","unstructured":"W3C XPath. w3.org\/TR\/1999\/REC-xpath-19991116."},{"key":"e_1_2_1_32_1","volume-title":"http:\/\/goo.gl\/dSFy","year":"2013","unstructured":"Wikipedia database. http:\/\/goo.gl\/dSFy, 2013."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0281-y"},{"key":"e_1_2_1_34_1","unstructured":"XML Generator. http:\/\/goo.gl\/QWvUJQ."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC.2011.74"},{"key":"e_1_2_1_36_1","first-page":"388","volume-title":"HiPC","author":"Zhang Y.","year":"2009","unstructured":"Y. Zhang, Y. Pan, and K. Chiu. Speculative p-DFAs for parallel XML parsing. In HiPC, pages 388-397, 2009."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2010.29"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2556549.2556558","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T22:36:00Z","timestamp":1729722960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2556549.2556558"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":37,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2556549.2556558"],"URL":"https:\/\/doi.org\/10.14778\/2556549.2556558","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}