Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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.
Institute of Logic and Computation, TU Wien Favoritenstraße 9-11, 1040 Wien, Austria.
2024 (engelsk)Inngår i: ACM Transactions on Database Systems, ISSN 0362-5915, E-ISSN 1557-4644, Vol. 49, nr 1, artikkel-id 1Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
ACM Digital Library, 2024. Vol. 49, nr 1, artikkel-id 1
Emneord [en]
CCS Concepts, Information systems, Relational database query languages, Mathematics of computing, Hypergraphs, Computing methodologies, Parallel algorithms
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-223094DOI: 10.1145/3638758Scopus ID: 2-s2.0-85189106116OAI: oai:DiVA.org:umu-223094DiVA, id: diva2:1850455
Tilgjengelig fra: 2024-04-10 Laget: 2024-04-10 Sist oppdatert: 2024-04-10bibliografisk kontrollert

Open Access i DiVA

fulltext(1142 kB)361 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 1142 kBChecksum SHA-512
91dca06556d66fa7c1c606bf5102f0c8b696cdf6e5d1a9b6f963390d4adac998b7c17c7886ee63e56ff74b33f28d9256449a3fc8e950ddebc5bcfeb9ffb78bf3
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstScopus

Person

Okulmus, Cem

Søk i DiVA

Av forfatter/redaktør
Okulmus, Cem
Av organisasjonen
I samme tidsskrift
ACM Transactions on Database Systems

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 361 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 533 treff
RefereraExporteraLink to record
Permanent link

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