Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m(vertical bar X vertical bar+1) n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.
Verfasserangaben: | Thomas BläsiusORCiDGND, Tobias FriedrichORCiDGND, Julius Lischeid, Kitty MeeksORCiDGND, Friedrich Martin SchirneckORCiDGND |
---|---|
DOI: | https://doi.org/10.1016/j.jcss.2021.10.002 |
ISSN: | 0022-0000 |
ISSN: | 1090-2724 |
Titel des übergeordneten Werks (Englisch): | Journal of computer and system sciences : JCSS |
Verlag: | Elsevier |
Verlagsort: | San Diego |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 29.10.2022 |
Erscheinungsjahr: | 2022 |
Datum der Freischaltung: | 25.04.2024 |
Freies Schlagwort / Tag: | Data profiling; Enumeration algorithm; Minimal hitting set; Transversal hypergraph; Unique column combination; W[3]-Completeness |
Band: | 124 |
Seitenanzahl: | 22 |
Erste Seite: | 192 |
Letzte Seite: | 213 |
Fördernde Institution: | Royal Society of Edinburgh - Scottish Government |
Organisationseinheiten: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Peer Review: | Referiert |