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

In recent years, distributed IT applications were developed which pose explicit requirements on the quality of end-to-end connections between the participating parties. Examples include voice-over-IP, video conferencing etc. Hence, those applications' functionality is significantly influenced by the underlying network infrastructures on which applications build upon. Services offered by networks must therefore meet certain criteria of quality - they have to provide and enforce quality-of-service (QoS). For this reason, different architectures have been and still are being developed to realize QoS on the network level. While such architectures have proven to be functional in principle for homogeneous networks of single providers, the situation is completely different when it comes to interconnecting autonomous or/and heterogeneous networks. Today, no QoS-enabled network services are offered which span multiple provider domains. But this is expected and necessary for the future, last but not least because of the pressure imposed by the application level. As there is no universal QoS architecture on the horizon to become accepted globally, ways have to be found to handle heterogeneity in a network of networks. --- When reviewing existing work in the field, it becomes evident that most approaches are limited to specific architectures or certain services. What is still missing is a universal internetworking architecture which could be applied in any situation and to any QoS architecture. The existence of such a generic architecture seems to be uncertain regarding the complexity of the task and the broad spectrum of QoS architectures which have to covered. --- This thesis strictly follows a service-oriented approach which can be summarized as "a generic way for gaining a specific solution". The approach consists of two major steps. The starting point of the first step are the QoS network services which are to be coupled as well as the QoS architectures these services are built upon. Initially, a normalized representation of the architectures is gained by modeling. In doing so, static and dynamic aspects of QoS architectures are considered. Afterwards, the modeling of QoS network services itself takes place and is based on the models for architectures. The whole modeling process creates a normalized starting point for the second major step. It consists of a generic methodology for gaining specific solutions to solve the coupling problem for individual cases. In this step the necessary architectural building blocks and the required workflows for the coupling are identified. The modeling as well as the methodology are strictly service-oriented, especially in considering the whole service life cycle for both parts. --- The generic model and the methodology are illustrated by a series of examples which are derived from real world scenarios. The thesis' results are supported by an analysis of different business use cases, e.g. bid invitation, estimation of effort etc.

Usual microarray data sets include only a handful of observations, but several thousands of predictor variables. Transforming the high-dimensional predictor space to make classification (for instance cancer diagnosis) possible is a major challenge. This thesis deals with various dimension reduction approaches which can handle such data. Chapter 2 gives an introduction into classification with microarray data as well as an overview of a few specific problems such as variable selection and comparison of classification methods. In Chapter 3, I discuss a particular class of interaction structures in the classification framework: "emerging patterns". I propose a new and more general definition referring to underlying probabilities and present a new simple method which is based on the CART algorithm to find the corresponding empirical patterns in concrete data sets. In addition, the detected patterns can be used to define new variables for classification. Thus, I propose a simple scheme to use the patterns to improve the performance of classification procedures. I implemented the search algorithm as well as the classification procedure in the language R. Some of these programs are publicly available from my homepage. Chapter 4 deals with classical linear dimension reduction methods. In the context of binary classification with continuous predictors, I prove two properties concerning the connections between Partial Least Squares (PLS) dimension reduction, between-group PCA and between linear discriminant analysis and between-group PCA. PLS dimension reduction for classification is examined thoroughly in Chapter 5. The classification procedure consisting of PLS dimension reduction and linear discriminant analysis on the new components is compared favorably with some of the best state-of-the-art classification methods using nine real microarray cancer data sets. Moreover, I apply a boosting algorithm to this classification method, which is a novel approach. In addition, I suggest a simple procedure to choose the number of PLS components. At last, I examine the connection between PLS dimension reduction and variable selection and prove a property concerning the equivalence between a common univariate selection criterion and a variable selection approach based on the first PLS component.

XML is nowadays the de facto standard for electronic data interchange on the Web. Available XML data ranges from small Web pages to ever-growing repositories of, e.g., biological and astronomical data, and even to rapidly changing and possibly unbounded streams, as used in Web data integration and publish-subscribe systems. Animated by the ubiquity of XML data, the basic task of XML querying is becoming of great theoretical and practical importance. The last years witnessed efforts as well from practitioners, as also from theoreticians towards defining an appropriate XML query language. At the core of this common effort has been identified a navigational approach for information localization in XML data, comprised in a practical and simple query language called XPath. This work brings together the two aforementioned ``worlds'', i.e., the XPath query evaluation and the XML data streams, and shows as well theoretical as also practical relevance of this fusion. Its relevance can not be subsumed by traditional database management systems, because the latter are not designed for rapid and continuous loading of individual data items, and do not directly support the continuous queries that are typical for stream applications. The first central contribution of this work consists in the definition and the theoretical investigation of three term rewriting systems to rewrite queries with reverse predicates, like parent or ancestor, into equivalent forward queries, i.e., queries without reverse predicates. Our rewriting approach is vital to the evaluation of queries with reverse predicates against unbounded XML streams, because neither the storage of past fragments of the stream, nor several stream traversals, as required by the evaluation of reverse predicates, are affordable. Beyond their declared main purpose of providing equivalences between queries with reverse predicates and forward queries, the applications of our rewriting systems shed light on other query language properties, like the expressivity of some of its fragments, the query minimization, or even the complexity of query evaluation. For example, using these systems, one can rewrite any graph query into an equivalent forward forest query. The second main contribution consists in a streamed and progressive evaluation strategy of forward queries against XML streams. The evaluation is specified using compositions of so-called stream processing functions, and is implemented using networks of deterministic pushdown transducers. The complexity of this evaluation strategy is polynomial in both the query and the data sizes for forward forest queries and even for a large fragment of graph queries. The third central contribution consists in two real monitoring applications that use directly the results of this work: the monitoring of processes running on UNIX computers, and a system for providing graphically real-time traffic and travel information, as broadcasted within ubiquitous radio signals.

This thesis investigates querying the Web and the Semantic Web. It proposes a new rulebased query language called Xcerpt. Xcerpt differs from other query languages in that it uses patterns instead of paths for the selection of data, and in that it supports both rule chaining and recursion. Rule chaining serves for structuring large queries, as well as for designing complex query programs (e.g. involving queries to the Semantic Web), and for modelling inference rules. Query patterns may contain special constructs like partial subqueries, optional subqueries, or negated subqueries that account for the particularly flexible structure of data on the Web. Furthermore, this thesis introduces the syntax of the language Xcerpt, which is illustrated on a large collection of use cases both from the conventional Web and the Semantic Web. In addition, a declarative semantics in form of a Tarski-style model theory is described, and an algorithm is proposed that performs a backward chaining evaluation of Xcerpt programs. This algorithm has also been implemented (partly) in a prototypical runtime system. A salient aspect of this algorithm is the specification of a non-standard unification algorithm called simulation unification that supports the new query constructs described above. This unification is symmetric in the sense that variables in both terms can be bound. On the other hand it is in contrast to standard unification assymmetric in the sense that the unification determines that the one term is a subterm of the other term.

This thesis is concerned with the analysis of spatial and temporal structures of epidemiological data using modern Bayes techniques. Mainly autoregressive distributions as Gaussian Markov random fields or random walks are used as smoothing priors. Such extensive models can be estimated using MCMC methods only. Some effective algorithms are introduced to get estimates in acceptable time. Especially for space time interactions such algorithms are essential. As example spatial Bayesian models are applied for wildlife disease incidence data. Discrete and continous frameworks for spatial analysis are compared on a data set on infant mortality cases. Age-period-cohort models are discussed in detail and an extension for spatial data is presented. Finally a stochastic model for space time data on infectious diseases is described.

The tremendous amount of data produced nowadays in various application domains such as molecular biology or geography can only be fully exploited by efficient and effective data mining tools. One of the primary data mining tasks is clustering, which is the task of partitioning points of a data set into distinct groups (clusters) such that two points from one cluster are similar to each other whereas two points from distinct clusters are not. Due to modern database technology, e.g.object relational databases, a huge amount of complex objects from scientific, engineering or multimedia applications is stored in database systems. Modelling such complex data often results in very high-dimensional vector data ("feature vectors"). In the context of clustering, this causes a lot of fundamental problems, commonly subsumed under the term "Curse of Dimensionality". As a result, traditional clustering algorithms often fail to generate meaningful results, because in such high-dimensional feature spaces data does not cluster anymore. But usually, there are clusters embedded in lower dimensional subspaces, i.e. meaningful clusters can be found if only a certain subset of features is regarded for clustering. The subset of features may even be different for varying clusters. In this thesis, we present original extensions and enhancements of the density-based clustering notion to cope with high-dimensional data. In particular, we propose an algorithm called SUBCLU (density-connected Subspace Clustering) that extends DBSCAN (Density-Based Spatial Clustering of Applications with Noise) to the problem of subspace clustering. SUBCLU efficiently computes all clusters of arbitrary shape and size that would have been found if DBSCAN were applied to all possible subspaces of the feature space. Two subspace selection techniques called RIS (Ranking Interesting Subspaces) and SURFING (SUbspaces Relevant For clusterING) are proposed. They do not compute the subspace clusters directly, but generate a list of subspaces ranked by their clustering characteristics. A hierarchical clustering algorithm can be applied to these interesting subspaces in order to compute a hierarchical (subspace) clustering. In addition, we propose the algorithm 4C (Computing Correlation Connected Clusters) that extends the concepts of DBSCAN to compute density-based correlation clusters. 4C searches for groups of objects which exhibit an arbitrary but uniform correlation. Often, the traditional approach of modelling data as high-dimensional feature vectors is no longer able to capture the intuitive notion of similarity between complex objects. Thus, objects like chemical compounds, CAD drawings, XML data or color images are often modelled by using more complex representations like graphs or trees. If a metric distance function like the edit distance for graphs and trees is used as similarity measure, traditional clustering approaches like density-based clustering are applicable to those data. However, we face the problem that a single distance calculation can be very expensive. As clustering performs a lot of distance calculations, approaches like filter and refinement and metric indices get important. The second part of this thesis deals with special approaches for clustering in application domains with complex similarity models. We show, how appropriate filters can be used to enhance the performance of query processing and, thus, clustering of hierarchical objects. Furthermore, we describe how the two paradigms of filtering and metric indexing can be combined. As complex objects can often be represented by using different similarity models, a new clustering approach is presented that is able to cluster objects that provide several different complex representations.

This thesis discusses some extensions of second-order logic AF2 with primitive constructors representing least and greatest fixed points of monotone operators, which allow to define predicates by induction and coinduction. Though the expressive power of second-order logic has been well-known for a long time and suffices to define (co)inductive predicates by means of its (co)induction principles, it is more user-friendly to have a direct way of defining predicates inductively. Moreover recent applications in computer science oblige to consider also coinductive definitions useful for handling infinite objects, the most prominent example being the data type of streams or infinite lists. Main features of our approach are the use clauses in the (co)inductive definition mechanism, concept which simplifies the syntactic shape of the predicates, as well as the inclusion of not only (co)iteration but also primitive (co)recursion principles and in the case of coinductive definitions an inversion principle. For sake of generality we consider full monotone, and not only positive definitions, after all positivity is only used to ensure monotonicity. Working towards practical use of our systems we give them realizability interpretations where the systems of realizers are strongly normalizing extensions of the second-order polymorphic lambda calculus, system F in Curry-style, with (co)inductive types corresponding directly to the logical systems via the Curry-Howard correspondence. Such realizability interpretations are therefore not reductive: the definition of realizability for a (co)inductive definition is again a (co)inductive definition. As main application of realizability we extend the so-called programming-with-proofs paradigm of Krivine and Parigot to our logics, by means of which a correct program of the lambda calculus can be extracted from a proof in the logic.

Knowledge Discovery in Databases (KDD) is the non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in large data collections. The most important step within the process of KDD is data mining which is concerned with the extraction of the valid patterns. KDD is necessary to analyze the steady growing amount of data caused by the enhanced performance of modern computer systems. However, with the growing amount of data the complexity of data objects increases as well. Modern methods of KDD should therefore examine more complex objects than simple feature vectors to solve real-world KDD applications adequately. Multi-instance and multi-represented objects are two important types of object representations for complex objects. Multi-instance objects consist of a set of object representations that all belong to the same feature space. Multi-represented objects are constructed as a tuple of feature representations where each feature representation belongs to a different feature space. The contribution of this thesis is the development of new KDD methods for the classification and clustering of complex objects. Therefore, the thesis introduces solutions for real-world applications that are based on multi-instance and multi-represented object representations. On the basis of these solutions, it is shown that a more general object representation often provides better results for many relevant KDD applications. The first part of the thesis is concerned with two KDD problems for which employing multi-instance objects provides efficient and effective solutions. The first is the data mining in CAD parts, e.g. the use of hierarchic clustering for the automatic construction of product hierarchies. The introduced solution decomposes a single part into a set of feature vectors and compares them by using a metric on multi-instance objects. Furthermore, multi-step query processing using a novel filter step is employed, enabling the user to efficiently process similarity queries. On the basis of this similarity search system, it is possible to perform several distance based data mining algorithms like the hierarchical clustering algorithm OPTICS to derive product hierarchies. The second important application is the classification and search for complete websites in the world wide web (WWW). A website is a set of HTML-documents that is published by the same person, group or organization and usually serves a common purpose. To perform data mining for websites, the thesis presents several methods to classify websites. After introducing naive methods modelling websites as webpages, two more sophisticated approaches to website classification are introduced. The first approach uses a preprocessing that maps single HTML-documents within each website to so-called page classes. The second approach directly compares websites as sets of word vectors and uses nearest neighbor classification. To search the WWW for new, relevant websites, a focused crawler is introduced that efficiently retrieves relevant websites. This crawler minimizes the number of HTML-documents and increases the accuracy of website retrieval. The second part of the thesis is concerned with the data mining in multi-represented objects. An important example application for this kind of complex objects are proteins that can be represented as a tuple of a protein sequence and a text annotation. To analyze multi-represented objects, a clustering method for multi-represented objects is introduced that is based on the density based clustering algorithm DBSCAN. This method uses all representations that are provided to find a global clustering of the given data objects. However, in many applications there already exists a sophisticated class ontology for the given data objects, e.g. proteins. To map new objects into an ontology a new method for the hierarchical classification of multi-represented objects is described. The system employs the hierarchical structure of the ontology to efficiently classify new proteins, using support vector machines.

The development, design, manufacturing and maintenance of modern engineering products is a very expensive and complex task. Shorter product cycles and a greater diversity of models are becoming decisive competitive factors in the hard-fought automobile and plane market. In order to support engineers to create complex products when being pressed for time, systems are required which answer collision and similarity queries effectively and efficiently. In order to achieve industrial strength, the required specialized functionality has to be integrated into fully-fledged database systems, so that fundamental services of these systems can be fully reused, including transactions, concurrency control and recovery. This thesis aims at the development of theoretical sound and practical realizable algorithms which effectively and efficiently detect colliding and similar complex spatial objects. After a short introductory Part I, we look in Part II at different spatial index structures and discuss their integrability into object-relational database systems. Based on this discussion, we present two generic approaches for accelerating collision queries. The first approach exploits available statistical information in order to accelerate the query process. The second approach is based on a cost-based decompositioning of complex spatial objects. In a broad experimental evaluation based on real-world test data sets, we demonstrate the usefulness of the presented techniques which allow interactive query response times even for large data sets of complex objects. In Part III of the thesis, we discuss several similarity models for spatial objects. We show by means of a new evaluation method that data-partitioning similarity models yield more meaningful results than space-partitioning similarity models. We introduce a very effective similarity model which is based on a new paradigm in similarity search, namely the use of vector set represented objects. In order to guarantee efficient query processing, suitable filters are introduced for accelerating similarity queries on complex spatial objects. Based on clustering and the introduced similarity models we present an industrial prototype which helps the user to navigate through massive data sets.

Conformal field theory is intimately connected to the theory of vertex algebras and the geometry of Riemann surfaces. In this thesis a new algebro-geometric structure called global vertex algebra is defined on Riemann surfaces which is supposed to be a natural generalization of vertex algebras. In order to define this structure a formal calculus of fields on Riemann surfaces is constructed. The basic objects in vertex algebra theory are fields. They are defined as formal Laurent series with possibly infinite principal part. The coefficients are endomorphisms. As an example for such a structure the global vertex algebra of bosons of Krichever-Novikov type will be constructed. At the beginning of this thesis the formal calculus of classical vertex algebras is introduced from the viewpoint of distributions in complex analysis. Furthermore a graphical calculus for the computation of correlation functions of primary fields associated to affine Kac-Moody algebras is introduced.

Das policy–basierte Management nimmt sowohl in der Forschung als auch in der Industrie einen steigenden Stellenwert ein. Durch die verteilte Spezifikation und aufgrund divergenter Ziele können Policies zueinander in Konflikt stehen. Die bereits existierenden Ansätze zur Policy–Konfliktbehandlung sind nur begrenzt einsetzbar, da sie häufig auf eine dediziert Policy–Sprache limitiert sind, wichtige Konfliktarten per se nicht erkennen können oder für neuartige Konfliktarten keine Methodik zur Integration bieten. Diese Arbeit zeigt, dass unter Berücksichtigung von Managementmodellen neue Konfliktarten nachgewiesen werden können, die bis jetzt mit den Ansätzen in der Literatur nicht behandelbar sind. Dazu werden Managementmodelle als a priori Modelle aufgefasst. Ein a priori Modell beschreibt den Sollzustand eines Systems und definiert somit eine Menge von einzuhaltenden Bedingungen. Unter dieser Prämisse werden neuartige Konflikte — Konflikte zwischen Beziehungen von Managementobjekten — nachgewiesen. Den Kern der Lösungsidee bildet eine Methodik zur Ableitung von Konfliktdefinitionen aus Modellaspekten. Dabei werden ausgehend von Modellaspekten Invarianten abgeleitet, mit Policy–Aktionen verknüpft und schließlich Vorbedingungen definiert, deren Einhaltung Konflikte verhindert. Die breite Anwendbarkeit der Methodik wird anhand eines statischen Beziehungsmodells für die Beziehungen der funktionalen Abhängigkeit und Enthaltenseinsrelationen gezeigt. Ebenso wird die Anwendbarkeit der Methodik für Vertreter von dynamischen Modellen, den endlichen Automaten demonstriert. Zur Konfliktbehandlung wurde ein neuer Algorithmus entwickelt, der aus den Phasen Konfliktlokalisierung, Konflikterkennung und Konfliktlösung besteht. In der ersten Phase wird durch Teilmengenbildung die Anzahl der zu betrachtenden Policies schnell reduziert. In der letzten Phase werden für die einzelnen Konfliktarten Strategien entwickelt, die eine optimale Konfliktlösung gewährleisten. Der Algorithmus ist sowohl für die präventive als auch die reaktive Konfliktbehandlung anwendbar. Damit eine generische Lösung erreicht wird, sind wichtige Designziele für die Methodik und dem Algorithmus: die Unabhängigkeit von einer dedizierten Policy–Sprache, die Breite der behandelbaren Konfliktarten sowie die Unabhängigkeit von einem spezifischen Managementinformationsmodell. Die Anwendbarkeit der Lösung in der Praxis wird durch eine exemplarische Abbildung der Konfliktdefinitionen in das Common Information Model gezeigt.

Description and survey of the possible, guaranteed or offered quality of a service (QoS) is one of the key features to establish a performance and quality oriented assesment or accounting of IT-services. This task is accomplished using various criteria - the so called QoS-characteristics - which, in most cases, are specific to a certain service. From the point of view of the service life cycle, characteristics of a service are evaluated with in the usage phase but are usually determined in the negotiation phase before a service is implemented. The realization of this specifications in the following phases of the service life cycle, service provisioning or implementation and service usage, has not been methodically supported until now and has to be done by hand . Thus, the impact of a specification made in the negotiation phase on the other life cycle phases can only be estimated with expert knowledge. An objective assessment of this impact is impossible. The work presented introduces a technique enabling the formal specification of QoScharacteristics, thus allowing an automatic realization of the specification in the provisioning and usage phase of a service. Until now, only isolated approaches on the specification of QoS-characteristics focusing on specific technologies have been made. In this thesis we present a completely technology independent approach distilled from the typical processes used for measuring QoS in different technologies. In order to implement this idea, a formal model of a common measurement process, based on the MNM service model, is introduced and the specification of a QoScharacteristic is formalized as a refinement of this model. A formal language, capable of facilitating the generation of these models has been developed for this purpose. Consequently, a compiler for this language has been developed to automatically generate a measurement system out of the specification of a QoS-characteristic. This enables the uniform and technology independent specification of QoS-characteristics. In conclusion, a concept for the computer aided specification of QoS-characteristics has been established which, as an audit included in this thesis demonstrates, can be applied to various scenarios in the area of service management. The concept introduced adds quality orientation to existing approaches like CSM (customer service management) and thus paves the way to quality oriented service management.