{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T23:28:23Z","timestamp":1771889303612,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T00:00:00Z","timestamp":1625788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P30930-N35;W1255-N23"],"award-info":[{"award-number":["P30930-N35;W1255-N23"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"publisher","award":["RP\\R1\\201074"],"award-info":[{"award-number":["RP\\R1\\201074"]}],"id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>To cope with the intractability of answering Conjunctive Queries (CQs) and solving Constraint Satisfaction Problems (CSPs), several notions of hypergraph decompositions have been proposed\u2014giving rise to different notions of width, noticeably, plain, generalized, and fractional hypertree width (hw, ghw, and fhw). Given the increasing interest in using such decomposition methods in practice, a publicly accessible repository of decomposition software, as well as a large set of benchmarks, and a web-accessible workbench for inserting, analyzing, and retrieving hypergraphs are called for.<\/jats:p>\n          <jats:p>We address this need by providing (i) concrete implementations of hypergraph decompositions (including new practical algorithms), (ii) a new, comprehensive benchmark of hypergraphs stemming from disparate CQ and CSP collections, and (iii) HyperBench, our new web-interface for accessing the benchmark and the results of our analyses. In addition, we describe a number of actual experiments we carried out with this new infrastructure.<\/jats:p>","DOI":"10.1145\/3440015","type":"journal-article","created":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T15:06:22Z","timestamp":1625843182000},"page":"1-40","source":"Crossref","is-referenced-by-count":9,"title":["HyperBench"],"prefix":"10.1145","volume":"26","author":[{"given":"Wolfgang","family":"Fischl","sequence":"first","affiliation":[{"name":"TU Wien"}]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[{"name":"University of Oxford"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4018-4994","authenticated-orcid":false,"given":"Davide Mario","family":"Longo","sequence":"additional","affiliation":[{"name":"TU Wien"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien"}]}],"member":"320","published-online":{"date-parts":[[2021,7,9]]},"reference":[{"key":"e_1_2_1_1_1","article-title":"EmptyHeaded: A relational engine for graph processing","volume":"42","author":"Aberger Christopher R.","year":"2017","unstructured":"Christopher R. Aberger , Andrew Lamb , Susan Tu , Andres N\u00f6tzli , Kunle Olukotun , and Christopher R\u00e9 . 2017 . EmptyHeaded: A relational engine for graph processing . ACM Trans. Datab. Syst. 42 , 4 (2017), 20:1\u201320:44. DOI: DOI:https:\/\/doi.org\/10.1145\/3129246. 10.1145\/3129246 Christopher R. Aberger, Andrew Lamb, Susan Tu, Andres N\u00f6tzli, Kunle Olukotun, and Christopher R\u00e9. 2017. EmptyHeaded: A relational engine for graph processing. ACM Trans. Datab. Syst. 42, 4 (2017), 20:1\u201320:44. DOI: DOI:https:\/\/doi.org\/10.1145\/3129246.","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_2_1_2_1","volume-title":"Old techniques for new join algorithms: A case study in RDF processing. CoRR abs\/1602.03557","author":"Aberger Christopher R.","year":"2016","unstructured":"Christopher R. Aberger , Susan Tu , Kunle Olukotun , and Christopher R\u00e9. 2016. Old techniques for new join algorithms: A case study in RDF processing. CoRR abs\/1602.03557 ( 2016 ). Christopher R. Aberger, Susan Tu, Kunle Olukotun, and Christopher R\u00e9. 2016. Old techniques for new join algorithms: A case study in RDF processing. CoRR abs\/1602.03557 (2016)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-150694"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850586"},{"key":"e_1_2_1_7_1","unstructured":"Gilles Audemard Fr\u00e9d\u00e9ric Boussemart Christophe Lecoutre and C\u00e9dric Piette. 2016. XCSP3: an XML-based format designed to represent combinatorial constrained problems. Retrieved from http:\/\/www.xcsp.org\/.  Gilles Audemard Fr\u00e9d\u00e9ric Boussemart Christophe Lecoutre and C\u00e9dric Piette. 2016. XCSP3: an XML-based format designed to represent combinatorial constrained problems. Retrieved from http:\/\/www.xcsp.org\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_9_1","unstructured":"Michael Benedikt. 2017. CQ benchmarks. Personal Communication.  Michael Benedikt. 2017. CQ benchmarks. Personal Communication."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034796"},{"key":"e_1_2_1_11_1","volume-title":"MaxSAT benchmarks based on determining generalized hypertree-width. MaxSAT Evaluation 2017: Solver and Benchmark Descriptions B-2017-2","author":"Berg Jeremias","year":"2017","unstructured":"Jeremias Berg , Neha Lodha , Matti J\u00e4rvisalo , and Stefan Szeider . 2017. MaxSAT benchmarks based on determining generalized hypertree-width. MaxSAT Evaluation 2017: Solver and Benchmark Descriptions B-2017-2 ( 2017 ), 22. Jeremias Berg, Neha Lodha, Matti J\u00e4rvisalo, and Stefan Szeider. 2017. MaxSAT benchmarks based on determining generalized hypertree-width. MaxSAT Evaluation 2017: Solver and Benchmark Descriptions B-2017-2 (2017), 22."},{"key":"e_1_2_1_12_1","first-page":"149","article-title":"An analytical study of large SPARQL query logs","volume":"11","author":"Bonifati Angela","year":"2017","unstructured":"Angela Bonifati , Wim Martens , and Thomas Timm . 2017 . An analytical study of large SPARQL query logs . PVLDB 11 , 2 (2017), 149 \u2013 161 . DOI:https:\/\/doi.org\/10.14778\/3149193.3149196. 10.14778\/3149193.3149196 Angela Bonifati, Wim Martens, and Thomas Timm. 2017. An analytical study of large SPARQL query logs. PVLDB 11, 2 (2017), 149\u2013161. DOI:https:\/\/doi.org\/10.14778\/3149193.3149196.","journal-title":"PVLDB"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056109"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 9th ACM Symposium on Theory of Computing, John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison (Eds.). ACM, 77\u201390","author":"Ashok","unstructured":"Ashok K. Chandra and Philip M. Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases . In Proceedings of the 9th ACM Symposium on Theory of Computing, John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison (Eds.). ACM, 77\u201390 . DOI:https:\/\/doi.org\/10.1145\/800105.803397. 10.1145\/800105.803397 Ashok K. Chandra and Philip M. Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th ACM Symposium on Theory of Computing, John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison (Eds.). ACM, 77\u201390. DOI:https:\/\/doi.org\/10.1145\/800105.803397."},{"key":"e_1_2_1_16_1","volume-title":"Constraint Processing","author":"Dechter Rina","unstructured":"Rina Dechter . 2003. Constraint Processing . Elsevier . DOI:https:\/\/doi.org\/10.1016\/b978-1-55860-890-0.x5000-2. 10.1016\/b978-1-55860-890-0.x5000-2 Rina Dechter. 2003. Constraint Processing. Elsevier. DOI:https:\/\/doi.org\/10.1016\/b978-1-55860-890-0.x5000-2."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98334-9_8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319683"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196962"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816654"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367849"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2064023"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_25_1","volume-title":"Complexity analysis of generalized and fractional hypertree decompositions. CoRR abs\/2002.05239","author":"Gottlob Georg","year":"2020","unstructured":"Georg Gottlob , Matthias Lanzinger , Reinhard Pichler , and Igor Razgon . 2020. Complexity analysis of generalized and fractional hypertree decompositions. CoRR abs\/2002.05239 ( 2020 ). Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. 2020. Complexity analysis of generalized and fractional hypertree decompositions. CoRR abs\/2002.05239 (2020)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48309-8_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/161"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"A backtracking-based algorithm for hypertree decomposition","volume":"13","author":"Gottlob Georg","year":"2008","unstructured":"Georg Gottlob and Marko Samer . 2008 . A backtracking-based algorithm for hypertree decomposition . ACM J. Experim. Algor. 13 (2008), 1: 1 .1\u20131:1.19. DOI:https:\/\/doi.org\/10.1145\/1412228.1412229. 10.1145\/1412228.1412229 Georg Gottlob and Marko Samer. 2008. A backtracking-based algorithm for hypertree decomposition. ACM J. Experim. Algor. 13 (2008), 1:1.1\u20131:1.19. DOI:https:\/\/doi.org\/10.1145\/1412228.1412229.","journal-title":"ACM J. Experim. Algor."},{"key":"e_1_2_1_31_1","article-title":"Constraint solving via fractional edge covers","volume":"11","author":"Grohe Martin","year":"2014","unstructured":"Martin Grohe and D\u00e1niel Marx . 2014 . Constraint solving via fractional edge covers . ACM Trans. Algor. 11 , 1 (2014), 4:1\u20134:20. DOI:https:\/\/doi.org\/10.1145\/2636918. 10.1145\/2636918 Martin Grohe and D\u00e1niel Marx. 2014. Constraint solving via fractional edge covers. ACM Trans. Algor. 11, 1 (2014), 4:1\u20134:20. DOI:https:\/\/doi.org\/10.1145\/2636918.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.06.005"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/0952813X.2014.993507"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159940"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 9th Symposium on Abstraction, Reformulation, and Approximation (SARA\u201911)","author":"Karakashian Shant","unstructured":"Shant Karakashian , Robert J. Woodward , and Berthe Y. Choueiry . 2011. Reformulating R(*, m)C with tree decomposition . In Proceedings of the 9th Symposium on Abstraction, Reformulation, and Approximation (SARA\u201911) , Michael R. Genesereth and Peter Z. Revesz (Eds.). AAAI, 62\u201369. Retrieved from http:\/\/www.aaai.org\/ocs\/index.php\/SARA\/SARA11\/paper\/view\/4234. Shant Karakashian, Robert J. Woodward, and Berthe Y. Choueiry. 2011. Reformulating R(*, m)C with tree decomposition. In Proceedings of the 9th Symposium on Abstraction, Reformulation, and Approximation (SARA\u201911), Michael R. Genesereth and Peter Z. Revesz (Eds.). AAAI, 62\u201369. Retrieved from http:\/\/www.aaai.org\/ocs\/index.php\/SARA\/SARA11\/paper\/view\/4234."},{"key":"e_1_2_1_36_1","article-title":"Joins via geometric resolutions: Worst case and beyond","volume":"41","author":"Khamis Mahmoud Abo","year":"2016","unstructured":"Mahmoud Abo Khamis , Hung Q. Ngo , Christopher R\u00e9 , and Atri Rudra . 2016 . Joins via geometric resolutions: Worst case and beyond . ACM Trans. Datab. Syst. 41 , 4 (2016), 22:1\u201322:45. DOI:https:\/\/doi.org\/10.1145\/2967101. 10.1145\/2967101 Mahmoud Abo Khamis, Hung Q. Ngo, Christopher R\u00e9, and Atri Rudra. 2016. Joins via geometric resolutions: Worst case and beyond. ACM Trans. Datab. Syst. 41, 4 (2016), 22:1\u201322:45. DOI:https:\/\/doi.org\/10.1145\/2967101.","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_38_1","unstructured":"Tuukka Korhonen. 2019. Potential Maximal Cliques Parameterized by Edge Clique Cover. arxiv:1912.10989 [cs.DS].  Tuukka Korhonen. 2019. Potential Maximal Cliques Parameterized by Edge Clique Cover. arxiv:1912.10989 [cs.DS]."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 16th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA@AI*IA\u201909)(CEUR Workshop Proceedings","volume":"11","author":"Lalou Mohammed","year":"2009","unstructured":"Mohammed Lalou , Zineb Habbas , and Kamal Amroun . 2009 . Solving hypertree structured CSP: Sequential and parallel approaches . In Proceedings of the 16th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA@AI*IA\u201909)(CEUR Workshop Proceedings , Vol. 589), Marco Gavanelli and Toni Mancini (Eds.). CEUR-WS.org. Retrieved from http:\/\/ceur-ws.org\/Vol-589\/paper 11 .pdf. Mohammed Lalou, Zineb Habbas, and Kamal Amroun. 2009. Solving hypertree structured CSP: Sequential and parallel approaches. In Proceedings of the 16th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA@AI*IA\u201909)(CEUR Workshop Proceedings, Vol. 589), Marco Gavanelli and Toni Mancini (Eds.). CEUR-WS.org. Retrieved from http:\/\/ceur-ws.org\/Vol-589\/paper11.pdf."},{"key":"e_1_2_1_40_1","volume-title":"How good are query optimizers, really?PVLDB 9, 3","author":"Leis Viktor","year":"2015","unstructured":"Viktor Leis , Andrey Gubichev , Atanas Mirchev , Peter A. Boncz , Alfons Kemper , and Thomas Neumann . 2015. How good are query optimizers, really?PVLDB 9, 3 ( 2015 ), 204\u2013215. DOI:https:\/\/doi.org\/10.14778\/2850583.2850594. 10.14778\/2850583.2850594 Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter A. Boncz, Alfons Kemper, and Thomas Neumann. 2015. How good are query optimizers, really?PVLDB 9, 3 (2015), 204\u2013215. DOI:https:\/\/doi.org\/10.14778\/2850583.2850594."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00668-6_23"},{"key":"e_1_2_1_43_1","article-title":"Approximating fractional hypertree width","volume":"6","author":"Marx D\u00e1niel","year":"2010","unstructured":"D\u00e1niel Marx . 2010 . Approximating fractional hypertree width . ACM Trans. Algor. 6 , 2 (2010), 29:1\u201329:17. DOI:https:\/\/doi.org\/10.1145\/1721837.1721845. 10.1145\/1721837.1721845 D\u00e1niel Marx. 2010. Approximating fractional hypertree width. ACM Trans. Algor. 6, 2 (2010), 29:1\u201329:17. DOI:https:\/\/doi.org\/10.1145\/1721837.1721845.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381449"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.002"},{"key":"e_1_2_1_46_1","article-title":"Size bounds for factorised representations of query results","volume":"40","author":"Olteanu Dan","year":"2015","unstructured":"Dan Olteanu and Jakub Z\u00e1vodn\u00fd . 2015 . Size bounds for factorised representations of query results . ACM Trans. Datab. Syst. 40 , 1 (2015), 2:1\u20132:44. DOI:https:\/\/doi.org\/10.1145\/2656335. 10.1145\/2656335 Dan Olteanu and Jakub Z\u00e1vodn\u00fd. 2015. Size bounds for factorised representations of query results. ACM Trans. Datab. Syst. 40, 1 (2015), 2:1\u20132:44. DOI:https:\/\/doi.org\/10.1145\/2656335.","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2764945"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1999299.1999306"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767146"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1223810.1223867"},{"key":"e_1_2_1_51_1","unstructured":"Werner Schafhauser. 2006. New heuristic methods for tree decompositions and generalized hypertree decompositions. Master\u2019s thesis. Technische Universit\u00e4t Wien.  Werner Schafhauser. 2006. New heuristic methods for tree decompositions and generalized hypertree decompositions. Master\u2019s thesis. Technische Universit\u00e4t Wien."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.1"},{"key":"e_1_2_1_53_1","unstructured":"Transaction Processing Performance Council (TPC). 2006. TPC-DS decision support benchmark. Retrieved from http:\/\/www.tpc.org\/tpcds\/.  Transaction Processing Performance Council (TPC). 2006. TPC-DS decision support benchmark. Retrieved from http:\/\/www.tpc.org\/tpcds\/."},{"key":"e_1_2_1_54_1","unstructured":"Transaction Processing Performance Council (TPC). 2014. TPC-H decision support benchmark. Retrieved from http:\/\/www.tpc.org\/tpch\/default.asp.  Transaction Processing Performance Council (TPC). 2014. TPC-H decision support benchmark. Retrieved from http:\/\/www.tpc.org\/tpch\/default.asp."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2764946"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_57_1","unstructured":"Tobias Warneke. 2019. JSqlParser. Retrieved from https:\/\/github.com\/JSQLParser\/JSqlParser.  Tobias Warneke. 2019. JSqlParser. Retrieved from https:\/\/github.com\/JSQLParser\/JSqlParser."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3440015","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3440015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:17Z","timestamp":1750197737000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3440015"}},"subtitle":["A Benchmark and Tool for Hypergraphs and Empirical Findings"],"short-title":[],"issued":{"date-parts":[[2021,7,9]]},"references-count":56,"alternative-id":["10.1145\/3440015"],"URL":"https:\/\/doi.org\/10.1145\/3440015","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,9]]}}}