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

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.

Count data models have a large number of pratical applications.

However there can be several problems which prevent the use of

the standard Poisson regression. We may detect

individual unobserved heterogeneity, caused by missing covariates,

and/or excess of zero observations in our data. Both distributional issues

results in deviations of the response distribution from the classical Poisson

assumption. We may in addition want to extend our predictor

to model temporal or spatial correlation and possibly nonlinear effects

of continuous covariates or time scales available in the data.

Here we study and develop semiparametric count data

models which can solve these problems. We have extended the Poisson

distribution to account for overdispersion and/or zero inflation.

Additionally we have incorporated corresponding components in structured additive

form into the predictor. The models are fully Bayesian and inference

is carried out by computationally efficient MCMC techniques. In

simulation studies, we investigate how well the different components

can be identified with the data at hand. Finally, the approaches are

applied to two data sets: to a patent data set and to a large data set

of claim frequencies from car insurance.

Enabling computer systems to understand human thinking or

behaviors has ever been an exciting challenge to computer

scientists. In recent years one such a topic, information

filtering, emerges to help users find desired information items (e.g.~movies, books, news) from large amount of available data, and has become crucial in many applications, like product recommendation, image retrieval, spam email filtering, news filtering, and web navigation etc..

An information filtering system must be able to understand users' information needs. Existing approaches either infer a

user's profile by exploring his/her connections to other users, i.e.~collaborative filtering (CF), or analyzing the content descriptions of liked or disliked examples annotated by the user, ~i.e.~content-based filtering (CBF). Those methods work well to some extent, but are facing difficulties due to lack of insights into the problem.

This thesis intensively studies a wide scope of information

filtering technologies. Novel and principled machine

learning methods are proposed to model users' information needs. The work demonstrates that the uncertainty of user profiles and the connections between them can be effectively modelled by using probability theory and Bayes rule. As one major contribution of this thesis, the work clarifies the ``structure'' of information filtering and gives rise to principled solutions. In summary, the work of this thesis mainly covers the following

three aspects:

Collaborative filtering: We develop a probabilistic model for memory-based collaborative filtering (PMCF), which has clear links with classical memory-based CF. Various heuristics to improve memory-based CF have been proposed

in the literature. In contrast, extensions based on PMCF can be made in a principled probabilistic way. With PMCF, we describe a CF paradigm that involves interactions with

users, instead of passively receiving data from users in conventional CF, and actively chooses the most informative patterns to learn, thereby greatly reduce user efforts and computational costs.

Content-based filtering: One major problem for CBF is the

deficiency and high dimensionality of content-descriptive

features. Information items (e.g.~images or articles) are typically described by high-dimensional features with mixed types of attributes, that seem to be developed independently but intrinsically related. We derive a generalized principle component analysis to merge high-dimensional and heterogenous content features into a low-dimensional continuous latent space. The derived features brings great conveniences to CBF, because most existing algorithms easily cope with low-dimensional and continuous data, and more importantly, the extracted data highlight the intrinsic semantics of original content features.

Hybrid filtering: How to combine CF and CBF in an ``smart'' way remains one of the most challenging problems in information filtering. Little principled work exists so far. This thesis reveals that people's information needs can be naturally modelled with a hierarchical Bayesian thinking, where each individual's data are generated based on his/her own profile model, which itself is a sample from a common distribution of the population of user profiles. Users are thus connected to each other via this common distribution. Due to the complexity of such a distribution in real-world applications, usually applied parametric models are too restrictive, and we thus introduce a nonparametric hierarchical Bayesian model using Dirichlet process. We derive effective and efficient algorithms to learn the described model. In particular, the finally achieved hybrid filtering methods are surprisingly simple and intuitively understandable, offering clear insights to previous work on pure CF, pure CBF, and hybrid filtering.

Mit Hilfe einer unitaeren Transformation wird der Coulomb-Dirac-Operator eines Ions in einen pseudorelativistischen Operator uebergefuehrt, der zu beliebiger Ordnung n in der Potentialstaerke block-diagonal ist bezueglich der Projektionen auf den positiven bzw. negativen Spektralraum des freien Dirac-Operators. Fuer ein Ion mit einem oder mit zwei Elektronen und n=2, wird die Positivitaet des pseudorelativistischen Operators sowie die Relativbeschraenktheit der Potentialterme hoeherer Ordnung bezueglich der kinetischen Energie und bezueglich der Potentialterme niedrigerer Ordnung im Fall unterkritischer Potentialstaerke gezeigt. Ferner werden Aussagen zum wesentlichen Spektrum des pseudorelativistischen Operators gemacht.

Knowledge Discovery in Databases (KDD) is the non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data. The core step of the KDD process is the application of a Data Mining algorithm in order to produce a particular enumeration of patterns and relationships in large databases. Clustering is one of the major data mining tasks and aims at grouping the data objects into meaningful classes (clusters) such that the similarity of objects within clusters is maximized, and the similarity of objects from different clusters is minimized. Beside many others, the density-based clustering notion underlying the algorithm DBSCAN and its hierarchical extension OPTICS has been proposed recently, being one of the most successful approaches to clustering.

In this thesis, our aim is to advance the state-of-the-art clustering, especially density-based clustering by identifying novel challenges for density-based clustering and proposing innovative and solid solutions for these challenges.

We describe the development of the industrial prototype BOSS (Browsing OPTICS plots for Similarity Search) which is a first step towards developing a comprehensive, scalable and distributed computing solution designed to make the efficiency and analytical capabilities of OPTICS available to a broader audience. For the development of BOSS, several key enhancements of OPTICS are required which are addressed in this thesis. We develop incremental algorithms of OPTICS to efficiently reconstruct the hierarchical clustering structure in frequently updated databases, in particular, when a set of objects is inserted in or deleted from the database. We empirically show that these incremental algorithms yield significant speed-up factors over the original OPTICS algorithm. Furthermore, we propose a novel algorithm for automatic extraction of clusters from hierarchical clustering representations that outperforms comparative methods, and introduce two novel approaches for selecting meaningful representatives, using the density-based concepts of OPTICS and producing better results than the related medoid approach.

Another major challenge for density-based clustering is to cope with high dimensional data. Many today's real-world data sets contain a large number of measurements (or features) for a single data object. Usually, global feature reduction techniques cannot be applied to these data sets. Thus, the task of feature selection must be combined with and incooperated into the clustering process. 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 based SUBspace CLUstering) that extends DBSCAN to the problem of subspace clustering. SUBCLU efficiently computes all clusters that would have been found if DBSCAN is applied to all possible subspaces of the feature space. An experimental evaluation on real-world data sets illustrates that SUBCLU is more effective than existing subspace clustering algorithms because it is able to find clusters of arbitrary size and shape, and produces determine results. A semi-hierarchical extension of SUBCLU called RIS (Ranking Interesting Subspaces) is proposed that does not compute the subspace clusters directly, but generates 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. A comparative evaluation of RIS and SUBCLU shows that RIS in combination with OPTICS can achieve an information gain over SUBCLU. In addition, we propose the algorithm 4C (Computing Correlation Connected Clusters) that extends the concepts of DBSCAN to compute density-based correlation clusters. 4C benefits from an innovative, well-defined and effective clustering model, outperforming related approaches in terms of