Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • 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å universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-7742-0439
Institute of Logic and Computation, TU Wien Favoritenstraße 9-11, 1040 Wien, Austria.
2024 (Engelska)Ingår i: ACM Transactions on Database Systems, ISSN 0362-5915, E-ISSN 1557-4644, Vol. 49, nr 1, artikel-id 1Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
ACM Digital Library, 2024. Vol. 49, nr 1, artikel-id 1
Nyckelord [en]
CCS Concepts, Information systems, Relational database query languages, Mathematics of computing, Hypergraphs, Computing methodologies, Parallel algorithms
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-223094DOI: 10.1145/3638758Scopus ID: 2-s2.0-85189106116OAI: oai:DiVA.org:umu-223094DiVA, id: diva2:1850455
Tillgänglig från: 2024-04-10 Skapad: 2024-04-10 Senast uppdaterad: 2024-07-02Bibliografiskt granskad

Open Access i DiVA

fulltext(1142 kB)371 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1142 kBChecksumma SHA-512
91dca06556d66fa7c1c606bf5102f0c8b696cdf6e5d1a9b6f963390d4adac998b7c17c7886ee63e56ff74b33f28d9256449a3fc8e950ddebc5bcfeb9ffb78bf3
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Okulmus, Cem

Sök vidare i DiVA

Av författaren/redaktören
Okulmus, Cem
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
ACM Transactions on Database Systems
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 371 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 547 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf