{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T23:54:43Z","timestamp":1676678083334},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>Because of high volumes and unpredictable arrival rates, stream processing systems are not always able to keep up with input data - resulting in buffer overflow and uncontrolled loss of data. To produce eventually complete results, load spilling, which pushes some fractions of data to disks temporarily, is commonly employed in relational stream engines. In this work, we now introduce \"structure-based spilling\", a spilling technique customized for XML streams by considering the partial spillage of possibly complex XML elements. Such structure-based spilling brings new challenges. When a path is spilled, multiple paths may be affected. We analyze possible spilling effects on the query paths and how to execute the \"reduced\" query to produce partial results. To select the reduced query that maximizes output quality, we develop three optimization strategies, namely, OptR, OptPrune and ToX. We also examine the clean-up stage to guarantee that an entire result set is eventually generated by producing supplementary results. Our experimental study demonstrates that our proposed solutions consistently achieve higher quality results compared to the state-of-the-art techniques.<\/jats:p>","DOI":"10.14778\/1920841.1920998","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1267-1278","source":"Crossref","is-referenced-by-count":5,"title":["Achieving high output quality under limited resources through structure-based spilling in XML streams"],"prefix":"10.14778","volume":"3","author":[{"given":"Mingzhu","family":"Wei","sequence":"first","affiliation":[{"name":"Worcester Polytechnic Institute"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elke A.","family":"Rundensteiner","sequence":"additional","affiliation":[{"name":"Worcester Polytechnic Institute"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Murali","family":"Mani","sequence":"additional","affiliation":[{"name":"University of Michigan, Flint"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"228","volume-title":"FluxQuery: An Optimizing XQuery Processor for Streaming XML Data,\" in International Conference on Very Large Data Bases (VLDB)","author":"Koch C.","year":"2004","unstructured":"C. Koch , S. Scherzinger , N. Scheweikardt and B. Stegmaier , \" FluxQuery: An Optimizing XQuery Processor for Streaming XML Data,\" in International Conference on Very Large Data Bases (VLDB) , 2004 , pp. 228 -- 239 . C. Koch, S. Scherzinger, N. Scheweikardt and B. Stegmaier, \"FluxQuery: An Optimizing XQuery Processor for Streaming XML Data,\" in International Conference on Very Large Data Bases (VLDB), 2004, pp. 228--239."},{"key":"e_1_2_1_2_1","first-page":"261","volume-title":"International Conference on Very Large Data Bases (VLDB)","author":"Diao Y.","year":"2003","unstructured":"Y. Diao XML Message Brokering ,\" in International Conference on Very Large Data Bases (VLDB) , 2003 , pp. 261 -- 272 . Y. Diao et al., \"Query Processing for High-Volume XML Message Brokering,\" in International Conference on Very Large Data Bases (VLDB), 2003, pp. 261--272."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872809"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287390"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0078-5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872810"},{"issue":"2","key":"e_1_2_1_7_1","first-page":"27","article-title":"Xjoin: A reactively-scheduled pipelined join operator","volume":"23","author":"Urhan T.","year":"2000","unstructured":"T. Urhan , \" Xjoin: A reactively-scheduled pipelined join operator ,\" IEEE Data Engineering Bulletin , vol. 23 , no. 2 , pp. 27 -- 33 , 2000 . T. Urhan et al., \"Xjoin: A reactively-scheduled pipelined join operator,\" IEEE Data Engineering Bulletin, vol. 23, no. 2, pp. 27--33, 2000.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_8_1","first-page":"251","article-title":"Hash-merge join: A non-blocking join algorithm for producing fast and early join results","author":"Mokbel M.","year":"2004","unstructured":"M. Mokbel , , \" Hash-merge join: A non-blocking join algorithm for producing fast and early join results ,\" in Proceedings of ICDE , 2004 , p. 251 . M. Mokbel, et al., \"Hash-merge join: A non-blocking join algorithm for producing fast and early join results,\" in Proceedings of ICDE, 2004, p. 251.","journal-title":"Proceedings of ICDE"},{"key":"e_1_2_1_9_1","first-page":"841","article-title":"Early hash join: a configurable algorithm for the efficient and early production of join results","author":"Lawrence R.","year":"2005","unstructured":"R. Lawrence , \" Early hash join: a configurable algorithm for the efficient and early production of join results ,\" in VLDB , 2005 , pp. 841 -- 852 . R. Lawrence, \"Early hash join: a configurable algorithm for the efficient and early production of join results,\" in VLDB, 2005, pp. 841--852.","journal-title":"VLDB"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353414"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/mksc.19.1.4.15178"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584816"},{"key":"e_1_2_1_13_1","first-page":"241","volume-title":"Proceedings of the 27th VLDB Conference","author":"Manolescu I.","year":"2001","unstructured":"I. Manolescu , XML Queries on Heterogeneous Data Sources ,\" in Proceedings of the 27th VLDB Conference , Edinburgh, Scotland , 2001 , pp. 241 -- 250 . I. Manolescu, et al., \"Answering XML Queries on Heterogeneous Data Sources,\" in Proceedings of the 27th VLDB Conference, Edinburgh, Scotland, 2001, pp. 241--250."},{"key":"e_1_2_1_14_1","volume-title":"dissertation","author":"Chen L.","year":"2004","unstructured":"L. Chen , \"Semantic caching for xml queries,\" Ph. D. dissertation , Worcester Polytechnic Institute , 2004 . L. Chen, \"Semantic caching for xml queries,\" Ph.D. dissertation, Worcester Polytechnic Institute, 2004."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956917"},{"key":"e_1_2_1_16_1","first-page":"14","article-title":"Optimizing Regular Path Expressions Using Graph Schemas","author":"Fernandez M. F.","year":"1998","unstructured":"M. F. Fernandez , D. Suciu , \" Optimizing Regular Path Expressions Using Graph Schemas ,\" in ICDE , 1998 , pp. 14 -- 23 . M. F. Fernandez, D. Suciu, \"Optimizing Regular Path Expressions Using Graph Schemas,\" in ICDE, 1998, pp. 14--23.","journal-title":"ICDE"},{"key":"e_1_2_1_17_1","first-page":"17","article-title":"Architecting a network query engine for producing partial results","author":"Shanmugasundaram J.","year":"2000","unstructured":"J. Shanmugasundaram , , \" Architecting a network query engine for producing partial results ,\" in WebDB , 2000 , pp. 17 -- 22 . J. Shanmugasundaram, et al., \"Architecting a network query engine for producing partial results,\" in WebDB, 2000, pp. 17--22.","journal-title":"WebDB"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564769"},{"key":"e_1_2_1_19_1","first-page":"3","volume-title":"Heavy-tailed probability distributions in the world wide web,\" in In A Practical Guide To Heavy Tails","author":"Crovella M. E.","year":"1998","unstructured":"M. E. Crovella , , \" Heavy-tailed probability distributions in the world wide web,\" in In A Practical Guide To Heavy Tails , chapter 1. Chapman Hall , 1998 , pp. 3 -- 26 . M. E. Crovella, et al., \"Heavy-tailed probability distributions in the world wide web,\" in In A Practical Guide To Heavy Tails, chapter 1. Chapman Hall, 1998, pp. 3--26."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367613"},{"key":"e_1_2_1_21_1","first-page":"309","article-title":"Load shedding in a data stream manager","author":"Tatbul N.","year":"2003","unstructured":"N. Tatbul , , \" Load shedding in a data stream manager ,\" in VLDB , 2003 , pp. 309 -- 320 . N. Tatbul, et al., \"Load shedding in a data stream manager,\" in VLDB, 2003, pp. 309--320.","journal-title":"VLDB"},{"key":"e_1_2_1_22_1","volume-title":"Load shedding techniques for data stream systems.\" in MPDS","author":"Babcock B.","year":"2003","unstructured":"B. Babcock , , \" Load shedding techniques for data stream systems.\" in MPDS , 2003 . B. Babcock, et al., \"Load shedding techniques for data stream systems.\" in MPDS, 2003."},{"key":"e_1_2_1_23_1","first-page":"141","volume-title":"Feb 2002","author":"Al-Khalifa S.","unstructured":"S. Al-Khalifa , : A primitive for efficient xml query pattern matching,\" in IEEE International Conference on Data Engineering (ICDE) , Feb 2002 , p. 141 . S. Al-Khalifa, et al., \"Structural joins: A primitive for efficient xml query pattern matching,\" in IEEE International Conference on Data Engineering (ICDE), Feb 2002, p. 141."},{"key":"e_1_2_1_24_1","first-page":"443","article-title":"Structural Join Order Selection for XML Query Optimization","author":"Wu Y.","year":"2003","unstructured":"Y. Wu , J. M. Patel and H. V. Jagadish , \" Structural Join Order Selection for XML Query Optimization ,\" in ICDE , 2003 , pp. 443 -- 454 . Y. Wu, J. M. Patel and H. V. Jagadish, \"Structural Join Order Selection for XML Query Optimization,\" in ICDE, 2003, pp. 443--454.","journal-title":"ICDE"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920998","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:50:33Z","timestamp":1672228233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920998"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920998"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920998","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}