TY  - JOUR
A1  - Birnick, Johann
A1  - Bläsius, Thomas
A1  - Friedrich, Tobias
A1  - Naumann, Felix
A1  - Papenbrock, Thorsten
A1  - Schirneck, Friedrich Martin
T1  - Hitting set enumeration with partial information for unique column combination discovery
JF  - Proceedings of the VLDB Endowment
N2  - 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.
Y1  - 2020
U6  - https://doi.org/10.14778/3407790.3407824
SN  - 2150-8097
VL  - 13
IS  - 11
SP  - 2270
EP  - 2283
PB  - Association for Computing Machinery
CY  - [New York, NY]
ER  - 
TY  - JOUR
A1  - Blaesius, Thomas
A1  - Friedrich, Tobias
A1  - Schirneck, Friedrich Martin
T1  - The complexity of dependency detection and discovery in relational databases
JF  - Theoretical computer science
N2  - 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.
KW  - data profiling
KW  - enumeration complexity
KW  - functional dependency
KW  - inclusion
KW  - dependency
KW  - parameterized complexity
KW  - parsimonious reduction
KW  - transversal hypergraph
KW  - Unique column combination
KW  - W[3]-completeness
Y1  - 2021
U6  - https://doi.org/10.1016/j.tcs.2021.11.020
SN  - 0304-3975
SN  - 1879-2294
VL  - 900
SP  - 79
EP  - 96
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Bläsius, Thomas
A1  - Friedrich, Tobias
A1  - Lischeid, Julius
A1  - Meeks, Kitty
A1  - Schirneck, Friedrich Martin
T1  - Efficiently enumerating hitting sets of hypergraphs arising in data profiling
JF  - Journal of computer and system sciences : JCSS
N2  - 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.
KW  - Data profiling
KW  - Enumeration algorithm
KW  - Minimal hitting set
KW  - Transversal hypergraph
KW  - Unique column combination
KW  - W[3]-Completeness
Y1  - 2022
U6  - https://doi.org/10.1016/j.jcss.2021.10.002
SN  - 0022-0000
SN  - 1090-2724
VL  - 124
SP  - 192
EP  - 213
PB  - Elsevier
CY  - San Diego
ER  - 
TY  - GEN
A1  - Blaesius, Thomas
A1  - Eube, Jan
A1  - Feldtkeller, Thomas
A1  - Friedrich, Tobias
A1  - Krejca, Martin Stefan
A1  - Lagodzinski, Gregor J. A.
A1  - Rothenberger, Ralf
A1  - Severin, Julius
A1  - Sommer, Fabian
A1  - Trautmann, Justin
T1  - Memory-restricted Routing With Tiled Map Data
T2  - 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)
N2  - 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*.
Y1  - 2018
SN  - 978-1-5386-6650-0
U6  - https://doi.org/10.1109/SMC.2018.00567
SN  - 1062-922X
SP  - 3347
EP  - 3354
PB  - IEEE
CY  - New York
ER  - 
TY  - JOUR
A1  - Günther, Oliver
A1  - Mangelsdorf, Birgit
A1  - Mitzner, Rolf
A1  - Loschelder, Wolfgang
A1  - Peter, Andreas
A1  - Eckert, Barbara
A1  - Mikelskis, Helmut
A1  - Klein, Alfred
A1  - Kirsch, Bärbel
A1  - Edelstein, Wolfgang
A1  - Thomas, Grünewald
A1  - Thomas, Pösl
A1  - Wagner, Dieter
A1  - Winskowski, Friedrich
A1  - Schad, Martina
A1  - Frey, Anne
A1  - Bickenbach, Wulf
A1  - Madani, Roya
A1  - Olaka, Lydia
T1  - Portal alumni
T2  - Das Ehemaligen-Magazin der Universität Potsdam
N2  - Das zurückliegende Jahr stand an der Universität Potsdam auch im Zeichen des zwanzigjährigen Jubiläums der Hochschule. Am 15. Juli 1991, wurde sie gegründet und während einer Festwoche feierten Professorinnen und Professoren, Mitarbeiterinnen, Mitarbeiter und Studierende dieses Jubiläum gebührend. Seit der Gründung der größten brandenburgischen Hochschule sind wissenschaftliches Renommee, Ansehen und Attraktivität stetig gewachsen. Gerade in den letzten Jahren hat sie ihr Profil geschä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ür die erfolgreiche Entwicklung, die die Universität Potsdam in den letzten zwei Jahrzehnten durchlaufen hat. Die drei ehemaligen Präsidenten sowie verschiedene andere Protagonisten werfen in dieser Ausgabe der Portal Alumni einen Blick auf unterschiedliche Aspekte der zurückliegenden Entwicklung der Universität. Vom Erfolg der Universität zeugt auch die wachsende Zahl der Absolventinnen und Absolventen, die die Universität verlassen. Portal Alumni stellt in der vorliegenden Ausgabe deshalb Absolventen und deren universitäre und berufliche Lebenswege genauer vor und lässt damit zugleich kaleidoskopartig 20 Jahre Studium an der Universität Potsdam Revue passieren.
T3  - Portal alumni : das Ehemaligen-Magazin der Universität Potsdam - 9/2012 
Y1  - 2012
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-444943
SN  - 1613-2343
IS  - 9
ER  - 
TY  - JOUR
A1  - Vorburger, Thomas
A1  - Nedielkov, Ruslan
A1  - Brosig, Alexander
A1  - Bok, Eva
A1  - Schunke, Emina
A1  - Steffen, Wojtek
A1  - Mayer, Sonja
A1  - Goetz, Friedrich
A1  - Möller, Heiko Michael
A1  - Steuber, Julia
T1  - Role of the Na+-translocating NADH:quinone oxidoreductase in voltage generation and Na+ extrusion in Vibrio cholerae
JF  - Biochimica et biophysica acta : Bioenergetics
N2  - 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.
KW  - Nuclear magnetic resonance (NMR)
KW  - Sodium transport
KW  - Vibrio cholerae
KW  - Respiration
KW  - Na+ homeostasis
KW  - Hypoosmotic stress
Y1  - 2016
U6  - https://doi.org/10.1016/j.bbabio.2015.12.010
SN  - 0005-2728
SN  - 0006-3002
VL  - 1857
SP  - 473
EP  - 482
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Friedrich, Tobias
A1  - Krejca, Martin Stefan
A1  - Rothenberger, Ralf
A1  - Arndt, Tobias
A1  - Hafner, Danijar
A1  - Kellermeier, Thomas
A1  - Krogmann, Simon
A1  - Razmjou, Armin
T1  - Routing for on-street parking search using probabilistic data
JF  - AI communications : AICOM ; the European journal on artificial intelligence
N2  - 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.
KW  - Parking search
KW  - probabilistic routing
KW  - constrained optimization
KW  - field study
Y1  - 2019
U6  - https://doi.org/10.3233/AIC-180574
SN  - 0921-7126
SN  - 1875-8452
VL  - 32
IS  - 2
SP  - 113
EP  - 124
PB  - IOS Press
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Prasse, Rüdiger
A1  - Ristow, Michael
A1  - Klemm, Gunther
A1  - Machatzi, Bernd
A1  - Raus, Thomas
A1  - Scholz, Hildemar
A1  - Stohr, Gerrit
A1  - Sukopp, Herbert
A1  - Zimmermann, Friedrich
T1  - Liste der wildwachsenden Gefäßpflanzen des Landes Berlin : mit Roter Liste
Y1  - 2001
SN  - 3-88961-137-0
PB  - Kulturbuch-Verl.
CY  - Berlin
ER  - 
TY  - JOUR
A1  - Castellanos, Reynel Urrea
A1  - Friedrich, Thomas
A1  - Petrovic, Nevena
A1  - Altmann, Simone
A1  - Brzezinka, Krzysztof
A1  - Gorka, Michal
A1  - Graf, Alexander
A1  - Bäurle, Isabel
T1  - FORGETTER2 protein phosphatase and phospholipase D modulate heat stress memory in Arabidopsis
JF  - The plant journal
N2  - 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.
KW  - priming
KW  - protein phosphatase
KW  - stress memory
KW  - heat stress
KW  - Arabidopsis
KW  - thaliana
Y1  - 2020
U6  - https://doi.org/10.1111/tpj.14927
SN  - 0960-7412
SN  - 1365-313X
VL  - 104
IS  - 1
SP  - 7
EP  - 17
PB  - Wiley
CY  - Hoboken
ER  - 
TY  - JOUR
A1  - Kabelitz, Tina
A1  - Brzezinka, Krzysztof
A1  - Friedrich, Thomas
A1  - Gorka, Michal
A1  - Graf, Alexander
A1  - Kappel, Christian
A1  - Bäurle, Isabel
T1  - A JUMONJI Protein with E3 Ligase and Histone H3 Binding Activities Affects Transposon Silencing in Arabidopsis
JF  - Plant physiology : an international journal devoted to physiology, biochemistry, cellular and molecular biology, biophysics and environmental biology of plants
N2  - 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.
Y1  - 2016
U6  - https://doi.org/10.1104/pp.15.01688
SN  - 0032-0889
SN  - 1532-2548
VL  - 171
SP  - 344
EP  - 358
PB  - American Society of Plant Physiologists
CY  - Rockville
ER  -