Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fast parallel hypertree decompositions in logarithmic recursion depth
Dipartimento di Matematica e Informatica, University of Calabria, Via P. Bucci-Edificio 30B, Arcavacata di Rende, Italy.
Department of Computer Science, University of Oxford, 7 Parks Road, Oxford, United Kingdom.
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-7742-0439
Institute of Logic and Computation, TU Wien Favoritenstraße 9-11, 1040 Wien, Austria.
2024 (English)In: ACM Transactions on Database Systems, ISSN 0362-5915, E-ISSN 1557-4644, Vol. 49, no 1, article id 1Article in journal (Refereed) Published
Abstract [en]

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 log-k-decomp 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 log-k-decomp outperforms the current state of the art significantly.

Place, publisher, year, edition, pages
ACM Digital Library, 2024. Vol. 49, no 1, article id 1
Keywords [en]
CCS Concepts, Information systems, Relational database query languages, Mathematics of computing, Hypergraphs, Computing methodologies, Parallel algorithms
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-223094DOI: 10.1145/3638758Scopus ID: 2-s2.0-85189106116OAI: oai:DiVA.org:umu-223094DiVA, id: diva2:1850455
Available from: 2024-04-10 Created: 2024-04-10 Last updated: 2024-07-02Bibliographically approved

Open Access in DiVA

fulltext(1142 kB)371 downloads
File information
File name FULLTEXT01.pdfFile size 1142 kBChecksum SHA-512
91dca06556d66fa7c1c606bf5102f0c8b696cdf6e5d1a9b6f963390d4adac998b7c17c7886ee63e56ff74b33f28d9256449a3fc8e950ddebc5bcfeb9ffb78bf3
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Okulmus, Cem

Search in DiVA

By author/editor
Okulmus, Cem
By organisation
Department of Computing Science
In the same journal
ACM Transactions on Database Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 371 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 547 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf