Refine
Year of publication
Document Type
- Article (15)
- Monograph/Edited Volume (3)
- Part of Periodical (2)
- Part of a Book (1)
- Other (1)
- Postprint (1)
- Review (1)
Keywords
- Cloud Computing (2)
- Forschungsprojekte (2)
- Future SOC Lab (2)
- In-Memory Technologie (2)
- Multicore Architekturen (2)
- Unique column combination (2)
- artifical intelligence (2)
- cloud computing (2)
- in-memory technology (2)
- künstliche Intelligenz (2)
Institute
- Institut für Biochemie und Biologie (6)
- Hasso-Plattner-Institut für Digital Engineering GmbH (5)
- Hasso-Plattner-Institut für Digital Engineering gGmbH (3)
- Dezernat 2: Studienangelegenheiten (2)
- Institut für Chemie (2)
- Extern (1)
- Historisches Institut (1)
- Institut für Ernährungswissenschaft (1)
- Institut für Geowissenschaften (1)
- Institut für Physik und Astronomie (1)
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.
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.
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.
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*.
Portal alumni
(2012)
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.
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.
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.
FORGETTER2 protein phosphatase and phospholipase D modulate heat stress memory in Arabidopsis
(2020)
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.
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.