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

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