Refine
Year of publication
Document Type
- Doctoral Thesis (26)
- Article (3)
- Book (1)
- Other (1)
Keywords
- Algorithmus (3)
- Middleware (3)
- Abfrageverarbeitung (2)
- Ad-hoc-Netz (2)
- Mobile Computing (2)
- OBDD (2)
- OBDDs (2)
- Peer-to-Peer-Netz (2)
- Selbstorganisation (2)
- mobile computing (2)
Institute
- Informatik (31) (remove)
Reconstructing invisible deviating events: A conformance checking approach for recurring events
(2022)
Conformance checking enables organizations to determine whether their executed processes are compliant with the intended process. However, if the processes contain recurring activities, state-of-the-art approaches unfortunately have difficulties calculating the conformance. The occurrence of complex temporal rules can further increase the complexity of the problem. Identifying this limitation, this paper presents a novel approach towards dealing with recurring activities in conformance checking. The core idea of the approach is to reconstruct the missing events in the event log using defined rules while incorporating specified temporal event characteristics. This approach then enables the use of native conformance checking algorithms. The paper illustrates the algorithmic approach and defines the required temporal event characteristics. Furthermore, the approach is applied and evaluated in a case study on an event log for melanoma surveillance.
Even though in most cases time is a good metric to measure costs of algorithms, there are cases where theoretical worst-case time and experimental running time do not match. Since modern CPUs feature an innate memory hierarchy, the location of data is another factor to consider. When most operations of an algorithm are executed on data which is already in the CPU cache, the running time is significantly faster than algorithms where most operations have to load the data from the memory. The topic of this thesis is a new metric to measure costs of algorithms called memory distance—which can be seen as an abstraction of the just mentioned aspect. We will show that there are simple algorithms which show a discrepancy between measured running time and theoretical time but not between measured time and memory distance. Moreover we will show that in some cases it is sufficient to optimize the input of an algorithm with regard to memory distance (while treating the algorithm as a black box) to improve running times. Further we show the relation between worst-case time, memory distance and space and sketch how to define "the usual" memory distance complexity classes.
Similarity-based retrieval of semantic graphs is a core task of Process-Oriented Case-Based Reasoning (POCBR) with applications in real-world scenarios, e.g., in smart manufacturing. The involved similarity computation is usually complex and time-consuming, as it requires some kind of inexact graph matching. To tackle these problems, we present an approach to modeling similarity measures based on embedding semantic graphs via Graph Neural Networks (GNNs). Therefore, we first examine how arbitrary semantic graphs, including node and edge types and their knowledge-rich semantic annotations, can be encoded in a numeric format that is usable by GNNs. Given this, the architecture of two generic graph embedding models from the literature is adapted to enable their usage as a similarity measure for similarity-based retrieval. Thereby, one of the two models is more optimized towards fast similarity prediction, while the other model is optimized towards knowledge-intensive, more expressive predictions. The evaluation examines the quality and performance of these models in preselecting retrieval candidates and in approximating the ground-truth similarities of a graph-matching-based similarity measure for two semantic graph domains. The results show the great potential of the approach for use in a retrieval scenario, either as a preselection model or as an approximation of a graph similarity measure.
Designing a Randomized Trial with an Age Simulation Suit—Representing People with Health Impairments
(2020)
Due to demographic change, there is an increasing demand for professional care services, whereby this demand cannot be met by available caregivers. To enable adequate care by relieving informal and formal care, the independence of people with chronic diseases has to be preserved for as long as possible. Assistance approaches can be used that support promoting physical activity, which is a main predictor of independence. One challenge is to design and test such approaches without affecting the people in focus. In this paper, we propose a design for a randomized trial to enable the use of an age simulation suit to generate reference data of people with health impairments with young and healthy participants. Therefore, we focus on situations of increased physical activity.
This thesis considers the general task of computing a partition of a set of given objects such that each set of the partition has a cardinality of at least a fixed number k. Among such kinds of partitions, which we call k-clusters, the objective is to find the k-cluster which minimises a certain cost derived from a given pairwise difference between objects which end up the same set. As a first step, this thesis introduces a general problem, denoted by (||.||,f)-k-cluster, which models the task to find a k-cluster of minimum cost given by an objective function computed with respect to specific choices for the cost functions f and ||.||. In particular this thesis considers three different choices for f and also three different choices for ||.|| which results in a total of nine different variants of the general problem. Especially with the idea to use the concept of parameterised approximation, we first investigate the role of the lower bound on the cluster cardinalities and find that k is not a suitable parameter, due to remaining NP-hardness even for the restriction to the constant 3. The reductions presented to show this hardness yield the even stronger result which states that polynomial time approximations with some constant performance ratio for any of the nine variants of (||.||,f)-k-cluster require a restriction to instances for which the pairwise distance on the objects satisfies the triangle inequality. For this restriction to what we informally refer to as metric instances, constant-factor approximation algorithms for eight of the nine variants of (||.||,f)-k-cluster are presented. While two of these algorithms yield the provably best approximation ratio (assuming P!=NP), others can only guarantee a performance which depends on the lower bound k. With the positive effect of the triangle inequality and applications to facility location in mind, we discuss the further restriction to the setting where the given objects are points in the Euclidean metric space. Considering the effect of computational hardness caused by high dimensionality of the input for other related problems (curse of dimensionality) we check if this is also the source of intractability for (||.||,f)-k-cluster. Remaining NP-hardness for restriction to small constant dimensionality however disproves this theory. We then use parameterisation to develop approximation algorithms for (||.||,f)-k-cluster without restriction to metric instances. In particular, we discuss structural parameters which reflect how much the given input differs from a metric. This idea results in parameterised approximation algorithms with parameters such as the number of conflicts (our name for pairs of objects for which the triangle inequality is violated) or the number of conflict vertices (objects involved in a conflict). The performance ratios of these parameterised approximations are in most cases identical to those of the approximations for metric instances. This shows that for most variants of (||.||,f)-k-cluster efficient and reasonable solutions are also possible for non-metric instances.
Digital libraries have become a central aspect of our live. They provide us with an immediate access to an amount of data which has been unthinkable in the past. Support of computers and the ability to aggregate data from different libraries enables small projects to maintain large digital collections on various topics. A central aspect of digital libraries is the metadata -- the information that describes the objects in the collection. Metadata are digital and can be processed and studied automatically. In recent years, several studies considered different aspects of metadata. Many studies focus on finding defects in the data. Specifically, locating errors related to the handling of personal names has drawn attention. In most cases the studies concentrate on the most recent metadata of a collection. For example, they look for errors in the collection at day X. This is a reasonable approach for many applications. However, to answer questions such as when the errors were added to the collection we need to consider the history of the metadata itself. In this work, we study how the history of metadata can be used to improve the understanding of a digital library. To this goal, we consider how digital libraries handle and store their metadata. Based in this information we develop a taxonomy to describe available historical data which means data on how the metadata records changed over time. We develop a system that identifies changes to metadata over time and groups them in semantically related blocks. We found that historical meta data is often unavailable. However, we were able to apply our system on a set of large real-world collections. A central part of this work is the identification and analysis of changes to metadata which corrected a defect in the collection. These corrections are the accumulated effort to ensure data quality of a digital library. In this work, we present a system that automatically extracts corrections of defects from the set of all modifications. We present test collections containing more than 100,000 test cases which we created by extracting defects and their corrections from DBLP. This collections can be used to evaluate automatic approaches for error detection. Furthermore, we use these collections to study properties of defects. We will concentrate on defects related to the person name problem. We show that many defects occur in situations where very little context information is available. This has major implications for automatic defect detection. We also show that properties of defects depend on the digital library in which they occur. We also discuss briefly how corrected defects can be used to detect hidden or future defects. Besides the study of defects, we show that historical metadata can be used to study the development of a digital library over time. In this work, we present different studies as example how historical metadata can be used. At first we describe the development of the DBLP collection over a period of 15 years. Specifically, we study how the coverage of different computer science sub fields changed over time. We show that DBLP evolved from a specialized project to a collection that encompasses most parts of computer science. In another study we analyze the impact of user emails to defect corrections in DBLP. We show that these emails trigger a significant amount of error corrections. Based on these data we can draw conclusions on why users report a defective entry in DBLP.
Automata theory is the study of abstract machines. It is a theory in theoretical computer science and discrete mathematics (a subject of study in mathematics and computer science). The word automata (the plural of automaton) comes from a Greek word which means "self-acting". Automata theory is closely related to formal language theory [99, 101]. The theory of formal languages constitutes the backbone of the field of science now generally known as theoretical computer science. This thesis aims to introduce a few types of automata and studies then class of languages recognized by them. Chapter 1 is the road map with introduction and preliminaries. In Chapter 2 we consider few formal languages associated to graphs that has Eulerian trails. We place few languages in the Chomsky hierarchy that has some other properties together with the Eulerian property. In Chapter 3 we consider jumping finite automata, i. e., finite automata in which input head after reading and consuming a symbol, can jump to an arbitrary position of the remaining input. We characterize the class of languages described by jumping finite automata in terms of special shuffle expressions and survey other equivalent notions from the existing literature. We could also characterize some super classes of this language class. In Chapter 4 we introduce boustrophedon finite automata, i. e., finite automata working on rectangular shaped arrays (i. e., pictures) in a boustrophedon mode and we also introduce returning finite automata that reads the input, line after line, does not alters the direction like boustrophedon finite automata i. e., reads always from left to right, line after line. We provide close relationships with the well-established class of regular matrix (array) languages. We sketch possible applications to character recognition and kolam patterns. Chapter 5 deals with general boustrophedon finite automata, general returning finite automata that read with different scanning strategies. We show that all 32 different variants only describe two different classes of array languages. We also introduce Mealy machines working on pictures and show how these can be used in a modular design of picture processing devices. In Chapter 6 we compare three different types of regular grammars of array languages introduced in the literature, regular matrix grammars, (regular : regular) array grammars, isometric regular array grammars, and variants thereof, focusing on hierarchical questions. We also refine the presentation of (regular : regular) array grammars in order to clarify the interrelations. In Chapter 7 we provide further directions of research with respect to the study that we have done in each of the chapters.
Der vorliegende Bericht basiert auf einer universitätsweiten Online-Umfrage zum Status quo des Forschungsdatenma-nagements an der Universität Trier. Er ist ein erster Schritt, um den aktuellen und zukünftigen Bedarf an zentralen Dienstleistungen zu identifizieren. Neue Handlungsfelder sollen frühzeitig erkannt werden, auch um der Strategie-entwicklung eine Richtung zu weisen.rnDie Befragten befürworten generell die Initiative zur Entwicklung zentraler IT- und Beratungsangebote. Sie sind bereit, die eigenen Forschungsdaten anderen zur Nachnutzung zur Verfügung zu stellen, sofern die geeigneten Instrumente vorhanden, sind die eine solche Arbeitsweise unterstützen. Allerdings wird eine unkommentierte Bereit-stellung von Rohdaten eher kritisch beurteilt. Der Dokumentationsaufwand einer öffentlichen Bereitstellung von Daten wird in einem ungünstigen Kosten-Nutzenverhältnis gesehen. Es fällt auf, dass die Datenarchivierung größ-tenteils in proprietären Formaten erfolgt.
In dieser Arbeit präsentieren wir einen systematischen Ansatz zur Multithread Implementierung von Divide und Conquer sowie inkrementellen Algorithmen. Wir stellen für beide Kategorien von Algorithmen ein Framework vor. Beide Frameworks sollen die Behandlung von Threads erleichtern, die Implementierung von parallelen Algorithmen beschleunigen und die Rechenzeit verringern. Mit Hilfe der Frameworks parallelisieren wir beispielhaft zahlreiche Algorithmen insbesondere aus dem Bereich Computational Geometry, unter anderem: Sortieralgorithmen, konvexe Hülle Algorithmen und Triangulierungen. Der Programmcode zu diese Arbeit ist in C++ unter Verwendung templatisierter Klassen implementiert und basiert auf der LEDA Bibliothek.
We are living in a connected world, surrounded by interwoven technical systems. Since they pervade more and more aspects of our everyday lives, a thorough understanding of the structure and dynamics of these systems is becoming increasingly important. However - rather than being blueprinted and constructed at the drawing board - many technical infrastructures like for example the Internet's global router network, the World Wide Web, large scale Peer-to-Peer systems or the power grid - evolve in a distributed fashion, beyond the control of a central instance and influenced by various surrounding conditions and interdependencies. Hence, due to this increase in complexity, making statements about the structure and behavior of tomorrow's networked systems is becoming increasingly complicated. A number of failures has shown that complex structures can emerge unintentionally that resemble those which can be observed in biological, physical and social systems. In this dissertation, we investigate how such complex phenomena can be controlled and actively used. For this, we review methodologies stemming from the field of random and complex networks, which are being used for the study of natural, social and technical systems, thus delivering insights into their structure and dynamics. A particularly interesting finding is the fact that the efficiency, dependability and adaptivity of natural systems can be related to rather simple local interactions between a large number of elements. We review a number of interesting findings about the formation of complex structures and collective dynamics and investigate how these are applicable in the design and operation of large scale networked computing systems. A particular focus of this dissertation are applications of principles and methods stemming from the study of complex networks in distributed computing systems that are based on overlay networks. Here we argue how the fact that the (virtual) connectivity in such systems is alterable and widely independent from physical limitations facilitates a design that is based on analogies between complex network structures and phenomena studied in statistical physics. Based on results about the properties of scale-free networks, we present a simple membership protocol by which scale-free overlay networks with adjustable degree distribution exponent can be created in a distributed fashion. With this protocol we further exemplify how phase transition phenomena - as occurring frequently in the domain of statistical physics - can actively be used to quickly adapt macroscopic statistical network parameters which are known to massively influence the stability and performance of networked systems. In the case considered in this dissertation, the adaptation of the degree distribution exponent of a random, scale-free overlay allows - within critical regions - a change of relevant structural and dynamical properties. As such, the proposed scheme allows to make sound statements about the relation between the local behavior of individual nodes and large scale properties of the resulting complex network structures. For systems in which the degree distribution exponent cannot easily be derived for example from local protocol parameters, we further present a distributed, probabilistic mechanism which can be used to monitor a network's degree distribution exponent and thus to reason about important structural qualities. Finally, the dissertation shifts its focus towards the study of complex, non-linear dynamics in networked systems. We consider a message-based protocol which - based on the Kuramoto model for coupled oscillators - achieves a stable, global synchronization of periodic heartbeat events. The protocol's performance and stability is evaluated in different network topologies. We further argue that - based on existing findings about the interrelation between spectral network properties and the dynamics of coupled oscillators - the proposed protocol allows to monitor structural properties of networked computing systems. An important aspect of this dissertation is its interdisciplinary approach towards a sensible and constructive handling of complex structures and collective dynamics in networked systems. The associated investigation of distributed systems from the perspective of non-linear dynamics and statistical physics highlights interesting parallels both to biological and physical systems. This foreshadows systems whose structures and dynamics can be analyzed and understood in the conceptual frameworks of statistical physics and complex systems.
This thesis centers on formal tree languages and on their learnability by algorithmic methods in abstractions of several learning settings. After a general introduction, we present a survey of relevant definitions for the formal tree concept as well as special cases (strings) and refinements (multi-dimensional trees) thereof. In Chapter 3 we discuss the theoretical foundations of algorithmic learning in a specific type of setting of particular interest in the area of Grammatical Inference where the task consists in deriving a correct formal description for an unknown target language from various information sources (queries and/or finite samples) in a polynomial number of steps. We develop a parameterized meta-algorithm that incorporates several prominent learning algorithms from the literature in order to highlight the basic routines which regardless of the nature of the information sources have to be run through by all those algorithms alike. In this framework, the intended target descriptions are deterministic finite-state tree automata. We discuss the limited transferability of this approach to another class of descriptions, residual finite-state tree automata, for which we propose several learning algorithms as well. The learnable class by these techniques corresponds to the class of regular tree languages. In Chapter 4we outline a recent range of attempts in Grammatical Inference to extend the learnable language classes beyond regularity and even beyond context-freeness by techniques based on syntactic observations which can be subsumed under the term 'distributional learning', and we describe learning algorithms in several settings for the tree case taking this approach. We conclude with some general reflections on the notion of learning from structural information.
This work is concerned with two kinds of objects: regular expressions and finite automata. These formalisms describe regular languages, i.e., sets of strings that share a comparatively simple structure. Such languages - and, in turn, expressions and automata - are used in the description of textual patterns, workflow and dependence modeling, or formal verification. Testing words for membership in any given such language can be implemented using a fixed - i.e., finite - amount of memory, which is conveyed by the phrasing finite-automaton. In this aspect they differ from more general classes, which require potentially unbound memory, but have the potential to model less regular, i.e., more involved, objects. Other than expressions and automata, there are several further formalisms to describe regular languages. These formalisms are all equivalent and conversions among them are well-known.However, expressions and automata are arguably the notions which are used most frequently: regular expressions come natural to humans in order to express patterns, while finite automata translate immediately to efficient data structures. This raises the interest in methods to translate among the two notions efficiently. In particular,the direction from expressions to automata, or from human input to machine representation, is of great practical relevance. Probably the most frequent application that involves regular expressions and finite automata is pattern matching in static text and streaming data. Common tools to locate instances of a pattern in a text are the grep application or its (many) derivatives, as well as awk, sed and lex. Notice that these programs accept slightly more general patterns, namely ''POSIX expressions''. Concerning streaming data, regular expressions are nowadays used to specify filter rules in routing hardware.These applications have in common that an input pattern is specified in form a regular expression while the execution applies a regular automaton. As it turns out, the effort that is necessary to describe a regular language, i.e., the size of the descriptor,varies with the chosen representation. For example, in the case of regular expressions and finite automata, it is rather easy to see that any regular expression can be converted to a finite automaton whose size is linear in that of the expression. For the converse direction, however, it is known that there are regular languages for which the size of the smallest describing expression is exponential in the size of the smallest describing automaton.This brings us to the subject at the core of the present work: we investigate conversions between expressions and automata and take a closer look at the properties that exert an influence on the relative sizes of these objects.We refer to the aspects involved with these consideration under the titular term of Relative Descriptional Complexity.
Virtuelle Umgebungen erfreuen sich in den letzten Jahren einer großen Beliebtheit und können kontinuierlich wachsende Nutzerzahlen vorweisen. Deshalb wird erwartet, dass die ohnehin große Nutzergemeinde weiterhin wächst. Dieses Wachstum stellt jedoch die Entwickler und die Betreiber von virtuellen Umgebungen vor eine Herausforderung. Die meisten heutzutage erfolgreichen virtuellen Umgebungen basieren auf einer Client-Server-Infrastruktur, in der der Server für die Verwaltung der gesamten Umgebung zuständig ist. Bei einer gleichzeitigen Inanspruchnahme durch viele Nutzer werden die serverbasierten Umgebungen jedoch massiven Skalierbarkeits- und Lastverteilungsproblemen ausgesetzt. Diese Probleme führen beispielsweise dazu, dass Nutzer Wartezeiten beim Einloggen in Kauf nehmen müssen bzw. selbst im Falle eines erfolgreichen Logins die "überfüllten" virtuellen Regionen nicht betreten dürfen. Deshalb wird in dieser Arbeit untersucht, ob eine Verbesserung der Skalierbarkeit und der Lastverteilung in virtuellen Umgebungen durch die Verwendung alternativer Infrastrukturansätze erreicht werden kann. Außerdem werden Maßnahmen zur weiteren Entlastung der Basis-Infrastruktur entwickelt. Diese Verbesserung soll zum einen dadurch erzielt werden, dass anstelle eines Servers ein Server-Verbund (Peer-to-Peer-System) als eine Art Management-Schicht agieren soll, in der jeder Knoten nur einen bestimmten Teil der virtuellen Umgebung verwaltet. Dabei wird die gewünschte Lastverteilung durch die Aufteilung der Verantwortungsbereiche auf die Knoten der Management-Schicht erreicht. Gleichzeitig entsteht aber ein Mehraufwand für die Konstruktion bzw. Erhaltung einer solchen Management-Schicht. Deshalb werden in dieser Arbeit die Vor- und Nachteile eines Infrastrukturwechsels hin zu dezentralisierten Infrastruktur-Ansätzen untersucht. Zum anderen wird eine spürbare Entlastung der Management-Schicht und somit eine Verbesserung der Skalierbarkeit und der Lastverteilung durch die Übertragung einiger Verwaltungsaufgaben an die Clients angestrebt. Zu diesen Verwaltungsaufgaben zählen die Gruppenkommunikation und das Konsistenz-Handling. Dazu wird in dieser Arbeit erforscht, inwiefern die Clients, die sich innerhalb derselben virtuellen Region befinden, selbst die Gruppenkommunikation über eine Multicast-Infrastruktur regeln können bzw. in die Wahrung der Konsistenz eines gemeinsamen Zustandes und der gemeinsam genutzten Objekte involviert werden können. Bei dem clientbasierten Konsistenz-Handling sollte vor allem auf die besonderen Interaktivitäts- und Konsistenzanforderungen, die Nutzer an die virtuellen Umgebungen stellen, geachtet werden. Dazu wird ein neues Konsistenzmodell definiert, welches die Einhaltung der strengen Interaktivitätsanforderungen erzwingt und die Konsistenz mit einer bestimmten Wahrscheinlichkeit garantieren kann.
The visualization of relational data is at the heart of information visualization. The prevalence of visual representations for this kind of data is based on many real world examples spread over many application domains: protein-protein interaction networks in the field of bioinformatics, hyperlinked documents in the World Wide Web, call graphs in software systems, or co-author networks are just four instances of a rich source of relational datasets. The most common visual metaphor for this kind of data is definitely the node-link approach, which typically suffers from visual clutter caused by many edge crossings. Many sophisticated algorithms have been developed to layout a graph efficiently and with respect to a list of aesthetic graph drawing criteria. Relations between objects normally change over time. Visualizing the dynamics means an additional challenge for graph visualization researchers. Applying the same layout algorithms for static graphs to intermediate states of dynamic graphs may also be a strategy to compute layouts for an animated graph sequence that shows the dynamics. The major drawback of this approach is the high cognitive effort for a viewer of the animation to preserve his mental map. To tackle this problem, a sophisticated layout algorithm has to inspect the whole graph sequence and compute a layout with as little changes as possible between subsequent graphs. The main contribution and ultimate goal of this thesis is the visualization of dynamic compound weighted multi directed graphs as a static image that targets at visual clutter reduction and at mental map preservation. To achieve this goal, we use a radial space-filling visual metaphor to represent the dynamics in relational data. As a side effect the obtained pictures are very aesthetically appealing. In this thesis we firstly describe static graph visualizations for rule sets obtained by extracting knowledge from software archives under version control. In a different work we apply animated node-link diagrams to code-developer relationships to show the dynamics in software systems. An underestimated visualization paradigm is the radial representation of data. Though this kind of data has a long history back to centuries-old statistical graphics, only little efforts have been done to fully explore the benefits of this paradigm. We evaluated a Cartesian and a radial counterpart of a visualization technique for visually encoding transaction sequences and dynamic compound digraphs with both an eyetracking and an online study. We found some interesting phenomena apart from the fact that also laymen in graph theory can understand the novel approach in a short time and apply it to datasets. The thesis is concluded by an aesthetic dimensions framework for dynamic graph drawing, future work, and currently open issues.
This work addresses the algorithmic tractability of hard combinatorial problems. Basically, we are considering \NP-hard problems. For those problems we can not find a polynomial time algorithm. Several algorithmic approaches already exist which deal with this dilemma. Among them we find (randomized) approximation algorithms and heuristics. Even though in practice they often work in reasonable time they usually do not return an optimal solution. If we constrain optimality then there are only two methods which suffice for this purpose: exponential time algorithms and parameterized algorithms. In the first approach we seek to design algorithms consuming exponentially many steps who are more clever than some trivial algorithm (who simply enumerates all solution candidates). Typically, the naive enumerative approach yields an algorithm with run time $\Oh^*(2^n)$. So, the general task is to construct algorithms obeying a run time of the form $\Oh^*(c^n)$ where $c<2$. The second approach considers an additional parameter $k$ besides the input size $n$. This parameter should provide more information about the problem and cover a typical characteristic. The standard parameterization is to see $k$ as an upper (lower, resp.) bound on the solution size in case of a minimization (maximization, resp.) problem. Then a parameterized algorithm should solve the problem in time $f(k)\cdot n^\beta$ where $\beta$ is a constant and $f$ is independent of $n$. In principle this method aims to restrict the combinatorial difficulty of the problem to the parameter $k$ (if possible). The basic hypothesis is that $k$ is small with respect to the overall input size. In both fields a frequent standard technique is the design of branching algorithms. These algorithms solve the problem by traversing the solution space in a clever way. They frequently select an entity of the input and create two new subproblems, one where this entity is considered as part of the future solution and another one where it is excluded from it. Then in both cases by fixing this entity possibly other entities will be fixed. If so then the traversed number of possible solution is smaller than the whole solution space. The visited solutions can be arranged like a search tree. To estimate the run time of such algorithms there is need for a method to obtain tight upper bounds on the size of the search trees. In the field of exponential time algorithms a powerful technique called Measure&Conquer has been developed for this purpose. It has been applied successfully to many problems, especially to problems where other algorithmic attacks could not break the trivial run time upper bound. On the other hand in the field of parameterized algorithms Measure&Conquer is almost not known. This piece of work will present examples where this technique can be used in this field. It also will point out what differences have to be made in order to successfully apply the technique. Further, exponential time algorithms for hard problems where Measure&Conquer is applied are presented. Another aspect is that a formalization (and generalization) of the notion of a search tree is given. It is shown that for certain problems such a formalization is extremely useful.
Synergieeffekte und Kollaboration bei e-Learning-Anwendungen in selbstorganisierenden Computernetzen
(2009)
In den letzten Jahren haben sich mehrere neue Netzklassen im Bereich der Verteilten Systeme etabliert. Diese können unter Ausnutzung von Selbstorganisationsprinzipien und verschiedener kollaborativer Aspekte viele der netzinhärenten Probleme wie Skalierbarkeit, Latenz- und Lastverteilungsbetrachtungen sowie Konsistenzwahrung entschärfen. Gleichzeitig kann die Nutzung entsprechender Prinzipien zu positiven Synergieeffekten führen, die von den verschiedenen auf diesen Netzen aufsetzten Applikationsdomänen genutzt werden können. Von besonderer Bedeutung sind diese Aspekte für die beiden neuartigen Netzklassen der Multi-Hop Adhoc-Netze (MANETs) und der globalen virtuellen Umgebungen (MMVEs). Beiden Netzklassen ist gemeinsam, dass sie aufgrund der erwähnten Problemstellungen nicht mit traditionellen verteilten Architekturen, wie zentralistischen und monolithischen Systemen, umgesetzt werden können. Hier muss ein Paradigmenwechsel hin zu dezentralen, selbstorganisierenden Systemstrukturen erfolgen, um den angesprochenen Herausforderungen zu begegnen. Die erste in dieser Arbeit untersuchte Netzklasse der MANETs zeichnet sich dadurch aus, dass sie Nutzern erlaubt, immer und überall auf Ihre Daten zugreifen zu können und mit der vor Ort vorhandenen Infrastruktur transparent zu kommunizieren. Dabei erfolgen die Daten-zugriffe vermehrt über immer kleiner werdende mobile Endgeräte, die sowohl aufgrund ihrer inhärenten Mobilität als auch ihrer eingeschränkten Ressourcen daran angepasste Netzstrukturen erfordern. Die neuartige Netzklasse der MMVEs dagegen soll Dateninhalte in einem dreidimensionalen Rahmen und damit nativ und intuitiver als die vorherrschende zweidimensionale Darstellung, wie z.B. im Internet, präsentieren. Der Datenzugriff erfolgt hier meist über eine virtuelle Benutzerrepräsentation " einen Avatar. MMVEs basieren zwar im Vergleich zu MANETs in der Regel auf physisch verlässlichen Netzen, benötigen aber aufgrund der massiven Verteilung und der großen Nutzerzahlen neue Netzwerkarchitekturen. Die Anwendungsdomäne e-Learning eignet sich in diesem Zusammenhang besonders gut für wissenschaftliche Untersuchungen, da hier eine ähnliche Entwicklung beobachtbar ist, wie bei den eingangs erwähnten Netzklassen. Genauso wie mobile Endgeräte immer kleiner und ubiquitär verfügbar werden und das Internet praktisch an jedem Ort der Welt mit hoher Bandbreite nutzbar ist, finden e-Learning Inhalte immer mehr Einzug in das tägliche Leben. Während sie früher nur eine vernachlässigbare Ergänzung zu etablierten Schulungsformen darstellten, die mehr oder weniger invasiv und starr zentral administriert wurde, steigt Ihre Bedeutung besonders im Zusammenhang mit neuen Zugangsformen täglich. Besonders das Bedürfnis an Schulen oder Universitäten sowie bei der innerbetrieblichen Aus- und Weiterbildung, immer und überall verteilt, nativ und transparent auf entsprechende Lehr- und Lerninhalte zugreifen zu können, steigt mit dem wachsenden und teilweise rein wirtschaftlich bedingten Bedarf nach einer qualitativ hohen, kontinuierlichen gesellschafts- und technikdurchdringenden Grund- und Weiterbildung. Die geforderte Transparenz und Ubiquität kann für die angesprochene Anwendungsdomäne dadurch erreicht werden, dass spezielle, auf die neuartigen verteilten Netzstrukturen abgestimmte, Applikationen entwickelt werden, die die netzinhärenten Selbstorganisations-prinzipien explizit ausnutzen. Eine wichtige Fragestellung in diesem Zusammenhang ist, welche Auswirkungen ein solcher Paradigmenwechsel auf die Qualität der Wissens-vermittlung und der Inhalte hat. Erste Evaluationen mit prototypischen Applikationen haben gezeigt, dass dieser Wechsel problemlos möglich ist. Dabei spiegeln auftretende Synergie-effekte die Abbildung auf soziale Netze wieder, die beiden Aspekten inhärent zugrunde liegt und einen Mehrwert erzeugen, der die dabei auftretenden technischen Herausforderungen und Probleme relativiert. Entsprechende Effekte lassen sich sogar noch weiter verstärken, indem kollaborative Aspekte sowohl auf Applikationsebene als auch in den darunter liegenden Basisstrukturen ausgenutzt werden. Die vorliegende Arbeit soll diese Annahmen durch adäquate Beispiele aus beiden Bereichen (MANETs und MMVEs) aus verschiedenen Perspektiven beleuchten und anhand von beispielhaften Anwendungen und darauf aufbauende Evaluationen den Synergiegewinn von e-Learning Applikationen und mögliche kollaborative Aspekte in diesem Umfeld aufzeigen.
In dieser Arbeit wird ein Middlewaremodell für Anwendungen in mobilen ad-hoc Netzwerken vorgestellt. Der primäre Fokus liegt dabei auf Netzen, die auf Basis von mobilen Endbenutzergeräten wie PDAs, PocketPCs oder Smartphones gebildet werden und die über eine drahtlose Kommunikationstechnik wie WLAN oder Bluetooth verfügen. Zur Identifizierung der Ansprüche an eine Middleware in diesen Netzen wurden Anwendungen aus dem universitären Umfeld untersucht. Da die Kommunikation in drahtlosen Netzen nicht immer so transparent wie in drahtgebundenen Infrastrukturnetzen erfolgen kann, enthält die Middleware ein Kommunikationsframework, welches die Adaption und auch die Kombination von Kommunikationsmechanismen ermöglicht. Neben der direkten Auslieferung von Nachrichten werden auch Mechanismen zur sukzessiven Weitergabe von Nachrichten, die so genannte Store-and-Forward Kommunikation, angeboten. Hier steht insbesondere die Weitergabe von Informationen im Vorbeigehen (En-Passant) im Vordergrund. Die Komponenten der Middleware und darauf basierenden Applikationen werden als interagierende mobile Objekte modelliert. Die Interaktion dieser Objekte erfolgt aufgrund der Dynamik der mobilen ad-hoc Netze ereignisorientiert. Sowohl die Interaktion, als auch die Adaption und Wahl von Kommunikationsmechanismen erfolgt auf Basis von Informationen über das direkte Umfeld, Applikationswissen über das Netzwerk und Erfahrungen aus der Vergangenheit. Diese Informationen, die von Objekten verbreitet und gesammelt werden können, werden als Spuren bezeichnet. Da eine Aufhebung der Transparenz der Middlewarekomponenten einen höheren Entwicklungsaufwand bedeutet, wird eine Realisierung der Objektinteraktion in Objektrepräsentanten vorgeschlagen. Objektrepräsentanten ermöglichen die Kommunikation mit entfernten Objekten, das lokale Verwalten von Informationen über diese Objekte und schließlich die Repräsentierung von Objekten ohne reale Objektinstanz. Objekte ohne Objektinstanz werden verwendet, um Gerätegruppen mit bestimmten Eigenschaften zusammenzufassen, beispielsweise Objekte an einem bestimmten geographischen Ort. Somit ist auch das Wissen über geographische Orte und deren Identifizierung ein wichtiger Aspekt des Modells. Aufgrund der Anwendungsuntersuchungen ist sukzessive ein Middlewareprototyp entstanden, der in eine Simulationsumgebung für mobile ad-hoc Netze integriert ist. Die Umgebung erlaubt neben der reinen Simulation mobiler ad-hoc Netze und der zu untersuchenden Anwendung auch die Integration realer Geräte und die Ausführung der Anwendungen auf realen Geräten. Somit konnte, neben einer simulativen Untersuchung, auch eine praktische Evaluation der Anwendungen in Feldversuchen durchgeführt werden.
Diese Arbeit stellt eine einheitliche Workbench zur Entwicklung von mobilen Anwendungen in multihop Ad-Hoc-Netzwerken vor. Die einheitliche Workbench besteht aus drei Bausteinen: einem Simulator für diese Netzwerke, einer hybriden Emulationsumgebung für mobile multihop Ad-Hoc-Netzwerke und einer Ausführungsplattform für Anwendungen auf mobilen Geräten. Anwendungen können bereits im Simulator vollständig implementiert und evaluiert werden. Der entstandene Code kann unverändert sowohl im Emulationsteil als auch auf der Ausführungsplattform für mobile Geräte eingesetzt werden. Im passenden dreistufigen Entwicklungsprozeß wird die Anwendung im Simulator implementiert und getestet, bevor sie -- zusammen mit einer graphischen Oberfläche -- in der hybriden Emulationsumgebung weiter evaluiert und optimiert wird. Zuletzt erfolgt die Erprobung auf mobilen Geräten im Feldversuch. Mehrere tausend bis zehntausend mobile Geräte können in der Workbench durch die Beschränkung auf die topologischen Aspekte des Ad-Hoc-Netzwerks und eine besondere Bewegungsmodellabstraktion, die die besonders effiziente Berechnung der Bewegungs- und Konnektivitätsdaten der Geräte ermöglicht, effizient simuliert werden. Die Vorausberechnung und Wiederverwendung dieser Daten ist möglich. Simulationen können in Echtzeit detailliert visualisiert werden, wobei die Art der Visualisierung und das Ausgabeformat vom Benutzer definiert werden können. Die Workbench und der Softwareentwicklungsprozeß für Anwendungen in mobilen multihop Ad-Hoc-Netzwerken werden anhand einer Fallstudie erprobt. Dabei werden die Erfahrungen bei der Implementierung einer Middleware für Ad-Hoc-Anwendungen sowie bei der Entwicklung einer selbstorganisierenden Auktionsanwendung aufgezeigt.
Die Geschichte verteilter Systeme und Anwendungen hat die unterschiedlichsten Technologien hervorgebracht: Client-Server-Architekturen, Peer-To-Peer-Netzwerke und Komponentensysteme sind nur einige Vertreter. Die vorliegende Arbeit ist im Bereich der Middleware-Architekturen angesiedelt, einem zur Zeit sehr stark beachteten Zweig der verteilten Anwendungen. Als Mittler zwischen den Anwendungen auf der einen Seite sowie Datenbanken, eMail-Systemen oder weiterer Servern auf der anderen Seite, schlägt sie die Brücke zu heterogenen IT-Landschaften. Sie verbirgt Details und Änderungen dieser IT-Umgebungen und schafft gleichzeitig einen transparenten Zugriff auf sie. Die Forschung hat viele Technologien im Middleware-Umfeld hervorgebracht und setzt bei den Zielen unterschiedliche Schwerpunkte. Eine Sicht auf die Middleware hat den Entwickler im Fokus und soll ihn bei der Erstellung von Anwendungen und Lösungen unterstützen. Aus diesem Grund stehen hier die Schnittstellen zum Server und zur Server-Infrastruktur sowie die Einbettung der Dienste in die Middleware im Vordergrund. Der interne Aufbau sowie die inneren Datenflüsse der Middleware dienen nur der Erfüllung dieser Ziele. Eine andere Sichtweise stellt den inneren Aufbau in den Fokus der Forschung. Hier ist das Ziel die Schaffung von flexiblen und erweiterbaren Server-Strukturen sowie die Effizienz von internen Abläufen und Datenflüssen. Damit ist eine einfache Anpassung an verschiedene Einsatzumgebungen sowie die Fähigkeit, auf die Leistungsmerkmale von Clients individuell eingehen zu können, möglich. Die im Rahmen dieser Arbeit entstandene Middleware-Architektur "Smart Data Server (SDS)" setzt Konzepte um, die beide Sichtweisen miteinander kombiniert. Ein Schwerpunkt neben der Entwicklung neuer Konzepte, liegt in der praktischen Anwendbarkeit der entwickelten Middleware. Die vorliegende Arbeit zeigt, dass der Smart Data Server die Praxistauglichkeit seiner Konzepte unter realen Bedingungen unter Beweis stellen kann und zeigt gleichzeitig, welche Konstrukte für den praktischen Einsatz tatsächlich notwendig sind. Ein zweiter Schwerpunkt liegt in der Entwicklung von Mechanismen zur Abarbeitung von streamingfähigen Anfragen. Üblicherweise folgt auf die Übermittlung von Anfragen an einen Server zunächst die Berechnung einer Antwort und anschließend deren Rücktransport. Bei Streaming-Anfragen ist neben der Übermittlung von Anfrageparametern ein kontinuierlicher und in seiner Dimension nicht beschränkter Datenstrom Bestandteil der Anfrage. Der Server startet seine Berechnungen wenn möglich schon vor dem Ende der Datenübermittlung und liefert schon bei Vorliegen von Teilergebnissen diese an den Client. Der benötigte Bedarf an Speicherplatz im Server kann so optimiert werden, da nur so viele Daten der Anfrage im Server vorgehalten werden müssen wie zur Berechnung tatsächlich notwendig sind und nicht etwa die gesamte Anfrage. Die Entwicklung eines Streaming-Mechanismuses muss entsprechende Möglichkeiten in der Anfragestruktur sowie in der Architektur der Middleware vorsehen. Der Smart Data Server schafft mit der Einführung einer streamingfähigen Anfragestruktur die Voraussetzung für die Verarbeitung solcher Anfragen. Zusätzlich muss eine Server-Architektur geschaffen werden, die das Abarbeiten von Streaming-basierten Anfragen unterstützt. Hier liegt der dritte Schwerpunkt der Arbeit: die Schaffung einer flexiblen und erweiterbaren Server-Struktur sowie die Effizienz von internen Abläufen und Datenflüssen unter Berücksichtigung der Anforderung einer streamingfähigen Anfragebearbeitung. Diese Anforderungen werden mit der neu entwickelten Technologie der inneren Workflow-Programme erfüllt. Innere Workflow-Programme repräsentieren Netzwerke von hochgradig unabhängigen Serverkomponenten. Durch die Umgestaltung dieser Netze sind neue Serverstrukturen möglich, um neuen Einsatzbedingungen angepasst werden zu können. Neben diesem statischen Netzwerk von Server-Komponenten kann zur Laufzeit eine Pipeline zur Abarbeitung von Datenströmen aufgebaut werden, mit der dann letztendlich die Streamingfähigkeit des Servers hergestellt wird.
