Perhaps the most flexible synopsis of a database is a uniform random sample of the data; such samples are widely used to speed up the processing of analytic queries and data-mining tasks, to enhance query optimization, and to facilitate information integration. Most of the existing work on database sampling focuses on how to create or exploit a random sample of a static database, that is, a database that does not change over time. The assumption of a static database, however, severely limits the applicability of these techniques in practice, where data is often not static but continuously evolving. In order to maintain the statistical validity of the sample, any changes to the database have to be appropriately reflected in the sample. In this thesis, we study efficient methods for incrementally maintaining a uniform random sample of the items in a dataset in the presence of an arbitrary sequence of insertions, updates, and deletions. We consider instances of the maintenance problem that arise when sampling from an evolving set, from an evolving multiset, from the distinct items in an evolving multiset, or from a sliding window over a data stream. Our algorithms completely avoid any accesses to the base data and can be several orders of magnitude faster than algorithms that do rely on such expensive accesses. The improved efficiency of our algorithms comes at virtually no cost: the resulting samples are provably uniform and only a small amount of auxiliary information is associated with the sample. We show that the auxiliary information not only facilitates efficient maintenance, but it can also be exploited to derive unbiased, low-variance estimators for counts, sums, averages, and the number of distinct items in the underlying dataset. In addition to sample maintenance, we discuss methods that greatly improve the flexibility of random sampling from a system's point of view. More specifically, we initiate the study of algorithms that resize a random sample upwards or downwards. Our resizing algorithms can be exploited to dynamically control the size of the sample when the dataset grows or shrinks; they facilitate resource management and help to avoid under- or oversized samples. Furthermore, in large-scale databases with data being distributed across several remote locations, it is usually infeasible to reconstruct the entire dataset for the purpose of sampling. To address this problem, we provide efficient algorithms that directly combine the local samples maintained at each location into a sample of the global dataset. We also consider a more general problem, where the global dataset is defined as an arbitrary set or multiset expression involving the local datasets, and provide efficient solutions based on hashing.

Der erste Teil der Arbeit beschreibt die Etablierung einer modifizierten Form des klassichen SILAC-Verfahrens, das in der quantitativen Massenspektrometrie zur Bestimmung von relativen Änderungen in Proteinmengen benutzt wird. Im sog. „pulsed SILAC (pSILAC)“ Verfahren werden Zellen im Zuge einer differentiellen Behandlung in Kulturmedien transferiert, die unterschiedlich Isotop-markierte Aminosäuren enthalten. Da hier die Quantifizierung auf dem Verhältnis der neusynthetisierten Proteinmengen beruht, können gezielt Unterschiede in der Proteinproduktion bestimmt werden. Mit Hilfe von pSILAC konnte im zweiten Teil der Arbeit erstmals quantitativ erfasst werden, welchen Einfluss microRNAs auf die Proteinsynthese ausüben. So konnte gezeigt werden, dass sowohl die Überexpression als auch die Repression einzelner microRNAs die Produktion hunderter Proteine beeinflussen kann. Außerdem konnten Genprodukte identifiziert werden, die ausschließlich translational reguliert werden. Die Messung von Proteinneusynthese ermöglichte auch die Bestimmung von Proteinumsatzraten, dargestellt im dritten Teil der Arbeit. Zusammen mit mRNA-Umsatzraten sowie Protein- und mRNA-Mengen bilden sie die Grundlage für eine dynamische Beschreibung zelluärer Genexpression. Durch den gleichzeitigen Einsatz des Nukleosidanalogons 4-Thiouridin (4sU) und von schweren Aminosäuren (SILAC) konnte eine metabolische Markierung neusynthetiserter mRNAs und Proteine in murinen Fibroblasten erreicht und damit eine Berechnung von Protein- und mRNA-Halbwertszeiten und absoluten Mengen für ca. 5,000 Gene ermöglicht werden. Während mRNA- und Proteinenmengen deutlich korrelierten, war zwischen mRNA- und Proteinhalbwertszeiten nur eine äußerste schwache Korrelation zu erkennen. Dennoch stehen mRNA- und Proteinumsatzraten nicht einem willkürlichen Zusammhang zu einander, da bestimmte Kombinationen von mRNA- und Proteinhalbwertszeiten eine Optimierung von Genen hinsichtlich ihrer biologischen Funktionen erkennen ließen. / The first part of the thesis describes the establishment of a modified version of the classic SILAC approach routinely used in quantitative mass spectrometry (MS) to assay relative changes in protein levels. In the newly-devised approach termed pulsed SILAC (pSILAC) differentially treated cells are transferred to culture medium supplemented with different versions of stable-isotope labeled heavy amino acids. As MS-based relative quantification is exclusively based on the newly-synthesized heavy protein amounts the method enables the detection of differences in protein production resulting from the treatment. The second part of the thesis shows the use of pSILAC to globally quantify the impact of microRNAs onto the proteome. Ectopic over-expression or knock-down of a single microRNA both affected protein production of hundreds of proteins. pSILAC identified several target genes as exclusively translationally regulated as changes in corresponding transcript levels were virtually absent. Measuring newly-synthesized protein amounts with heavy amino acids in a pulsed-labeling fashion has also been used to determine turnover rates of individual proteins, described in the third part of the present work. Along with transcript turnover as well as mRNA and protein levels they are essential for a dynamic description of gene expression. Simultaneous application of the nucleoside analogue 4-thiouridine (4sU) and heavy amino acids (SILAC) to metabolically label newly-produced mRNAs and proteins in mouse fibroblasts resulted in the calculation of mRNA and protein lifetimes and absolute levels for approximately 5,000 genes. While mRNA and protein levels were overall well correlated, a correlation between mRNA and protein half-lives was virtually absent. Yet this seemingly chaotic distribution of mRNA and protein half-lives was highly instructive since specific gene subsets have obviously evolved distinct combinations of half-lives that relate to their biological functions.

In dieser Arbeit beweisen wir für Optimierungsprobleme in L0-Moduln relevante Resultate und untersuchen Anwendungen für die Darstellung von Präferenzen. Im ersten Kapitel geht es um quasikonkave, monotone und lokale Funktionen von einem L0-Modul X nach L0, die wir robust darstellen. Im zweiten Kapitel entwickeln wir das Ekeland’sche Variationsprinzip für L0-Moduln, die eine L0-Metrik besitzen. Wir beweisen eine L0 -Variante einer Verallgemeinerung des Ekeland’schen Theorems. Der Beweis des Brouwerschen Fixpunktsatzes für Funktionen, die auf (L0)^d definiert sind, wird in Kapitel 3 behandelt. Wir definieren das Konzept des Simplexes in (L0)^d und beweisen, dass jede lokale, folgenstetige Funktion darauf einen Fixpunkt besitzt. Dies nutzen wir, um den Fixpunktsatz auch für Funktionen auf beliebigen abgeschlossenen, L0 -konvexen Mengen zu zeigen. Eine allgemeinere Struktur als L0 ist die bedingte Menge. Im vierten Kapitel behandeln wir bedingte topologische Vektorräume. Wir führen das Konzept der Dualität für bedingte Mengen ein und beweisen Theoreme der Funktionalanalysis darauf, unter anderem das Theorem von Banach-Alaoglu und Krein-Šmulian. Im fünften Kapitel widmen wir uns der Darstellung mit wandernden konvexen Mengen. Wir zeigen danach, wie die Transitivität für diese Darstellungsform beschrieben werden kann. Abschließend modellieren wir die Eigenschaft, dass die Transitivität einer Relation nur für ähnliche Elemente gesichert ist und diskutieren Arten der Darstellung solcher Relationen. / In this thesis, we prove results relevant for optimization problems in L0-modules and study applications to order theory. The first part deals with the notion of an Assessment Index (AI). For an L0 -module X an AI is a quasiconcave, monotone and local function mapping to L0. We prove a robust representation of these AIs. In the second chapter of this thesis, we develop Ekeland’s variational principle for L0-modules allowing for an L0-metric. We prove an L0-Version of a generalization of Ekeland’s theorem. A further application of L0 -theory is examined in the third chapter of this thesis, namely an extension of the Brouwer fixed point theorem to functions on (L0)^d . We define a conditional simplex, which is a simplex with respect to L0 , and prove that every local, sequentially continuous function has a fixed point. We extend the fixed point theorem to arbitrary closed, L0-convex sets. A more general structure than L0 -modules is the concept of conditional sets. In the fourth chapter of the thesis, we study conditional topological vector spaces. We examine the concept of duality for conditional sets and prove results of functional analysis: among others, the Banach-Alaoglu and the Krein-Šmulian theorem. Any L0 -module being a conditional set allows to apply all results to L0 -theory. In the fifth chapter, we discuss the property of transitivity of relations and its connection to certain forms of representations. After a survey of common representations of preferences, we attend to relations induced by moving convex sets which are relations of the form that x is preferred to y if and only if x − y is in a convex set depending on y. We examine in which cases such a representation is transitive. Finally, we exhibit nontransitivity due to dissimilarity of the compared object and discuss representations for relations of that type.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

No description available.