Julius Lischeid

dblp:235/6820 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
1since 2021 · last 2022
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 since 2021
YearPublicationVenuePosition
2022 Efficiently enumerating hitting sets of hypergraphs arising in data profiling
Thomas Bläsius, Tobias Friedrich 0001, Julius Lischeid, Kitty Meeks, Martin Schirneck
J. Comput. Syst. Sci.3
2019 Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
abstract
We devise an enumeration method for inclusion-wise minimal hitting sets in hypergraphs. It has delay O(mk* +1 · n2) and uses linear space. Hereby, n is the number of vertices, m the number of hyperedges, and k* the rank of the transversal hypergraph. In particular, on classes of hypergraphs for which the cardinality k* of the largest minimal hitting set is bounded, the delay is polynomial. The algorithm solves the extension problem for minimal hitting sets as a subroutine. We show that the extension problem is W[3]-complete when parameterised by the cardinality of the set which is to be extended. For the subroutine, we give an algorithm that is optimal under the exponential time hypothesis. Despite these lower bounds, we provide empirical evidence showing that the enumeration outperforms the theoretical worst-case guarantee on hypergraphs arising in the profiling of relational databases, namely, in the detection of unique column combinations.
Thomas Bläsius, Tobias Friedrich 0001, Julius Lischeid, Kitty Meeks, Martin Schirneck
ALENEX3