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

Characterization of intrinsically harmonic one-forms is given. Relations to singularity theory are discussed.

Very strong wind gusts can cause derailment of some high speed trains so knowledge of the wind process at extreme levels is required. Since the sensitivity of the train to strong wind occurrences varies with the relative direction of a gust this aspect has to be accounted for. We first focus on the wind process at one weather station. An extreme value model accounting at the same time for very strong wind speeds and wind directions is considered and applied to both raw data and component data, where the latter represent the force of the wind in a chosen direction. Extreme quantiles and exceedance probabilities are estimated and we give corresponding confidence intervals. A common problem with wind data, called the masking problem, is that per time interval only the largest wind speed over all directions is recorded, while occurrences in all other directions remain unrecorded for this time interval. To improve model estimates we suggest a model accounting for the masking problem. A simulation study is carried out to analyse the behaviour of this model under different conditions; the performance is judged by comparing the new model with a traditional model using the mean square error of high quantiles. Thereafter the model is applied to wind data. The model turns out to have desirable properties in the simulation study as well as in the data application. We further consider a multivariate extreme value model recently introduced; it allows for a broad range of dependence structures and is thus ideally suited for many applications. As the dependence structure of this model is characterised by several components, quantifying the degree of dependence is not straight forward. We therefore consider visual summary measures to support judging the degree of dependence and study their behaviour and usefulness via a simulation study. Subsequently, the new multivariate extreme value model is applied to wind data of two gauging stations where directional aspects are accounted for. Therefore this model allows for statements about the joint wind behaviour at the two stations. This knowledge gives insight whether storm events are likely to be jointly present at larger parts of a railway track or rather occur localized.

Due to the rapid development of computer technology and new methods for the extraction of data in the last few years, more and more applications of databases have emerged, for which an efficient and effective similarity search is of great importance. Application areas of similarity search include multimedia, computer aided engineering, marketing, image processing and many more. Special interest adheres to the task of finding similar objects in large amounts of data having complex representations. For example, set-valued objects as well as tree or graph structured objects are among these complex object representations. The grouping of similar objects, the so-called clustering, is a fundamental analysis technique, which allows to search through extensive data sets. The goal of this dissertation is to develop new efficient and effective methods for similarity search in large quantities of complex objects. Furthermore, the efficiency of existing density-based clustering algorithms is to be improved when applied to complex objects. The first part of this work motivates the use of vector sets for similarity modeling. For this purpose, a metric distance function is defined, which is suitable for various application ranges, but time-consuming to compute. Therefore, a filter refinement technology is suggested to efficiently process range queries and k-nearest neighbor queries, two basic query types within the field of similarity search. Several filter distances are presented, which approximate the exact object distance and can be computed efficiently. Moreover, a multi-step query processing approach is described, which can be directly integrated into the well-known density-based clustering algorithms DBSCAN and OPTICS. In the second part of this work, new application ranges for density-based hierarchical clustering using OPTICS are discussed. A prototype is introduced, which has been developed for these new application areas and is based on the aforementioned similarity models and accelerated clustering algorithms for complex objects. This prototype facilitates interactive semi-automatic cluster analysis and allows visual search for similar objects in multimedia databases. Another prototype extends these concepts and enables the user to analyze multi-represented and multi-instance data. Finally, the problem of music genre classification is addressed as another application supporting multi-represented and multi-instance data objects. An extensive experimental evaluation examines efficiency and effectiveness of the presented techniques using real-world data and points out advantages in comparison to conventional approaches.

So far, mobile devices have mainly been used for interactions between the user, the device and the used service without considering the context of use. However, during the last years we have seen a huge interest in industry and academia in using mobile devices for interactions with things, places and people in the real world, termed physical mobile interactions in this thesis. Until now there has been no comprehensive analysis of these interaction techniques and no user studies have been conducted to analyze when which interaction technique is preferred by which users. Furthermore there is no comprehensive framework available which can be reused by application developers to integrate such interactions into their applications, and no specific methods and best practices have been reported that can be of use when developing physical mobile interactions and applications. This dissertation presents the first comprehensive analysis and classification of physical mobile interactions. Furthermore a mature framework was developed that provides various implementations of four different interaction techniques. These four physical mobile interaction techniques were then used in five different prototypes and analysed in five different user studies. The results concern the advantages and disadvantages of these interaction techniques as seen by potential users. This work also reports experiences, guidelines, methods and best practices that simplify the process of developing physical mobile interactions and applications. Furthermore this dissertation provides an analysis of privacy aspects in mobile interactions with public displays, presents the novel interaction technique rotating compass and the first concept of using the mobile device for direct touch-based interaction with dynamic displays.

Models for infectious disease surveillance counts have to take into account the specific characteristics of this type of data. While showing a regular, often seasonal, pattern over long time periods, there are occasional irregularities or outbreaks. A model which is a compromise between mechanistic models and empirical models is proposed. A key idea is to distinguish between an endemic and an epidemic component, which allows to separate the regular pattern from the irregularities and outbreaks. This is of particular advantage for outbreak detection in public health surveillance. While the endemic component is parameter-driven, the epidemic component is based on observationdriven approaches, including an autoregression on past observations. A particular challenge of infectious disease counts is the modelling of the outbreaks and irregularities in the data. We model the autoregressive parameter of the epidemic component by a Bayesian changepoint model, which shows an adaptive amount of smoothing, and is able to model the jumps and fast increases as well as the smooth decreases in the data. While the model can be used as a generic approach for infectious disease counts, it is particularly suited for outbreak detection in public health surveillance. Furthermore, the predictive qualities of the Bayesian changepoint model allow for short term predictions of the number of disease cases, which are of particular public health interest. A sequential update using a particle filter is provided, that can be used for a prospective analysis of the changepoint model conditioning on fixed values for the other parameters, which is of particular advantage for public health surveillance. A suitable multivariate extension is provided, that is able to explain the interactions between units, e.g. age groups or spatial regions. An application to influenza and meningococcal disease data shows that the occasional outbreaks of meningococcal disease can largely be explained by the influence of influenza on meningococcal disease. The risk of a future meningococcal disease outbreak caused by influenza can be predicted. The comparison of the different models, including a model based on Gaussian Markov random fields shows that the inclusion of the epidemic component as well as a time varying epidemic parameter improves the fit and the predictive qualities of the model.

Modern automated methods for measurement, collection, and analysis of data in industry and science are providing more and more data with drastically increasing structure complexity. On the one hand, this growing complexity is justified by the need for a richer and more precise description of real-world objects, on the other hand it is justified by the rapid progress in measurement and analysis techniques that allow the user a versatile exploration of objects. In order to manage the huge volume of such complex data, advanced database systems are employed. In contrast to conventional database systems that support exact match queries, the user of these advanced database systems focuses on applying similarity search and data mining techniques. Based on an analysis of typical advanced database systems — such as biometrical, biological, multimedia, moving, and CAD-object database systems — the following three challenging characteristics of complexity are detected: uncertainty (probabilistic feature vectors), multiple instances (a set of homogeneous feature vectors), and multiple representations (a set of heterogeneous feature vectors). Therefore, the goal of this thesis is to develop similarity search and data mining techniques that are capable of handling uncertain, multi-instance, and multi-represented objects. The first part of this thesis deals with similarity search techniques. Object identification is a similarity search technique that is typically used for the recognition of objects from image, video, or audio data. Thus, we develop a novel probabilistic model for object identification. Based on it, two novel types of identification queries are defined. In order to process the novel query types efficiently, we introduce an index structure called Gauss-tree. In addition, we specify further probabilistic models and query types for uncertain multi-instance objects and uncertain spatial objects. Based on the index structure, we develop algorithms for an efficient processing of these query types. Practical benefits of using probabilistic feature vectors are demonstrated on a real-world application for video similarity search. Furthermore, a similarity search technique is presented that is based on aggregated multi-instance objects, and that is suitable for video similarity search. This technique takes multiple representations into account in order to achieve better effectiveness. The second part of this thesis deals with two major data mining techniques: clustering and classification. Since privacy preservation is a very important demand of distributed advanced applications, we propose using uncertainty for data obfuscation in order to provide privacy preservation during clustering. Furthermore, a model-based and a density-based clustering method for multi-instance objects are developed. Afterwards, original extensions and enhancements of the density-based clustering algorithms DBSCAN and OPTICS for handling multi-represented objects are introduced. Since several advanced database systems like biological or multimedia database systems handle predefined, very large class systems, two novel classification techniques for large class sets that benefit from using multiple representations are defined. The first classification method is based on the idea of a k-nearest-neighbor classifier. It employs a novel density-based technique to reduce training instances and exploits the entropy impurity of the local neighborhood in order to weight a given representation. The second technique addresses hierarchically-organized class systems. It uses a novel hierarchical, supervised method for the reduction of large multi-instance objects, e.g. audio or video, and applies support vector machines for efficient hierarchical classification of multi-represented objects. User benefits of this technique are demonstrated by a prototype that performs a classification of large music collections. The effectiveness and efficiency of all proposed techniques are discussed and verified by comparison with conventional approaches in versatile experimental evaluations on real-world datasets.

The rapid progress of digital technology has led to a situation where computers have become ubiquitous tools. Now we can find them in almost every environment, be it industrial or even private. With ever increasing performance computers assumed more and more vital tasks in engineering, climate and environmental research, medicine and the content industry. Previously, these tasks could only be accomplished by spending enormous amounts of time and money. By using digital sensor devices, like earth observation satellites, genome sequencers or video cameras, the amount and complexity of data with a spatial or temporal relation has gown enormously. This has led to new challenges for the data analysis and requires the use of modern multimedia databases. This thesis aims at developing efficient techniques for the analysis of complex multimedia objects such as CAD data, time series and videos. It is assumed that the data is modeled by commonly used representations. For example CAD data is represented as a set of voxels, audio and video data is represented as multi-represented, multi-dimensional time series. The main part of this thesis focuses on finding efficient methods for collision queries of complex spatial objects. One way to speed up those queries is to employ a cost-based decompositioning, which uses interval groups to approximate a spatial object. For example, this technique can be used for the Digital Mock-Up (DMU) process, which helps engineers to ensure short product cycles. This thesis defines and discusses a new similarity measure for time series called threshold-similarity. Two time series are considered similar if they expose a similar behavior regarding the transgression of a given threshold value. Another part of the thesis is concerned with the efficient calculation of reverse k-nearest neighbor (RkNN) queries in general metric spaces using conservative and progressive approximations. The aim of such RkNN queries is to determine the impact of single objects on the whole database. At the end, the thesis deals with video retrieval and hierarchical genre classification of music using multiple representations. The practical relevance of the discussed genre classification approach is highlighted with a prototype tool that helps the user to organize large music collections. Both the efficiency and the effectiveness of the presented techniques are thoroughly analyzed. The benefits over traditional approaches are shown by evaluating the new methods on real-world test datasets.

In diesem Buch werden zwei Schwerpunktziele verfolgt. In einem ersten Teil wird die Rahmenkonzeption der Themenstudienarbeit als Lernumgebung im Mathematikunterricht theoretisch fundiert. In einem zweiten Teil wird eine Studie beschrieben, die im Rahmen eines DFG-geförderten Forschungsprojekts durchgeführt wurde und die Evaluation einer Themenstudienarbeit zum Inhaltsbereich des geometrischen Beweisens und Argumentierens zum Gegenstand hatte.

Recent technological advances allow for building real-time, inter-active multi-modal dialog systems for a wide variety of applications ranging from information systems to communication systems interacting with back-end services. To retrieve or update information from various information systems the user has to interact among other man-machine-interfaces (simultaneously) with speech dialog systems. This will inevitably lead a situation where a user has to interact with multiple speech dialog systems within a single thread of activity. Exposing the users to such an environment with diverse speech interfaces will result in increased cognitive load and thus bad usability. An integrated speech enabled access layer to all available information from different applications would allow the user to access information more efficiently and easily. This dissertation proposes a novel approach to build such an integrated speech user interface to different applications by combining the existing speech user interfaces of different applications automatically or semi-automatically. By analyzing the dialog specifications of different applications, functional and semantic overlaps between the applications are recognized. The overlaps are solved successfully in the level of dialog specification so that the integrated speech user interface provides transparent access to different applications, solves the problems of task sharing and enables information sharing among different applications.

Die Vision des "Ubiquotous Computing" verspricht schon lange eine Welt, in der jeder Dienst zu jeder Zeit an jedem Ort verfügbar ist. Darüber hinaus soll die Alltagswelt mit Rechnern durchsetzt sein, ohne dass die Benutzer diese als solche bewusst wahrnehmen. Durch Kooperation und Informationsaustausch sollen die Benutzer unaufdringlich bei ihren Aufgaben unterstützt werden, genau abgestimmt auf ihre jeweilige Situation. Dafür bedarf es kontextsensitiver Dienste. Kontextsensitive Dienste sind nicht neu: Das Licht im Auto wird automatisch angeschaltet, sobald es draußen dunkler wird. Hierzu sind Sensoren und Aktuatoren fest verknüpft. Um der Vision von ubiquitären Computersystemen näher zu kommen, ist es wichtig, dass Kontextinformationen auch in spontanen, dynamischen Konfigurationen bereitgestellt, gefunden, ausgetauscht und verstanden werden können. Dies ist die Ausgangssituation dieser Arbeit: Kontextbereitstellung in offenen, ubiquitären Systemen. Dazu werden mehrere Beiträge geliefert: Eine Modellierung für Kontextinformationen, eine darauf aufbauende, dynamische Beschreibung für Kontextinformationsdienste und die Einführung von Kontextkonstruktionsbäumen, mit denen auf nicht-verfügbare Kontextinformationen geschlossen werden kann, oder mit denen diese wenigstens abgeschätzt werden können.

Innovative technologies in the area of multimedia and mechanical engineering as well as novel methods for data acquisition in different scientific subareas, including geo-science, environmental science, medicine, biology and astronomy, enable a more exact representation of the data, and thus, a more precise data analysis. The resulting quantitative and qualitative growth of specifically spatial and temporal data leads to new challenges for the management and processing of complex structured objects and requires the employment of efficient and effective methods for data analysis. Spatial data denote the description of objects in space by a well-defined extension, a specific location and by their relationships to the other objects. Classical representatives of complex structured spatial objects are three-dimensional CAD data from the sector "mechanical engineering" and two-dimensional bounded regions from the area "geography". For industrial applications, efficient collision and intersection queries are of great importance. Temporal data denote data describing time dependent processes, as for instance the duration of specific events or the description of time varying attributes of objects. Time series belong to one of the most popular and complex type of temporal data and are the most important form of description for time varying processes. An elementary type of query in time series databases is the similarity query which serves as basic query for data mining applications. The main target of this thesis is to develop an effective and efficient algorithm supporting collision queries on spatial data as well as similarity queries on temporal data, in particular, time series. The presented concepts are based on the efficient management of interval sequences which are suitable for spatial and temporal data. The effective analysis of the underlying objects will be efficiently supported by adequate access methods. First, this thesis deals with collision queries on complex spatial objects which can be reduced to intersection queries on interval sequences. We introduce statistical methods for the grouping of subsequences. Involving the concept of multi-step query processing, these methods enable the user to accelerate the query process drastically. Furthermore, in this thesis we will develop a cost model for the multi-step query process of interval sequences in distributed systems. The proposed approach successfully supports a cost based query strategy. Second, we introduce a novel similarity measure for time series. It allows the user to focus specific time series amplitudes for the similarity measurement. The new similarity model defines two time series to be similar iff they show similar temporal behavior w.r.t. being below or above a specific threshold. This type of query is primarily required in natural science applications. The main goal of this new query method is the detection of anomalies and the adaptation to new claims in the area of data mining in time series databases. In addition, a semi-supervised cluster analysis method will be presented which is based on the introduced similarity model for time series. The efficiency and effectiveness of the proposed techniques will be extensively discussed and the advantages against existing methods experimentally proofed by means of datasets derived from real-world applications.

The Extensible Markup Language (XML) is extremely popular as a generic markup language for text documents with an explicit hierarchical structure. The different types of XML data found in today’s document repositories, digital libraries, intranets and on the web range from flat text with little meaningful structure to be queried, over truly semistructured data with a rich and often irregular structure, to rather rigidly structured documents with little text that would also fit a relational database system (RDBS). Not surprisingly, various ways of storing and retrieving XML data have been investigated, including native XML systems, relational engines based on RDBSs, and hybrid combinations thereof. Over the years a number of native XML indexing techniques have emerged, the most important ones being structure indices and labelling schemes. Structure indices represent the document schema (i.e., the hierarchy of nested tags that occur in the documents) in a compact central data structure so that structural query constraints (e.g., path or tree patterns) can be efficiently matched without accessing the documents. Labelling schemes specify ways to assign unique identifiers, or labels, to the document nodes so that specific relations (e.g., parent/child) between individual nodes can be inferred from their labels alone in a decentralized manner, again without accessing the documents themselves. Since both structure indices and labelling schemes provide compact approximate views on the document structure, we collectively refer to them as structural summaries. This work presents new structural summaries that enable highly efficient and scalable XML retrieval in native, relational and hybrid systems. The key contribution of our approach is threefold. (1) We introduce BIRD, a very efficient and expressive labelling scheme for XML, and the CADG, a combined text and structure index, and combine them as two complementary building blocks of the same XML retrieval system. (2) We propose a purely relational variant of BIRD and the CADG, called RCADG, that is extremely fast and scales up to large document collections. (3) We present the RCADG Cache, a hybrid system that enhances the RCADG with incremental query evaluation based on cached results of earlier queries. The RCADG Cache exploits schema information in the RCADG to detect cached query results that can supply some or all matches to a new query with little or no computational and I/O effort. A main-memory cache index ensures that reusable query results are quickly retrieved even in a huge cache. Our work shows that structural summaries significantly improve the efficiency and scalability of XML retrieval systems in several ways. Former relational approaches have largely ignored structural summaries. The RCADG shows that these native indexing techniques are equally effective for XML retrieval in RDBSs. BIRD, unlike some other labelling schemes, achieves high retrieval performance with a fairly modest storage overhead. To the best of our knowledge, the RCADG Cache is the only approach to take advantage of structural summaries for effectively detecting query containment or overlap. Moreover, no other XML cache we know of exploits intermediate results that are produced as a by-product during the evaluation from scratch. These are valuable cache contents that increase the effectiveness of the cache at no extra computational cost. Extensive experiments quantify the practical benefit of all of the proposed techniques, which amounts to a performance gain of several orders of magnitude compared to various other approaches.