Fakultät für Mathematik, Informatik und Statistik - Digitale Hochschulschriften der LMU - Teil 01/02

Virtualisierungstechniken erfreuen sich immer größerer Beliebtheit in vielen Bereichen der Informatik. Ursprünglich wiederentdeckt mit dem Ziel Ressourcen und Dienste zu konsolidieren, dienen Virtualisierungsansätze heute als Grundlage für moderne Grid- und Cloud-Computing-Infastrukturen und werden damit auch im Bereich des Hochleistungsrechnens eingesetzt. Derzeit existieren keine objektiven und systematischen Analysen bezüglich des Wirkungsgrades von Virtualisierungsansätzen, Techniken und Implementierungen, obwohl sie von vielen großen Rechenzentren weltweit eingesetzt und produktiv betrieben werden. Alle existierenden, modernen Hostvirtualisierungsansätze setzen derzeit auf eine Softwareschicht, die sich je nach Virtualisierungstyp zwischen Hardware und Gast-Betriebssystem bzw. zwischen Host- und Gast-Betriebssystem befindet. Eine Anwendung in einer virtuellen Maschine ist somit nicht mehr nur von der Leistung des physischen Systems abhängig, sondern ebenfalls von der Technologie des eingesetzten Virtualisierungsproduktes und nebenläufigen virtuellen Maschinen. Je nach Anwendungstyp kann es daher sinnvoll sein, einen anderen Virtualisierungsansatz zu wählen und auf den Typ der nebenläufigen virtuellen Maschinen zu achten, um den Wirkungsgrad eines lokalen Systems sowie den der globalen Infrastruktur zu optimieren.

Um dieses Ziel zu erreichen, werden in einem zweistufigen Ansatz zunächst theoretisch Virtualisierungsansätze analysiert und Parameter identifiziert, deren Einfluss auf den Wirkungsgrad in einem zweiten Schritt empirisch quantifiziert wird. Für die Durchführung dieser quantitativen Analyse ist eine Anpassung verbreiteter Leistungsmaße, wie z.B. Durchsatz und Antwortzeit, für den Kontext der Virtualisierung erforderlich, da sie sich klassisch gesehen auf das Betriebssystem einer Maschine beziehen, eine virtuelle Maschine jedoch von der Architektur her eher einer klassischen Anwendung entspricht. Die Messung dieses Leistungsmaßes in virtuellen Umgebungen stellt eine weitere Herausforderung dar, da Zeitmessung in virtuellen Maschinen aufgrund von Scheduling durch den Hypervisor generell fehlerbehaftet ist und somit alternative Messmethoden konzipiert werden müssen. Basierend auf den durchgeführten Analysen und Messungen wird anschließend ein Leitfaden entwickelt, der dabei hilft, die zur Virtualisierung einer Infrastruktur benötigten Ressourcen qualitativ sowie quantitativ abzuschätzen und eine Verteilung der virtuellen Maschinen anhand ihres charakteristischen Ressourcenbedarfes auf physische Systeme vorzunehmen, so dass vorhandene physische Ressourcen optimal ausgenutzt werden können. Die Automatisierung des erstellten Leitfadens durch die Entwicklung und prototypische Implementierung eines globalen Ressourcen-Schedulers auf der Basis eines gewichteten Constraint Solvers rundet die Arbeit ab. Der verwendete Ansatz besitzt zwar eine theoretisch exponentielle Laufzeitkomplexität, liefert in der Praxis aufgrund einer entwickelten Greedy-Heuristik jedoch bereits nach extrem kurzer Laufzeit herausragende Ergebnisse. Die optimierten Verteilungen lassen sich anschließend mittels weniger Live Migration realisieren, da bereits bei der Berechnung einer Verteilung auf deren räumliche Nähe zur bestehenden Verteilung geachtet wird.

In the mid 90s, visiting libraries – as means of retrieving the latest literature – was still a common necessity among professionals. Nowadays, professionals simply access information by ‘googling’. Indeed, the name of the Web search engine market leader “Google” became a synonym for searching and retrieving information. Despite the increased popularity of search as a method for retrieving relevant information, at the workplace search engines still do not deliver satisfying results to professionals.

Search engines for instance ignore that the relevance of answers (the satisfaction of a searcher’s needs) depends not only on the query (the information request) and the document corpus, but also on the working context (the user’s personal needs, education, etc.). In effect, an answer which might be appropriate to one user might not be appropriate to the other user, even though the query and the document corpus are the same for both. Personalization services addressing the context become therefore more and more popular and are an active field of research.

This is only one of several challenges encountered in ‘professional search’: How can the working context of the searcher be incorporated in the ranking process; how can unstructured free-text documents be enriched with semantic information so that the information need can be expressed precisely at query time; how and to which extent can a company’s knowledge be exploited for search purposes; how should data from distributed sources be accessed from into one-single-entry-point.

This thesis is devoted to ‘professional search’, i.e. search at the workplace, especially in industrial research and development. We contribute by compiling and developing several approaches for facing the challenges mentioned above. The approaches are implemented into the prototype YASA (Your Adaptive Search Agent) which provides meta-search, adaptive ranking of search results, guided navigation, and which uses domain knowledge to drive the search processes. YASA is deployed in the pharmaceutical research department of Roche in Penzberg – a major pharmaceutical company – in which the applied methods were empirically evaluated.

Being confronted with mostly unstructured free-text documents and having barely explicit metadata at hand, we faced a serious challenge. Incorporating semantics (i.e. formal knowledge representation) into the search process can only be as good as the underlying data. Nonetheless, we are able to demonstrate that this issue can be largely compensated by incorporating automatic metadata extraction techniques. The metadata we were able to extract automatically was not perfectly accurate, nor did the ontology we applied contain considerably “rich semantics”. Nonetheless, our results show that already the little semantics incorporated into the search process, suffices to achieve a significant improvement in search and retrieval.

We thus contribute to the research field of context-based search by incorporating the working context into the search process – an area which so far has not yet been well studied.

For the last decade a multitude of new data formats for the World Wide Web

have been developed, and a huge amount of heterogeneous semi-structured data

is flourishing online. With the ever increasing number of documents on the

Web, rules have been identified as the means of choice for reasoning about

this

data, transforming and integrating it. Query languages such as SPARQL and rule

languages such as Xcerpt use compound queries that are matched or unified with

semi-structured data. This notion of unification is different from the one

that is known from logic programming engines in that it (i) provides

constructs that allow queries to be incomplete in several ways (ii) in that

variables may have different types, (iii) in that it results in sets of

substitutions for the variables in the query instead of a single substitution

and (iv) in that subsumption between queries is much harder to decide than in

logic programming.

This thesis abstracts from Xcerpt query term simulation, SPARQL graph pattern

matching and XPath XML document matching, and shows that all of them can be

considered as a form of rich unification. Given a set of mappings between

substitution sets of different languages, this abstraction opens up the

possibility for format-versatile querying, i.e. combination of queries in

different formats, or transformation of one format into another format within

a single rule.

To show the superiority of this approach, this thesis introduces an extension

of Xcerpt called Xcrdf, and describes use-cases for the combined querying

and integration of RDF and XML data. With XML being the predominant Web

format, and RDF the predominant Semantic Web format, Xcrdf extends Xcerpt

by a set of RDF query terms and construct terms, including query primitives

for RDF containers collections and reifications. Moreover, Xcrdf includes

an RDF path query language called RPL that is more expressive than previously

proposed polynomial-time RDF path query languages, but can still be evaluated

in polynomial time combined complexity.

Besides the introduction of this framework for data integration based on rich

unification, this thesis extends the theoretical knowledge about Xcerpt in

several ways: We show that Xcerpt simulation unification is decidable, and

give complexity bounds for subsumption in several fragments of Xcerpt query

terms. The proof is based on a set of subsumption monotone query term

transformations, and is only feasible because of the injectivity requirement

on subterms of Xcerpt queries. The proof gives rise to an algorithm for

deciding Xcerpt query term simulation. Moreover, we give a semantics to

locally and weakly stratified Xcerpt programs, but this semantics is

applicable not only to Xcerpt, but to any rule language with rich unification,

including multi-rule SPARQL programs. Finally, we show how Xcerpt grouping

stratification can be reduced to Xcerpt negation stratification, thereby also

introducing the notion of local grouping stratification and weak grouping

stratification.

Bohmsche Mechanik ist eine zur orthodoxen Quantenmechanik empirisch äquivalente Quantentheorie über Teilchen in Bewegung, d.h. über Teilchenbahnen. Da auch die Newtonsche Mechanik eine Theorie über Teilchenbahnen ist, lässt sich die Frage nach dem klassischen Limes in der Bohmschen Mechanik somit besonders einfach und klar formulieren: Wann sehen Bohmsche Bahnen wie Newtonsche Bahnen aus? Als ersten Schritt hin zu einer umfassenderen Antwort auf diese Frage zeigen wir, dass die Bohmschen Bahnen, die zu einer speziellen Klasse semiklassischer Wellenpakete gehören, in einem angemessenen Skalenlimes klassisch werden.

Des weiteren werden auch die Bohmschen Bahnen von Teilchen, die an einem kurzreichweitigen Potential gestreut werden, im klassischen Sinne asymptotisch frei: Für große Zeiten werden ihre Geschwindigkeiten konstant. Wir benutzen dieses Resultat, um den Streuquerschnitt (also die Wahrscheinlichkeit, dass Teilchen in einem gegebenen Raumwinkel detektiert werden) aus grundlegenden Prinzipien abzuleiten. Insbesondere zeigen wir, dass bei mehreren gestreuten Teilchen der Kollaps der Wellenfunktion auf Grund der Detektion eines Teilchens die Detektionsstatistik der verbliebenen Teilchen nicht ändert.

This work deals with questions that arise in classical and quantum electrodynamics when describing the phenomena of radiation reaction and pair creation. The two guiding ideas are the absorber idea of Wheeler and Feynman (i.e. all emitted radiation will be again be absorbed by matter) and the electron sea idea of Dirac.

In the first part classical dynamics are studied which allow for a description of radiation reaction without the need of renormalization. The starting point are the coupled Maxwell and Lorentz equations without self-interaction. Based on the notion of absorber medium, it is shown how the so-called Lorentz-Dirac equation for radiation reaction emerges and the intimate connection to the famous Wheeler-Feynman action at a distance electrodynamics is explained. Based on this, the mathematical problem of the existence of solutions to the Wheeler-Feynman theory, which is given by a functional differential equation, is rigorously analyzed.

In the second part the phenomenon of pair creation is discussed from a thermodynamic perspective in which the Dirac sea satisfies the absorber condition. Taking Dirac's original idea seriously, the vacuum is to be regarded as an equilibrium state in which all net-electron-electron interactions vanish. Small departures of this equilibrium can be effectively described by introducing pair creation. For the mathematical discussion these seas are considered to consist of infinitely many electrons (in the thermodynamical limit). The mathematical implementation of the quantum mechanical time-evolution for such infinitely many electron seas subject to prescribed external four-vector fields is then carried out in detail. The main result is that the probability amplitudes induced by this time-evolution are well-defined and unique.

In a last part we give a perspective on the quantization of Wheeler-Feynman-like inter- action. Based on the proposed equations, a derivation of the Dirac-Barut equation is given, which seems to predict QED corrections in accordance with the experiment.

In this thesis we study convex subcomplexes of spherical buildings. In particular, we are interested in a question of J. Tits which goes back to the 50’s, the so-called Center

Conjecture. It states that a convex subcomplex of a spherical building is a subbuilding or the building automorphisms preserving the subcomplex have a common fixed point in it.

A proof of the Center Conjecture for the buildings of classical types (An, Bn and Dn)

has been given by B. Muehlherr and J. Tits in [MT06]. The F4-case was presented by C.

Parker and K. Tent in a talk in Oberwolfach [PT08]. Both approaches use combinatorial methods from incidence geometry. B. Leeb and the author gave in [LR09] differentialgeometric proofs for the cases F4 and E6 from the point of view of the theory of metric spaces with curvature bounded from above.

In this work we develop the differential-geometric approach further. Our main result is the proof of the Center Conjecture for buildings of type E7 and E8, whose geometry

is considerably more complicated. In particular, this completes the proof of the Center Conjecture for all thick spherical buildings. We also give a short differential-geometric proof for the classical types. Finally, we show how the cases F4, E6 and E7 can be deduced

from the E8-case.

Die meisten internationalen und oft auch nationalen Netzverbindungen sind als horizontal gekoppelte Teildienste realisiert, die von mehreren Service Providern (SPs) erbracht werden.

Die Ende-zu-Ende (E2E) Dienstgüte (engl. Quality of Service, QoS) setzt sich aus der Güte der involvierten Teildienste zusammen.

In Bezug auf die E2E-QoS haben sich zwischen den SPs zwei Herangehensweisen etabliert: für die garantierte E2E-Dienstgüte werden üblicherweise hierarchische Organisationsbeziehungen aufgebaut, bei einer Gleichberechtigung der beteiligten Provider (was bei Internet- und Telefonverbindungen häufig der Fall ist) hat sich die sog. Best-Effort-Strategie durchgesetzt.

Durch die Anforderungen der modernen internationalen Forschungsprojekte und der neuartigen kundenorientierten Dienste ist nun der Bedarf entstanden, die E2E-QoS bei Netzverbindungen auch dann zu garantieren, wenn der Aufbau hierarchischer Organisationsbeziehungen aus diversen Gründen nicht möglich ist.

%

Die Dienstklasse, die die angesprochenen technischen und organisatorischen Eigenschaften in sich vereint, wird in dieser Arbeit als Verkettete Dienste (engl.: Concatenated Services) referenziert.

Um die Anforderungen für die zu entwickelnde Lösung zu bestimmen, werden in dieser Arbeit die Interessen unterschiedlicher Akteure in verschiedenen Verbindungsdiensten analysiert. Eine darauffolgende Untersuchung von existierenden Lösungen in relevanten Forschungsbereichen liefert eine Reihe von möglichen Lösungsbausteinen und lehrreichen Erfahrungen, die bei der Konzeption der eigentlichen Lösung berücksichtigt werden.

Die entwickelte Lösung besteht aus drei Teilen. Der Kern der Lösung ist durch die SLM-aware Routing-Architektur gegeben. In der entwickelten Lösung werden während des Routings nicht nur der Pfadverlauf, sondern auch die QoS-Anforderungen und die benötigte Managementfunktionalität aller involvierten Teildienste bestimmt. Durch die Bestimmung der Akteure, die die benötigten Rollen übernehmen sollen, sowie der Kommunikationswege zwischen Managementkomponenten wird die Durchführung von Service-Level-Management (SLM) in allen Lebenszyklusphasen ermöglicht.

Die Integrationsrolle zwischen den SPs wird von dem Kommunikationsprotokoll übernommen. Das Protokoll ist sowohl für die Signalisierung als auch für den Informationsaustausch während des kompletten Dienstinstanz-Lebenszyklus zuständig. Die mit den erlaubten Signalen assoziierten Basisprozesse erlauben eine unmissverständliche und intuitive Definition des erwarteten Verhaltens.

Die Definition von Referenzprozessen für Service Level Management bei Verketteten Diensten rundet die entwickelte Lösung ab. Die SLM-Prozesse bauen ausschließlich auf dem zuvor definierten Kommunikationsprotokoll auf, wodurch eine leichte Anpassbarkeit dieser Prozesse an zusätzliche Anforderungen gewährleistet wird.

Die Funktionsweise der entwickelten Lösung wird an einem detaillierten Beispiel illustriert. Die Güte der Lösung wird anhand der Erfahrungen mit der Integration der Lösungsteile in verschiedenen Forschungsprojekten sowie anhand der aufgestellten Anforderungen bewertet. Ein kurzer Ausblick auf die Weiterentwicklungsmöglichkeiten und auf verwandte Forschungsfragestellungen schließt diese Arbeit ab.

In the last 20 years the formal approach to the development

of software turned out to be a crucial technique for the generation

of correct programs.

This idea has its theoretical base into the several semi-automatic

methods to transform a formal specification that describe the behavior

of a program into an effective executable piece of code.

One of this is the so-called "program extraction from proof". The idea

is that from an constructive proof of a formula "for each x there exists

y such that P(x,y)" we can automatically extract a program "t" such that

the property P(x,t(x)) hold. In our days such proofs are normally written

by ad-hoc tools (some of them are: COQ, ISABLLE, MINLOG, PX, AGDA, etc...)

called "proof assistants".

Even if today this technique is pretty well established, the "manipulation"

of proofs in order to develop performing programs did not received big attention.

In this thesis we will develop several automatic and semi-automatic methods in

order to extract efficient code from constructive proofs. Our field of application

will be computational biology, a research field in which the development of

efficient programs is crucial. So our main goal will be to show how the manipulation

of formal proofs, essentially studied by proof theorist, has a big effect also in

practical program generation.

In prospective randomized trials differences in population based means can be considered as estimates of mean causal exposure or treatment effects. Nevertheless, occurence of intermediate events in the course of a trial may lead to biased estimates of treatment effects. Particularly this will be the case, if the probability of such an event is not independent of initial treatment allocation and the intermediate event is both a risk factor for the main outcome parameter (e.g. survival) and a predictor of subsequent treatment. This situation was referred as

'treatment by indication problem' by Robins (1992) and is common in epidemiological trials. Robins demonstrated that the usual approach of an adjusted estimation of treatment

effect using a time-dependent proportional hazards model may be biased in this situation, whether or not one further adjusts for past confounder history in the analysis. In this thesis a novel inference procedure for randomized trials is introduced which is based on the idea of Robin's G-Estimation principle but particularly consideres specifics of randomized trials. The suggested procedure allows for an unbiased and consistent estimation of a treatment effect parameter (or paremeter vector) which is connected by a real-valued function to the parameters of an underlying distribution of survival times. In fulfilment of the requirements of a causal individual-level based model, a link of a subject's observed and counterfactual

survival time is directly achieved by the inverse distribution function of survival times in a reference treatment arm. In this term, causal inference is

feasible based on the likelihood function and its corresponding test statistics, even under appropriate consideration of time-dependent confounders.

In the 1990s a number of technological innovations appeared that revolutionized biology, and 'Bioinformatics' became a new scientific discipline. Microarrays can measure the abundance of tens of thousands of mRNA species, data on the

complete genomic sequences of many different organisms are available, and other technologies make it possible to study various processes at the molecular level. In Bioinformatics and Biostatistics, current research and computations are limited by the available computer hardware. However, this problem can be solved using high-performance computing resources. There are several reasons for the increased focus on high-performance computing: larger data sets,

increased computational requirements stemming from more sophisticated methodologies, and latest developments in computer chip production.

The open-source programming language 'R' was developed to provide a powerful and extensible environment for statistical and graphical techniques. There are many

good reasons for preferring R to other software or programming languages for scientific computations (in statistics and biology). However, the development of

the R language was not aimed at providing a software for parallel or high-performance computing. Nonetheless, during the last decade, a great deal of research has been conducted on using parallel computing techniques with R.

This PhD thesis demonstrates the usefulness of the R language and parallel computing for biological research. It introduces parallel computing with R, and reviews and evaluates existing techniques and R packages for parallel computing on Computer Clusters, on Multi-Core Systems, and in Grid Computing. From a computer-scientific point of view the packages were examined as to their reusability in biological applications, and some upgrades were proposed.

Furthermore, parallel applications for next-generation sequence data and preprocessing of microarray data were developed. Microarray data are characterized by high levels of noise and bias. As these perturbations have to be removed, preprocessing of raw data has been a research topic of high priority over the past few years. A new Bioconductor package called affyPara for parallelized preprocessing of high-density oligonucleotide microarray data was developed and published. The partition of data can be performed on arrays using a block cyclic partition, and, as a result, parallelization of algorithms becomes directly

possible. Existing statistical algorithms and data structures had to be adjusted and reformulated for the use in parallel computing. Using the new parallel infrastructure, normalization methods can be enhanced and new methods became available. The partition of data and distribution to several nodes or processors solves the main memory problem and accelerates the methods by up to the factor fifteen for 300 arrays or more.

The final part of the thesis contains a huge cancer study analysing more than 7000 microarrays from a publicly available database, and estimating gene interaction networks. For this purpose, a new R package for microarray data management was developed, and various challenges regarding the analysis of this amount of data are discussed. The comparison of gene networks for different

pathways and different cancer entities in the new amount of data partly confirms already established forms of gene interaction.