{"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":1771889303729,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,2,28]],"date-time":"2024-02-28T00:00:00Z","timestamp":1709078400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["P30930-N35"],"award-info":[{"award-number":["P30930-N35"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["10.47379\/VRG18013, 10.47379\/NXT22018, 10.47379\/ICT2201"],"award-info":[{"award-number":["10.47379\/VRG18013, 10.47379\/NXT22018, 10.47379\/ICT2201"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Christian Doppler Research Association (CDG) JRC LIVE"},{"name":"Royal Society for the present work in the context of the project \u201cRAISON DATA\u201d","award":["RP\\R1\\201074"],"award-info":[{"award-number":["RP\\R1\\201074"]}]},{"name":"Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>\n            Various classic reasoning problems with natural hypergraph representations are known to be tractable if a hypertree decomposition (HD) of low width exists. The resulting algorithms are attractive for practical use in fields like databases and constraint satisfaction. However, algorithmic use of HDs relies on the difficult task of first computing a decomposition of the hypergraph underlying a given problem instance, which is then used to guide the algorithm for this particular instance. The performance of purely sequential methods for computing HDs is inherently limited, yet the problem is, theoretically, amenable to parallelisation. In this article, we propose the first algorithm for computing hypertree decompositions that is well suited for parallelisation. The newly proposed algorithm\n            <jats:monospace>\n              log-\n              <jats:italic>k<\/jats:italic>\n              -decomp\n            <\/jats:monospace>\n            requires only a logarithmic number of recursion levels and additionally allows for highly parallelised pruning of the search space by restriction to so-called balanced separators. We provide a detailed experimental evaluation over the HyperBench benchmark and demonstrate that\n            <jats:monospace>\n              log-\n              <jats:italic>k<\/jats:italic>\n              -decomp\n            <\/jats:monospace>\n            outperforms the current state of the art significantly.\n          <\/jats:p>","DOI":"10.1145\/3638758","type":"journal-article","created":{"date-parts":[[2023,12,30]],"date-time":"2023-12-30T15:57:44Z","timestamp":1703951864000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2353-5230","authenticated-orcid":false,"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"University of Calabria, Rende, Italy and University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7601-3727","authenticated-orcid":false,"given":"Matthias","family":"Lanzinger","sequence":"additional","affiliation":[{"name":"TU Wien, Wien, Austria and University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7742-0439","authenticated-orcid":false,"given":"Cem","family":"Okulmus","sequence":"additional","affiliation":[{"name":"Ume\u00e5 University, Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1760-122X","authenticated-orcid":false,"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,2,28]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2017.4"},{"key":"e_1_3_3_5_2","volume-title":"Exploiting Parallelism in Decomposition Methods for Constraint Satisfaction","author":"Akatov Dmitri","year":"2010","unstructured":"Dmitri Akatov. 2010. Exploiting Parallelism in Decomposition Methods for Constraint Satisfaction. Ph.D. Dissertation. University of Oxford, UK."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-50728-0_32"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289859"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.4"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.4"},{"key":"e_1_3_3_10_2","first-page":"25:1\u201325:23","volume-title":"Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC\u201919)","author":"Dzulfikar M. Ayaz","year":"2019","unstructured":"M. Ayaz Dzulfikar, Johannes Klaus Fichte, and Markus Hecher. 2019. The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper). In Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC\u201919). 25:1\u201325:23."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98334-9_8"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3440015"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367849"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2064023"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505987"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1683"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524153"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","unstructured":"Georg Gottlob Matthias Lanzinger Cem Okulmus and Reinhard Pichler. 2023. Experimental data for log-k-decomp. Zenodo. 10.5281\/zenodo.7180787","DOI":"10.5281\/zenodo.7180787"},{"key":"e_1_3_3_20_2","series-title":"Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920),","first-page":"41:1\u201341:14","volume":"170","author":"Gottlob Georg","year":"2020","unstructured":"Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. 2020. Fractional covers of hypergraphs with bounded multi-intersection. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920),LIPIcs, Vol. 170. Schloss Dagstuhl, 41:1\u201341:14."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3457374"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00108-6"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-022-09332-1"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412229"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89536"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90036-7"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/196"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/1064323.1064336"},{"key":"e_1_3_3_34_2","first-page":"82","volume-title":"Proceedings of the 7th International Conference on Very Large Databases (VLDB\u201981)","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Databases (VLDB\u201981). VLDB, 82\u201394."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3638758","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3638758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:33Z","timestamp":1750291413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3638758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,28]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3638758"],"URL":"https:\/\/doi.org\/10.1145\/3638758","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,28]]},"assertion":[{"value":"2022-10-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}