{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:25:16Z","timestamp":1758273916172},"reference-count":16,"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>In XML search systems twig queries specify predicates on node values and on the structural relationships between nodes, and a key operation is to join individual query node matches into full twig matches. Linear time twig join algorithms exist, but many non-optimal algorithms with better average-case performance have been introduced recently. These use somewhat simpler data structures that are faster in practice, but have exponential worst-case time complexity. In this paper we explore and extend the solution space spanned by previous approaches. We introduce new data structures and improved strategies for filtering out useless data nodes, yielding combinations that are both worst-case optimal and faster in practice. An experimental study shows that our best algorithm outperforms previous approaches by an average factor of three on common benchmarks. On queries with at least one unselective leaf node, our algorithm can be an order of magnitude faster, and it is never more than 20% slower on any tested benchmark query.<\/jats:p>","DOI":"10.14778\/1920841.1920955","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"894-905","source":"Crossref","is-referenced-by-count":12,"title":["Fast optimal twig joins"],"prefix":"10.14778","volume":"3","author":[{"given":"Nils","family":"Grimsmo","sequence":"first","affiliation":[{"name":"Norwegian University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Truls A.","family":"Bj\u00f8rklund","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magnus Lie","family":"Hetland","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1451940.1451962"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_3_1","volume-title":"Proc. VLDB","author":"Chen Songting","year":"2006","unstructured":"Songting Chen , Hua-Gang Li , Junichi Tatemura , Wang-Pin Hsiung , Divyakant Agrawal , and K. Sel\u00e7uk Candan . Twig2Stack: bottom-up processing of generalized-tree-pattern queries over XML documents . In Proc. VLDB , 2006 . Songting Chen, Hua-Gang Li, Junichi Tatemura, Wang-Pin Hsiung, Divyakant Agrawal, and K. Sel\u00e7uk Candan. Twig2Stack: bottom-up processing of generalized-tree-pattern queries over XML documents. In Proc. VLDB, 2006."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066209"},{"key":"e_1_2_1_5_1","unstructured":"Massimo Franceschet. XPathMark web page. http:\/\/sole.dimi.uniud.it\/~massimo.franceschet\/xpathmark\/.  Massimo Franceschet. XPathMark web page. http:\/\/sole.dimi.uniud.it\/~massimo.franceschet\/xpathmark\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1060"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315476"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2395856.2395869"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564707"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85654-2_45"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783823.1783914"},{"key":"e_1_2_1_12_1","volume-title":"Proc. ICDE","author":"Rao Praveen","year":"2004","unstructured":"Praveen Rao and Bongki Moon . PRIX : Indexing and querying XML using Pr\u00fcfer sequences . In Proc. ICDE , 2004 . Praveen Rao and Bongki Moon. PRIX: Indexing and querying XML using Pr\u00fcfer sequences. In Proc. ICDE, 2004."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497491"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031271"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375722"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978103"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920955","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:39:28Z","timestamp":1672227568000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920955"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":16,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920955"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920955","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}