Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
76 results
Search Results
Item Open Access Integration von Data Mining und Online Analytical Processing : eine Analyse von Datenschemata, Systemarchitekturen und Optimierungsstrategien(2003) Schwarz, Holger; Mitschang, Bernhard (Prof. Dr.-Ing. habil.)Die technischen Möglichkeiten, Daten zu erfassen und dauerhaft zu speichern, sind heute so ausgereift, dass insbesondere in Unternehmen und anderen Organisationen große Datenbestände verfügbar sind. In diesen Datenbeständen, häufig als Data Warehouse bezeichnet, sind alle relevanten Informationen zu den Organisationen selbst, den in ihnen ablaufenden Prozessen sowie deren Interaktion mit anderen Organisationen enthalten. Vielfach stellt die zielgerichtete Analyse der Datenbestände den entscheidenden Erfolgsfaktor für Organisationen dar. Zur Analyse der Daten in einem Data Warehouse sind verschiedenste Ansätze verfügbar und erprobt. Zwei der wichtigsten Vertreter sind das Online Analytical Processing (OLAP) und das Data Mining. Beide setzen unterschiedliche Schwerpunkte und werden bisher in der Regel weitgehend isoliert eingesetzt. In dieser Arbeit wird zunächst gezeigt, dass eine umfassende Analyse der Datenbestände in einem Data Warehouse nur durch den integrierten Einsatz beider Analyseansätze erzielt werden kann. Einzelne Fragestellungen, die sich aus diesem Integrationsbedarf ergeben werden ausführlich diskutiert. Zu den betrachteten Fragestellungen gehört die geeignete Modellierung der Daten in einem Data Warehouse. Bei der Bewertung gängiger Modellierungsansätze fließen insbesondere die Anforderungen ein, die sich durch den beschriebenen Integrationsansatz ergeben. Als Ergebnis wird ein konzeptuelles Datenmodell vorgestellt, das Informationen in einer Weise strukturiert, die für OLAP und Data Mining gleichermaßen geeignet ist. Im Bereich der logischen Modellierung werden schließlich diejenigen Schematypen identifiziert, die die Integration der Analyseansätze geeignet unterstützen. Im nächsten Schritt sind die für Data Mining und OLAP unterschiedlichen Systemarchitekturen Gegenstand dieser Arbeit. Deren umfassende Diskussion ergibt eine Reihe von Defiziten. Dies führt schließlich zu einer erweiterten Systemarchitektur, die die Schwachstellen beseitigt und die angestrebte Integration geeignet unterstützt. Die erweiterte Systemarchitektur weist eine Komponente zur anwendungsunabhängigen Optimierung unterschiedlicher Analyseanwendungen auf. Ein dritter Schwerpunkt dieser Arbeit besteht in der Identifikation geeigneter Optimierungsansätze hierfür. Die Bewertung der Ansätze wird einerseits qualitativ durchgeführt. Andererseits wird das Optimierungspotenzial der einzelnen Ansätze auch auf der Grundlage umfangreicher Messreihen gezeigt.Item Open Access Scalable computer network emulation using node virtualization and resource monitoring(2011) Maier, Steffen Dirk; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c.)Ongoing development of computer network technology requires new communication protocols on all layers of the protocol stack to adapt to and to exploit technology specifics. The performance of new protocol implementations has to be evaluated before deployment. Computer network emulation enables the execution of real unmodified protocol implementations within a configurable synthetic environment. Since network properties are reproduced synthetically, emulation supports reproducible measurement results for wired and wireless networks. Meaningful evaluation scenarios typically involve a large number of communicating nodes. Reproducing the network properties of the medium access control layer can be accomplished efficiently on cheap common off the shelf computers and allows to evaluate network protocols, transport protocols, and applications. However, meaningful emulation scenario sizes often require more nodes than affordable computers. To scale the number of nodes in an emulation scenario beyond the available computers, we discuss approaches to virtualization and operating system partitioning. Focusing on the latter, we argue for virtual protocol stacks, which provide an extremely lightweight node virtualization enabling the execution of multiple instances of software to be evaluated on each physical computer. To connect virtual nodes on the same and on different computers, we design and implement a highly efficient software communication switch. A centralized emulation control component distributes dynamic network property updates which result from node mobility for instance. To handle the large number of nodes and thus increased updates, we propose a hierarchical control where the central component delegates updates to sub-components distributed over the computers of an emulation system. Extensive evaluations show the scalability of our virtualized network emulation system. Virtual nodes executed on the same computer share its limited resources. Hosting too many virtual nodes on the same computer may lead to resource contention. This can cause unrealistic measurement results and is thus undesirable. Discussing different approaches to handle resource contention, we argue for detection and recovery. We define quality criteria that allow the detection of resource contention. In order to observe those quality criteria during emulation experiments, we propose a highly lightweight monitoring approach. Our monitoring is based on instrumenting an operating system kernel and observing basic resource scheduling events. This enables the detection of even peak resource usage within a split second. Thorough evaluations demonstrate the effectiveness of quality criteria and monitoring as well as the negligible overhead of our monitoring approach.Item Open Access Investigating dynamics by multilevel phase space discretization(2006) Fundinger, Danny Georg; Levi, Paul (Prof. Dr.)The subject of the thesis is the numerical investigation of dynamical systems. The aim is to provide approaches for the localization of several topological structures which are of vital importance for the global analysis of dynamical systems, namely, periodic orbits, the chain recurrent set, repellers, attractors and their domains of attraction as well as stable, unstable and connecting manifolds. The techniques introduced do not require any a priori knowledge about a system, and are also not restricted by the stability of the solution. Furthermore, they can generally be applied to a wide range of dynamical systems. Two theoretical concepts are considered to be at the center of the research - symbolic analysis and the RIM method. The underlying basic approach for both of them is multilevel phase space discretization. This means that a part of the phase space, the area of investigation, is subdivided in a finite number of sets. Then, instead of each point of the phase space, only these sets are subject of further analysis. The main target of every method proposed is to find those sets which contain parts of the solution and subdivide them into smaller parts until a desired accuracy is reached. In case of symbolic analysis, a directed graph is constructed which represents the structure of the state space for the investigated dynamical system. This graph is called the symbolic image of the focused system and can be seen as an approximation of the system flow. The theoretical background regarding the symbolic image graph as well as the constructive methods applied on it were already described in a series of works by G. Osipenko. In this work, strategies are introduced for a practical application. This requires the extension of the theoretical concepts and the development of appropriate algorithms and data structures. In practice, it turned out that these aspects are essential cornerstones for the usability of the discussed methods. Also some sophisticated tunings of the basic methods are proposed in order to extent the field of practical investigation. Although symbolic analysis can be seen as the main stimulation of this work, the investigation was not limited to it. Indeed, several shortcomings regarding the solution of some problems can be observed if the method is applied in practice. This led to the development of the RIM method. The core intention of the method is to solve the root finding problem. The standard approach toward this task is the application of an iteration scheme based on the Newton method. However, it has shown that such Newton schemes have several structural disadvantages which are especially crucial in the context of the fields of investigation which are relevant to this work. The RIM method proposes an alternative approach which does not require the application of any Newton-like method. Numerical case studies revealed that in several nontrivial scenarios the RIM method provides better results than both, symbolic analysis as well as Newton-based methods. Two applications of the RIM method for the investigation of dynamical systems are provided. One of them is the detection of periodic points. The other is the computation of stable manifolds. The proposed methods contribute not only to the direct investigation and simulation of specific dynamical processes but also to the research in the field of dynamical system theory in general. This is due to the fact that progress in theory depends to a large extent on the observation and investigation of phenomenons. These phenomenons can often only be revealed, analyzed and verified by numerical experiments. The presented numerical case studies give some concrete examples for the application of the methods. Hereby, the dynamical models are taken from different fields of scientific research, like geography, biology, meteorology, or physics.Item Open Access Interaktion und Koordination in Multiagentensystemen(2001) Muscholl, Klaus Matthias; Levi, Paul (Prof. Dr.)Das Zusichern von kohärentem Verhalten in Multiagentensystemen ist durch die inhärente Verteiltheit des Systems, als auch durch den unabhängigen Entwurf der Agenten bei offenen Systemen, ein weithin ungelöstes Problem. In der vorliegenden Dissertation wird ein entwurfstechnischer Ansatz vorgestellt, welcher mit Hilfe von Interaktionsverfahren Kohärenz sicherstellt. Interaktionsverfahren werden dabei durch das Interaktionsmodell beschrieben. Die Grundidee besteht darin, daß Agenten durch die Teilnahme an einer Interaktion einen Teil ihrer Autonomie an das die Interaktion beschreibende Verfahren und seine Entscheidungsmechanismen abtreten und sich ihm unterordnen. Dies wird dadurch erzielt, daß ein Interaktionsverfahren die Koordination der an ihn übertragenen Kompetenzen übernimmt. Ein Interaktionsverfahren ist somit gegenüber den teilnehmenden Agenten weisungsbefugt. Um an Interaktionsverfahren teilnehmen zu können, muß ein Agent eine Schnittstelle unterstützen, welche es dem Interaktionsverfahren ermöglicht, auf die an ihn übertragen Kompetenz zuzugreifen und die kollektiv getroffenen Entscheidungen im einzelnen durchzusetzen. Hierzu sind unabhängig von Interaktionsverfahren für einen Anwendungsbereich Dienstklassen definiert, welche Schnittstellen zu Fähigkeiten eines Agenten bilden. Ein Interaktionsverfahren definiert das Ablaufschema einer Interaktion. Das Ablaufschema abstrahiert von Agenten in Form von Rollen. Das Schema ist in einzelne Phasen strukturiert und definiert, wie die Rollen untereinander interagieren. Rollen sind die kleinsten aktiven Einheiten des Interaktionsmodells und nur innerhalb einer Phase gültig. Agenten, welche an einem Interaktionsverfahren teilnehmen, werden durch Rollen gesteuert, die ihnen in den jeweiligen Phasen zugewiesen werden. Die vorliegende Arbeit ist Bestandteil des Architekturkonzepts von Robotersystemen im Comros-Projekt.Item Open Access Optimierung datenintensiver Workflows: Konzepte und Realisierung eines heuristischen, regelbasierten Optimierers(2011) Vrhovnik, Marko; Mitschang, Bernhard (Prof. Dr.-Ing. habil.)Um die Modellierung datenintensiver Workflows, die große relationale Datenmengen verarbeiten, zu vereinfachen, wurden Workflowbeschreibungssprachen, wie BPEL, von führenden Herstellern von Workflow- und Datenbankmanagementsystemen um SQL-Funktionalität erweitert. Dadurch müssen Datenverarbeitungsoperationen, wie SQL-Anweisungen oder Aufrufe benutzerdefinierter Prozeduren, nicht mehr in Web-Services gekapselt werden, sondern können direkt auf der Workflowebene definiert werden. Daraus resultiert eine neue Möglichkeit der Anfrageoptimierung, die existierende Optimierungsansätze in Datenbanksystemen ergänzt: Suboptimal modellierte Datenverarbeitungsoperationen lassen sich in einer Workflowbeschreibung unter Verwendung von Restrukturierungsregeln derart transformieren, dass sie von einem Workflow- bzw. Datenbankmanagementsystem wesentlich effizienter ausgeführt werden können. In dieser Doktorarbeit werden Konzepte zur Realisierung eines heuristischen, regelbasierten Optimierers für datenintensive Workflows vorgestellt. Der Optimierer wendet eine Regelbasis gemäß einer wohldefinierten Kontrollstrategie auf eine interne Repräsentation für datenintensive Workflows, dem sogenannten Prozessgraphenmodell (PGM), an, um die Datenverarbeitung eines datenintensiven Workflows zu optimieren. PGM erlaubt eine effiziente und sprachunabhängige Definition und Anwendung der Restrukturierungsregeln und unterstützt somit eine Optimierung von Datenverarbeitungsoperationen, die in unterschiedlichen Beschreibungssprachen definiert sein können. Die Regelbasis enthält Restrukturierungsregeln, die auf existierenden und neuen Optimierungsstrategien beruhen. Insbesondere nutzen die Restrukturierungsregeln das Wissen über Abhängigkeiten in einer Workflowbeschreibung aus, um die darin eingebetteten Datenverarbeitungsoperationen unter Beibehaltung der ursprünglichen Ausführungssemantik eines datenintensiven Workflows zu optimieren. Die Kontrollstrategie bestimmt, welche Restrukturierungsregeln in welcher Reihenfolge auf welche Teile einer Workflowbeschreibung angewendet werden, um zum einen das Optimierungspotential eines datenintensiven Workflows umfassend zu nutzen und zum anderen die Korrektheit der Regelanwendungen sicherzustellen. Die ausführliche Beschreibung des Prozessgraphenmodells, der Regelbasis und der Kontrollstrategie stehen im Mittelpunkt dieser wissenschaftlichen Abhandlung. Des Weiteren wird eine prototypische Implementierung des Optimierungsansatzes vorgestellt, welche dessen praktische Einsatzfähigkeit unterstreicht. Schließlich wird die Effektivität der einzelnen Restrukturierungsregeln mithilfe verschiedener Messszenarien untersucht. Dabei wird gezeigt, dass durch Anwendung der Restrukturierungsregeln Leistungssteigerungen in mehreren Größenordnungen erreicht werden können.Item Open Access Supporting multi-tenancy in Relational Database Management Systems for OLTP-style software as a service applications(2015) Schiller, Oliver; Mitschang, Bernhard (Prof. Dr.-Ing. habil.)The consolidation of multiple tenants onto a single relational database management system (RDBMS) instance, commonly referred to as multi-tenancy, turned out being beneficial since it supports improving the profit margin of the provider and allows lowering service fees, by what the service attracts more tenants. So far, existing solutions create the required multi-tenancy support on top of a traditional RDBMS implementation, i. e., they implement data isolation between tenants, per-tenant customization and further tenant-centric data management features in application logic. This is complex, error-prone and often reimplements efforts the RDBMS already offers. Moreover, this approach disables some optimization opportunities in the RDBMS and represents a conceptual misstep with Separation of Concerns in mind. For the points mentioned, an RDBMS that provides support for the development and operation of a multi-tenant software as a service (SaaS) offering is compelling. In this thesis, we contribute to a multi-tenant RDBMS for OLTP-style SaaS applications by extending a traditional disk-oriented RDBMS architecture with multi-tenancy support. For this purpose, we primarily extend an RDBMS by introducing tenants as first-class database objects and establishing tenant contexts to isolate tenants logically. Using these extensions, we address tenant-aware schema management, for which we present a schema inheritance concept that is tailored to the needs of multi-tenant SaaS applications. Thereafter, we evaluate different storage concepts to store a tenant’s tuples with respect to their scalability. Next, we contribute an architecture of a multi-tenant RDBMS cluster for OLTP-style SaaS applications. At that, we focus on a partitioning solution which is aligned to tenants and allows obtaining independently manageable pieces. To balance load in the proposed cluster architecture, we present a live database migration approach, whose design favors low migration overhead and provides minimal interruption of service.Item Open Access Contributions to low energy consumption in digital circuits(2000) Bühler, Markus; Baitinger, Utz G. (Prof. Dr.-Ing)After bipolar, static PMOS, and NMOS technologies have been widely replaced by static CMOS, static current has practically disappeared in digital circuits. Thus, the problem of power consumption was thought to be solved. However, with increasing integration densities and operation frequencies, combined with the advent of complex portable devices, design for low power has regained its importance as the third design goal, beside delay and area consumption. But in contrast to the past, today, dynamic power consumption is dominant by far. The domain of low power design can be divided into two major subdomains: power estimation and actual circuit design for low power, the latter including all efforts for power optimization and low power synthesis. In this thesis, specific aspects of both subdomains are treated on different levels. The design aspect is covered by an investigation of suitable circuit techniques for a novel, 3D, T-gate, SOI technology. It was found that DPL fits best the structural requirements of this technology but consumes 50 more power than static CMOS. The consequences are discussed in the text. The main focus of this thesis is put on power estimation techniques on gate level. A novel, set based simulation method is presented and extended for real delay gate models (RDM). Several further optimization methods are proposed. It is shown that the RDM extension can also be applied to bitparallel logic simulators. As a last extension the set based approach is combined with probabilistic simulation methods, thus making it possible to take into account signal correlations during probabilistic estimation.Item Open Access Key distribution schemes for resource-constrained devices in wireless sensor networks(2007) Wacker, Arno Rüdiger; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c.)Wireless sensor networks based on highly resource-constrained devices require symmetric cryptography in order to make them secure. Integral to this is the exchange of unique symmetric keys between two devices. In this dissertation, we propose three novel decentralized key distribution schemes that guarantee the confidentiality of a key exchange even if an attacker has compromised some of the devices in the network. Our first key distribution scheme -- the basic key distribution scheme -- guarantees the confidentiality of any new established key in case there are only eavesdropping attacker and no device failures present. Our second scheme -- the fault-tolerant key distribution scheme -- extends the basic scheme so that also more powerful attackers and device failures can be handled. Our third proposed key distribution scheme -- the extended key distribution scheme -- is also based on the basic scheme but further optimized in terms of memory consumption and network traffic. A central objective of all key distribution scheme designs was to minimize resource consumption on the individual devices. We evaluate the resource requirements of our schemes in terms of attacker resilience, memory requirements, and network traffic both through theoretical analysis and through simulations.Item Open Access Algorithmische Aspekte der Fluid-Struktur-Wechselwirkung auf kartesischen Gittern(2007) Brenk, Markus; Bungartz, Hans-Joachim (Prof. Dr.)In vielen physikalischen Systemen und technischen Anwendungen spielen Fluid-Struktur-Wechselwirkungen eine wesentliche Rolle. Die Wechselwirkung von Fluiden und flexiblen Strukturen stellt ein gekoppeltes Problem dar, bei dem die Bewegung eines Fluides und einer Struktur über die so genannte nasse Oberfläche (Kopplungsoberfläche) der Struktur bidirektional gekoppelt sind. So sind Windlasten an Gebäuden und Brücken, das Aufblasen von Airbags, das Öffnen von Fallschirmen, der Blutfluss in einer Ader oder die Strömung zwischen den Lamellen eines Autoreifens Beispiele für diese Art der Kopplung. Bei der Untersuchung von Fluid-Struktur-Wechselwirkungen ist die numerische Simulation ein unerlässliches Hilfsmittel. Oft werden diese Simulationen durch so genannte partitionierte Ansätzen realisiert. Diese sind dadurch gekennzeichnet, dass getrennte und für die einzelnen Teilprobleme konzipierte und angepasste Programme zur Berechnung der Strömungen und der Strukturbewegungen bzw. -verformungen eingesetzt werden -- im Gegensatz zu so genannten monolithischen Ansätzen, bei denen alle Teilprobleme gemeinsam diskretisiert und in einem Programm behandelt werden. Bei partitionierten Ansätzen können Teile der Berechnungen mit bewährten und für den jeweiligen Teilaspekt am besten geeigneten Softwarelösungen erfolgen. Damit ist jedoch eine zusätzliche Programmkomponente erforderlich, die den Ablauf der gekoppelten Simulation steuert und den Austausch der Daten zwischen den Simulationsprogrammen ermöglicht und die somit einen integralen Bestandteil partitionierter Ansätze darstellt. Dies zeigt deutlich, dass sich bei der Simulation von Fluid-Struktur-Wechselwirkungen mit partitionierten Ansätzen, neben den ingenieurwissenschaftlichen Herausforderungen (wie bspw. dem Lösen konkreter Problemstellungen) und den mathematischen Herausforderungen (wie bspw. dem Sicherstellen von Konvergenz und Robustheit), insbesondere auch softwaretechnische und damit informatische Herausforderungen ergeben. Die vorliegende Arbeit befasst sich schwerpunktmäßig mit den resultierenden Fragestellungen zur Steuerung der Kopplung, zur Verknüpfung der in den Programmen unterschiedlichen geometrischen Darstellungen der nassen Oberfläche und zum Austausch der kopplungsrelevanten Daten. Die physikalische Beschreibung des Fluid-Struktur-Wechselwirkungsproblems fordert die Erfüllung von Gleichgewichtsbedingungen auf der Kopplungsoberfläche zu jedem Zeitpunkt. Für partitionierte Ansätze existieren je nach Anwendungsfall unterschiedliche Strategien und Methoden zum Austausch der Kopplungsdaten und zur Steuerung der Kopplung in der Zeit, um diese Gleichgewichte zwischen den getrennten Simulationen sicherzustellen. Dies erfordert eine Softwarelösung zur Kopplung der Simulationsprogramme, die neben einer einfachen und mit geringem Aufwand durchzuführenden Anpassung der Programme und einer flexiblen Möglichkeit zur Steuerung der Kopplung, eine Lösung zum Transfer der kopplungsrelevanten Daten -- zwischen den auf unterschiedlichen Diskretisierungen und Datenstrukturen aufbauenden Repräsentationen der Kopplungsober Fläche in den Simulationsprogrammen -- bietet. Dieser Transfer von Kopplungsdaten zwischen den verschiedenen Oberflächenrepräsentationen kann durch die Einbettung in eine übergeordnete Geometrierepräsentation wirkungsvoll unterstützt werden. Hierfür bieten sich insbesondere hierarchisch-strukturierte Zerlegungen des Raumes durch kartesische Volumenelemente (z. B. Oktalbäume) als laufzeit- und speichereffiziente Lösung an. Diesem Effizienz-Gedanken folgend, stellt sich die Frage, ob diese strukturierten kartesischen Zerlegungen des Raumes nicht direkt als Basis für die Diskretisierung des Strömungsgebietes bei der Simulation von Fluid-Struktur-Wechselwirkungen genutzt werden können. Die Untersuchung kartesischer Diskretisierungen im Kontext der Fluid-Struktur-Wechselwirkung bildet, neben den Fragestellungen der Realisierung der Kopplung den zweiten Schwerpunkt dieser Arbeit. Es werden entsprechende Methoden vorgestellt, untersucht und insbesondere durch die dreidimensionale Simulation des Transportes von Partikeln in Mikroströmungen validiert.Item Open Access Optimized information discovery in structured peer-to-peer overlay networks(2011) Memon, Faraz; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c.)Peer-to-peer (P2P) overlay networks allow for efficient information discovery in large-scale distributed systems. Although point queries are well supported by current P2P systems - in particular systems based on distributed hash tables (DHTs) -, providing efficient support for more complex queries remains a challenge. Therefore, the goal of this research is to develop methodologies that enable efficient processing of complex queries, in particular processing of multi-attribute range queries, over DHTs. Generally, the support for multi-attribute range queries over DHTs has been provided either by creating an individual index for each data attribute or by creating a single index using the combination of all data attributes. In contrast to these approaches, we propose to create and modify indices using the attribute combinations that dynamically appear in multi-attribute range queries in the system. In order to limit the overhead induced by index maintenance, the total number of created indices has to be limited. Thus, one of the major problems is to create a limited number of indices such that the overall system performance is optimal for multi-attribute range queries. We propose several index recommendation algorithms that implement heuristic solutions to this NP-hard problem. Our evaluations show that these heuristics lead to a close-to-optimal system performance for multi-attribute range queries. The final outcome of this research is an adaptive DHT-based information discovery system that adapts its set of indices according to the dynamic load of multi-attribute range queries in the system. The index adaptation is carried out using a four-phase index adaptation process. Our evaluations show that the adaptive information discovery system continuously optimizes the overall system performance for multi-attribute range queries. Moreover, compared to a non-adaptive system, our system achieves several orders of a magnitude improved performance.