@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.
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} } @article{BlaesiusFriedrichSchirneck2021, author = {Blaesius, Thomas and Friedrich, Tobias and Schirneck, Friedrich Martin}, title = {The complexity of dependency detection and discovery in relational databases}, series = {Theoretical computer science}, volume = {900}, journal = {Theoretical computer science}, publisher = {Elsevier}, address = {Amsterdam}, issn = {0304-3975}, doi = {10.1016/j.tcs.2021.11.020}, pages = {79 -- 96}, year = {2021}, abstract = {Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.}, language = {en} } @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} } @misc{BlaesiusEubeFeldtkelleretal.2018, author = {Blaesius, Thomas and Eube, Jan and Feldtkeller, Thomas and Friedrich, Tobias and Krejca, Martin Stefan and Lagodzinski, Gregor J. A. and Rothenberger, Ralf and Severin, Julius and Sommer, Fabian and Trautmann, Justin}, title = {Memory-restricted Routing With Tiled Map Data}, series = {2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)}, journal = {2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)}, publisher = {IEEE}, address = {New York}, isbn = {978-1-5386-6650-0}, issn = {1062-922X}, doi = {10.1109/SMC.2018.00567}, pages = {3347 -- 3354}, year = {2018}, abstract = {Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.}, language = {en} } @misc{GuentherMangelsdorfMitzneretal.2012, author = {G{\"u}nther, Oliver and Mangelsdorf, Birgit and Mitzner, Rolf and Loschelder, Wolfgang and Peter, Andreas and Eckert, Barbara and Mikelskis, Helmut and Klein, Alfred and Kirsch, B{\"a}rbel and Edelstein, Wolfgang and Thomas, Gr{\"u}newald and Thomas, P{\"o}sl and Wagner, Dieter and Winskowski, Friedrich and Schad, Martina and Frey, Anne and Bickenbach, Wulf and Madani, Roya and Olaka, Lydia}, title = {Portal alumni}, series = {Das Ehemaligen-Magazin der Universit{\"a}t Potsdam}, journal = {Das Ehemaligen-Magazin der Universit{\"a}t Potsdam}, number = {9}, organization = {Stabsstelle Studierendenmarketing/Alumniprogramm Im Auftrag der Pr{\"a}sidentin der Universit{\"a}t Potsdam}, issn = {1613-2343}, doi = {10.25932/publishup-44494}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-444943}, pages = {60}, year = {2012}, abstract = {Das zur{\"u}ckliegende Jahr stand an der Universit{\"a}t Potsdam auch im Zeichen des zwanzigj{\"a}hrigen Jubil{\"a}ums der Hochschule. Am 15. Juli 1991, wurde sie gegr{\"u}ndet und w{\"a}hrend einer Festwoche feierten Professorinnen und Professoren, Mitarbeiterinnen, Mitarbeiter und Studierende dieses Jubil{\"a}um geb{\"u}hrend. Seit der Gr{\"u}ndung der gr{\"o}ßten brandenburgischen Hochschule sind wissenschaftliches Renommee, Ansehen und Attraktivit{\"a}t stetig gewachsen. Gerade in den letzten Jahren hat sie ihr Profil gesch{\"a}rft. Vor allem die Kognitions-, die Geo- und Biowissenschaften sind hier zu nennen. Aber auch die Lehrerbildung besitzt einen hohen Stellenwert. International anerkannte Forschungsbereiche, Wissenschaftspreise, eine erfolgreiche Drittmittelbilanz und nicht zuletzt die bauliche Entwicklung an allen drei Standorten sind sichtbare Indikatoren f{\"u}r die erfolgreiche Entwicklung, die die Universit{\"a}t Potsdam in den letzten zwei Jahrzehnten durchlaufen hat. Die drei ehemaligen Pr{\"a}sidenten sowie verschiedene andere Protagonisten werfen in dieser Ausgabe der Portal Alumni einen Blick auf unterschiedliche Aspekte der zur{\"u}ckliegenden Entwicklung der Universit{\"a}t. Vom Erfolg der Universit{\"a}t zeugt auch die wachsende Zahl der Absolventinnen und Absolventen, die die Universit{\"a}t verlassen. Portal Alumni stellt in der vorliegenden Ausgabe deshalb Absolventen und deren universit{\"a}re und berufliche Lebenswege genauer vor und l{\"a}sst damit zugleich kaleidoskopartig 20 Jahre Studium an der Universit{\"a}t Potsdam Revue passieren.}, language = {de} } @article{VorburgerNedielkovBrosigetal.2016, author = {Vorburger, Thomas and Nedielkov, Ruslan and Brosig, Alexander and Bok, Eva and Schunke, Emina and Steffen, Wojtek and Mayer, Sonja and Goetz, Friedrich and M{\"o}ller, Heiko Michael and Steuber, Julia}, title = {Role of the Na+-translocating NADH:quinone oxidoreductase in voltage generation and Na+ extrusion in Vibrio cholerae}, series = {Biochimica et biophysica acta : Bioenergetics}, volume = {1857}, journal = {Biochimica et biophysica acta : Bioenergetics}, publisher = {Elsevier}, address = {Amsterdam}, issn = {0005-2728}, doi = {10.1016/j.bbabio.2015.12.010}, pages = {473 -- 482}, year = {2016}, abstract = {For Vibrio cholerae, the coordinated import and export of Na+ is crucial for adaptation to habitats with different osmolarities. We investigated the Na+-extruding branch of the sodium cycle in this human pathogen by in vivo Na-23-NMR spectroscopy. The Na+ extrusion activity of cells was monitored after adding glucose which stimulated respiration via the Na+-translocating NADH:quinone oxidoreductase (Na+-NQR). In a V. cholerae deletion mutant devoid of the Na+-NQR encoding genes (nqrA-F), rates of respiratory Na+ extrusion were decreased by a factor of four, but the cytoplasmic Na+ concentration was essentially unchanged. Furthermore, the mutant was impaired in formation of transmembrane voltage (Delta psi, inside negative) and did not grow under hypoosmotic conditions at pH 8.2 or above. This growth defect could be complemented by transformation with the plasmid encoded nqr operon. In an alkaline environment, Na+/H+ antiporters acidify the cytoplasm at the expense of the transmembrane voltage. It is proposed that, at alkaline pH and limiting Na+ concentrations, the Na+-NQR is crucial for generation of a transmembrane voltage to drive the import of H+ by electrogenic Na+/H+ antiporters. Our study provides the basis to understand the role of the Na+-NQR in pathogenicity of V. cholerae and other pathogens relying on this primary Na+ pump for respiration. (C) 2015 Elsevier B.V. All rights reserved.}, language = {en} } @article{FriedrichKrejcaRothenbergeretal.2019, author = {Friedrich, Tobias and Krejca, Martin Stefan and Rothenberger, Ralf and Arndt, Tobias and Hafner, Danijar and Kellermeier, Thomas and Krogmann, Simon and Razmjou, Armin}, title = {Routing for on-street parking search using probabilistic data}, series = {AI communications : AICOM ; the European journal on artificial intelligence}, volume = {32}, journal = {AI communications : AICOM ; the European journal on artificial intelligence}, number = {2}, publisher = {IOS Press}, address = {Amsterdam}, issn = {0921-7126}, doi = {10.3233/AIC-180574}, pages = {113 -- 124}, year = {2019}, abstract = {A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers.}, language = {en} } @article{PrasseRistowKlemmetal.2001, author = {Prasse, R{\"u}diger and Ristow, Michael and Klemm, Gunther and Machatzi, Bernd and Raus, Thomas and Scholz, Hildemar and Stohr, Gerrit and Sukopp, Herbert and Zimmermann, Friedrich}, title = {Liste der wildwachsenden Gef{\"a}ßpflanzen des Landes Berlin : mit Roter Liste}, publisher = {Kulturbuch-Verl.}, address = {Berlin}, isbn = {3-88961-137-0}, pages = {85 S.}, year = {2001}, language = {de} } @article{CastellanosFriedrichPetrovicetal.2020, author = {Castellanos, Reynel Urrea and Friedrich, Thomas and Petrovic, Nevena and Altmann, Simone and Brzezinka, Krzysztof and Gorka, Michal and Graf, Alexander and B{\"a}urle, Isabel}, title = {FORGETTER2 protein phosphatase and phospholipase D modulate heat stress memory in Arabidopsis}, series = {The plant journal}, volume = {104}, journal = {The plant journal}, number = {1}, publisher = {Wiley}, address = {Hoboken}, issn = {0960-7412}, doi = {10.1111/tpj.14927}, pages = {7 -- 17}, year = {2020}, abstract = {Plants can mitigate environmental stress conditions through acclimation. In the case of fluctuating stress conditions such as high temperatures, maintaining a stress memory enables a more efficient response upon recurring stress. In a genetic screen forArabidopsis thalianamutants impaired in the memory of heat stress (HS) we have isolated theFORGETTER2(FGT2) gene, which encodes a type 2C protein phosphatase (PP2C) of the D-clade.Fgt2mutants acquire thermotolerance normally; however, they are defective in the memory of HS. FGT2 interacts with phospholipase D alpha 2 (PLD alpha 2), which is involved in the metabolism of membrane phospholipids and is also required for HS memory. In summary, we have uncovered a previously unknown component of HS memory and identified the FGT2 protein phosphatase and PLD alpha 2 as crucial players, suggesting that phosphatidic acid-dependent signaling or membrane composition dynamics underlie HS memory.}, language = {en} } @article{KabelitzBrzezinkaFriedrichetal.2016, author = {Kabelitz, Tina and Brzezinka, Krzysztof and Friedrich, Thomas and Gorka, Michal and Graf, Alexander and Kappel, Christian and B{\"a}urle, Isabel}, title = {A JUMONJI Protein with E3 Ligase and Histone H3 Binding Activities Affects Transposon Silencing in Arabidopsis}, series = {Plant physiology : an international journal devoted to physiology, biochemistry, cellular and molecular biology, biophysics and environmental biology of plants}, volume = {171}, journal = {Plant physiology : an international journal devoted to physiology, biochemistry, cellular and molecular biology, biophysics and environmental biology of plants}, publisher = {American Society of Plant Physiologists}, address = {Rockville}, issn = {0032-0889}, doi = {10.1104/pp.15.01688}, pages = {344 -- 358}, year = {2016}, abstract = {Transposable elements (TEs) make up a large proportion of eukaryotic genomes. As their mobilization creates genetic variation that threatens genome integrity, TEs are epigenetically silenced through several pathways, and this may spread to neighboring sequences. JUMONJI (JMJ) proteins can function as antisilencing factors and prevent silencing of genes next to TEs. Whether TE silencing is counterbalanced by the activity of antisilencing factors is still unclear. Here, we characterize JMJ24 as a regulator of TE silencing. We show that loss of JMJ24 results in increased silencing of the DNA transposon AtMu1c, while overexpression of JMJ24 reduces silencing. JMJ24 has a JumonjiC (JmjC) domain and two RING domains. JMJ24 autoubiquitinates in vitro, demonstrating E3 ligase activity of the RING domain(s). JMJ24-JmjC binds the N-terminal tail of histone H3, and full-length JMJ24 binds histone H3 in vivo. JMJ24 activity is anticorrelated with histone H3 Lys 9 dimethylation (H3K9me2) levels at AtMu1c. Double mutant analyses with epigenetic silencing mutants suggest that JMJ24 antagonizes histone H3K9me2 and requires H3K9 methyltransferases for its activity on AtMu1c. Genome-wide transcriptome analysis indicates that JMJ24 affects silencing at additional TEs. Our results suggest that the JmjC domain of JMJ24 has lost demethylase activity but has been retained as a binding domain for histone H3. This is in line with phylogenetic analyses indicating that JMJ24 (with the mutated JmjC domain) is widely conserved in angiosperms. Taken together, this study assigns a role in TE silencing to a conserved JmjC-domain protein with E3 ligase activity, but no demethylase activity.}, language = {en} }