@article{BlaesiusFriedrichLischeidetal.2022,
  author    = {Bl{\"a}sius, Thomas and Friedrich, Tobias and Lischeid, Julius and Meeks, Kitty and Schirneck, Friedrich Martin},
  title     = {Efficiently enumerating hitting sets of hypergraphs arising in data profiling},
  series = {Journal of computer and system sciences : JCSS},
  volume    = {124},
  journal   = {Journal of computer and system sciences : JCSS},
  publisher = {Elsevier},
  address   = {San Diego},
  issn      = {0022-0000},
  doi       = {10.1016/j.jcss.2021.10.002},
  pages     = {192 -- 213},
  year      = {2022},
  abstract  = {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.},
  language  = {en}
}
@article{BlaesiusFreibergerFriedrichetal.2022,
  author    = {Bl{\"a}sius, Thomas and Freiberger, Cedric and Friedrich, Tobias and Katzmann, Maximilian and Montenegro-Retana, Felix and Thieffry, Marianne},
  title     = {Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry},
  series = {ACM Transactions on Algorithms},
  volume    = {18},
  journal   = {ACM Transactions on Algorithms},
  number    = {2},
  publisher = {Association for Computing Machinery},
  address   = {New York},
  issn      = {1549-6325},
  doi       = {10.1145/3516483},
  pages     = {1 -- 32},
  year      = {2022},
  abstract  = {A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. <br /> To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is (O) over tilde (n(2-1/alpha) + n(1/(2 alpha)) + delta(max)) with high probability, where alpha is an element of (1/2, 1) controls the power-law exponent of the degree distribution, and dmax is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.},
  language  = {en}
}
@article{BirnickBlaesiusFriedrichetal.2020,
  author    = {Birnick, Johann and Bl{\"a}sius, Thomas and Friedrich, Tobias and Naumann, Felix and Papenbrock, Thorsten and Schirneck, Friedrich Martin},
  title     = {Hitting set enumeration with partial information for unique column combination discovery},
  series = {Proceedings of the VLDB Endowment},
  volume    = {13},
  journal   = {Proceedings of the VLDB Endowment},
  number    = {11},
  publisher = {Association for Computing Machinery},
  address   = {[New York, NY]},
  issn      = {2150-8097},
  doi       = {10.14778/3407790.3407824},
  pages     = {2270 -- 2283},
  year      = {2020},
  abstract  = {Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. <br /> In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.},
  language  = {en}
}