Skalierbares schlüssel-basiertes Routing in verteilten Systemen ist eine Methode zur Weiterleitung von Nachrichten zu den für die Partition verantwortlichen Maschinen. Diese Technik findet Verwendung in Key-Value Speichersystemen, Content Distribution Networks oder auch beim Media Streaming. Einer der Gründe für die Verbreitung ist die Einfachheit der Routingabstraktion, bei welcher der Entwickler sich nicht um die Details des Gruppenmanagements oder Datenreplikation kümmern muss. Auf der anderen Seite sind die meisten schlüssel-basierten Routingverfahren optimistische Verfahren, bei denen der Datenzugriff keine strenge Konsistenz bietet. In dieser Arbeit präsentieren wir das System Recode mit dem schlüssel-basierten Routingabstraktion routecast, welches eine strengere Zugriffssemantik ermöglicht. Dabei garantiert routecast, dass Nachrichten eines bestimmten Schlüssels in der gleichen Reihenfolge an alle Replikate geliefert werden. Mit Hilfe dieser strengeren Garantien können auch Anwendungen wie Koordinations- oder Metadatendienste bzw. konsistente Speichersysteme das schlüssel-basierte Routing verwenden. Recode ist außerdem rekonfigurierbar bei Veränderungen der zur Verfügung stehenden Maschinen sowie bei Auslastungsänderung. Es ist ein komplett dezentralisiertes System und enthält damit keinen single-point of failure oder Systemengpass. Die drei Hauptbeiträge der Arbeit sind 1) die Abstraktion der Gruppenkommunikation unter Verwendung von Primary/Backup mit Leases für ein failover des Primary, 2) die Entwicklung und die Algorithmen der routcast-Primitive, 3) Mechanismen zur atomaren Rekonfiguration des dezentralen Schlüsselraumes. Um die Einfachheit unseres Ansatzes zu betonen, beschreiben wir außerdem drei verschiedene Anwendungen aufbauend auf Recode. Abschließend zeigen wir durch die Evaluation von Recode in einer Cluster-Umgebung die Leistungsfähigkeit. / Scalable key-based routing in distributed systems, where a mes- sage is forwarded towards a machine responsible for a partition in a large key space, has been used in many services such as key-value stores, content distribution networks and media streaming. This success can mainly be attributed to the simplicity of the route ab- straction, a developer does not need to care about the mechanisms for membership management, load balancing or data replication. A limitation, however, is that most key-based routing solutions are best-effort, which means that only eventually consistent data access is possible. This thesis presents a system (Recode) with a key-based routing primitive called routecast which provides strong delivery semantics. More specifically, routecast guarantees that a message for a key is delivered in the same total order at a set of replicas. With stronger guarantees, applications such as coordination and metadata services as used in large storage systems or consistent key-value stores can use key-based routing. Additionally, Recode aims to be both re- configurable, to handle changes to the machines running the service and updates to the workload, and fully decentralized which means there is no single point of failure or bottleneck. We make three main contributions in this thesis: 1) a group com- munication abstraction using primary/backup with leases for pri- mary fail-over, 2) the design and algorithms of the routecast-primitive and, 3) mechanisms for atomic reconfiguration of a decentralized key space. Each part of the system is broken up into modules and presented with a specification and a set of algorithms. To validate the simplicity claim, we describe how to implement three different applications on top of Recode. Finally, we evaluate Recode in a cluster environment and show that the performance is competitive.

Die Arbeit widmet sich der Frage, ob sich die etablierte Technik des modellbasierten Testens (MBT) auf eine spezielle Art von Software-Komponentensystemen, den dynamischen Komponentensystemen (DCS), anwenden lässt. DCS bieten die besondere Eigenschaft, dass sich die Komposition der Komponenteninstanzen zur Laufzeit ändern kann, da in solchen Systemen jede Komponenteninstanz einen Lebenszyklus aufweist. Damit ist es möglich, im laufenden Betrieb einzelne Komponenten im Softwaresystem zu aktualisieren oder dem System neue hinzuzufügen. Derartige Eingriffe führen dazu, dass die von den Komponenteninstanzen bereitgestellte Funktionalität jederzeit eingeschränkt oder unverfügbar werden kann. Diese Eigenschaft der DCS macht die Entwicklung von Komponenten schwierig, da diese in ihrem potentiellen Verhalten darauf vorbereitet werden müssen, dass die von ihnen jeweils benötigte und genutzte Funktionalität nicht ständig verfügbar ist. Ziel dieser Dissertation ist es nun, einen systematischen Testansatz zu entwickeln, der es erlaubt, bereits während der Entwicklung von DCS-Komponenten Toleranzaussagen bzgl. ihrer dynamischen Verfügbarkeit treffen zu können. Untersucht wird, inwieweit bestehende MBT-Ansätze bei entsprechender Anpassung für den neuen Testansatz übernommen werden können. Durch die in der Dissertation entwickelten Ansätze sowie deren Implementierung und Anwendung in einer Fallstudie wird gezeigt, dass eine systematische Testfallgenerierung für dynamische Komponentensysteme mit Hilfe der Anwendung und Anpassung von modellbasierten Testtechnologien erreicht werden kann. / This dissertation devotes to the question whether the established technique of model based testing (MBT) can be applied to a special type of software component systems called dynamic component systems (DCSs). DCSs have the special characteristic that they support the change of component instance compositions during runtime of the system. In these systems, each component instance exhibits an own lifecycle. This makes it possible to update existing, or add new components to the system, while it is running. Such changes cause that functionality provided by the component instances may become restricted or unavailable at any time. This characteristic of DCSs makes the development of components difficult because required and used functionality is not available all the time. The goal of this dissertation is to develop a systematic testing approach which allows to test a component’s tolerance to dynamic availability during development time. We analyze, to what extend existing MBT approaches can be reused or adapted. The approaches of this dissertation has been implemented in a software prototype. This prototype has been used in a case study and it has been showed, that systematic test generation for DCSs can be done with the help of MBT.

In der klassischen Komplexitätstheorie werden worst-case Laufzeiten von Algorithmen typischerweise einzig abhängig von der Eingabegröße angegeben. In dem Kontext der parametrisierten Komplexitätstheorie versucht man die Analyse der Laufzeit dahingehend zu verfeinern, dass man zusätzlich zu der Eingabengröße noch einen Parameter berücksichtigt, welcher angibt, wie strukturiert die Eingabe bezüglich einer gewissen Eigenschaft ist. Ein parametrisierter Algorithmus nutzt dann diese beschriebene Struktur aus und erreicht so eine Laufzeit, welche schneller ist als die eines besten unparametrisierten Algorithmus, falls der Parameter klein ist. Der erste Hauptteil dieser Arbeit führt die Forschung in diese Richtung weiter aus und untersucht den Einfluss von verschieden Parametern auf die Laufzeit von bekannten effizient lösbaren Problemen. Einige vorgestellte Algorithmen sind dabei adaptive Algorithmen, was bedeutet, dass die Laufzeit von diesen Algorithmen mit der Laufzeit des besten unparametrisierten Algorithm für den größtmöglichen Parameterwert übereinstimmt und damit theoretisch niemals schlechter als die besten unparametrisierten Algorithmen und übertreffen diese bereits für leicht nichttriviale Parameterwerte. Motiviert durch den allgemeinen Erfolg und der Vielzahl solcher parametrisierten Algorithmen, welche eine vielzahl verschiedener Strukturen ausnutzen, untersuchen wir im zweiten Hauptteil dieser Arbeit, wie man solche unterschiedliche homogene Strukturen zu mehr heterogenen Strukturen vereinen kann. Ausgehend von algebraischen Ausdrücken, welche benutzt werden können, um von Parametern beschriebene Strukturen zu definieren, charakterisieren wir klar und robust heterogene Strukturen und zeigen exemplarisch, wie sich die Parameter tree-depth und modular-width heterogen verbinden lassen. Wir beschreiben dazu effiziente Algorithmen auf heterogenen Strukturen mit Laufzeiten, welche im Spezialfall mit den homogenen Algorithmen übereinstimmen. / In classical complexity theory, the worst-case running times of algorithms depend solely on the size of the input. In parameterized complexity the goal is to refine the analysis of the running time of an algorithm by additionally considering a parameter that measures some kind of structure in the input. A parameterized algorithm then utilizes the structure described by the parameter and achieves a running time that is faster than the best general (unparameterized) algorithm for instances of low parameter value. In the first part of this thesis, we carry forward in this direction and investigate the influence of several parameters on the running times of well-known tractable problems. Several presented algorithms are adaptive algorithms, meaning that they match the running time of a best unparameterized algorithm for worst-case parameter values. Thus, an adaptive parameterized algorithm is asymptotically never worse than the best unparameterized algorithm, while it outperforms the best general algorithm already for slightly non-trivial parameter values. As illustrated in the first part of this thesis, for many problems there exist efficient parameterized algorithms regarding multiple parameters, each describing a different kind of structure. In the second part of this thesis, we explore how to combine such homogeneous structures to more general and heterogeneous structures. Using algebraic expressions, we define new combined graph classes of heterogeneous structure in a clean and robust way, and we showcase this for the heterogeneous merge of the parameters tree-depth and modular-width, by presenting parameterized algorithms on such heterogeneous graph classes and getting running times that match the homogeneous cases throughout.

Im Bereich von Exascale Computing und HPC sind Fehler nicht gelegentlich. Sondern treten sie regelmäßig während der Laufzeit von Anwendungen auf. Die Bewältigung dieser Herausforderungen ist wichtig, um die Zuverlässigkeit der Supercomputing-Anwendung zu verbessern. Checkpoint/Restart ist eine Technik, die in HPC verwendet wird, um die Ausfallsicherheit bei Ausfällen zu verbessern. Dabei wird der Status einer Anwendung regelmäßig auf der Festplatte gespeichert, sodass die Anwendung bei einem Ausfall vom letzten Checkpoint aus neu gestartet werden kann. Checkpointing kann jedoch zeitaufwändig sein insbesondere hinsichtlich I/O. Daher ist die Optimierung des C/R-Prozesses wichtig, um seine Auswirkungen auf die Anwendungsleistung zu reduzieren und die Job-Resilienz zu verbessern. Der erste Teil dieser Arbeit erforscht und entwickelt innovative Techniken im Bereich des C/R-Managements im HPC-Kontext. Dazu gehört die Entwicklung eines neuartigen C/R-Ansatzes, die Entwicklung eines Modells für mehrstufiges C/R, und die Optimierung der gemeinsamen Nutzung von Burst-Puffer für C/R in Supercomputern. C/R-Prozeduren erzeugen umfangreiche I/O-Operationen. Daher ist eine Optimierung der I/O-Prozesse zwingend erforderlich. Um den C/R-Prozess zu optimieren, ist es auch wichtig, das I/O-Verhalten einer Anwendung zu verstehen, einschließlich der Menge an Daten, die geschrieben werden müssen, wie oft Checkpoints genommen werden sollten und wo die Checkpoints gespeichert werden sollen. Daher untersuchen und stellen wir im zweiten Teil Innovationen von Ansätzen für I/O-Modellierung und -Management. Dazu gehört die Entwicklung eines Plugins für GCC, das das optimale Speichergerät für die I/O von Anwendungen basierend auf ihrem durch Pragma-Vorstellungen definierten Verhalten auswählt, und die Entwicklung eines Modells zur Schätzung der I/O-Kosten Anwendungen unter Linux unter Berücksichtigung von Seitenverwaltung und Prozessdrosselung. / In the context of exascale computing and HPC, failures are not occasional but rather inherent, occurring during the runtime of applications. Addressing these challenges is essential to enhance the resilience and reliability of supercomputing operations. Checkpoint/Restart (C/R) is a technique used in HPC to improve job resilience in the case of failures. This involves periodically saving the state of an application to disk, so that if the application fails, it can be restarted from the last checkpoint. However, checkpointing can be time-consuming and significantly impact application performance, particularly regarding its I/O operations. Therefore, optimizing C/R is crucial for reducing its impact on application performance and improving job resilience. The first part of this work develops novel techniques in C/R management within the context of HPC. This includes developing a novel C/R approach by combining XOR and partner C/R mechanisms, developing a model for multilevel C/R in large computational resources, and optimising the shared usage of burst buffers for C/R in supercomputers. C/R procedures generate substantial I/O operations, emerging as a bottleneck for HPC applications. Hence, the need for optimization in I/O processes becomes imperative to overcome this bottleneck. To optimize the C/R process, it is also important to understand the I/O behavior of an application, including how much data needs to be written, how frequently checkpoints should be taken, and where to store the checkpoints to minimize I/O bottlenecks. Hence, in the second part, we investigate and introduce innovative techniques and approaches for I/O modeling and management. This includes developing a plugin for GNU C Compiler (GCC) that selects the optimal storage device for the I/O of applications based on their behavior that is defined by Pragma notions, and developing a model to estimate I/O cost of applications under Linux considering page management and process throttling.

Event Stream Processing (ESP) Systeme überwachen kontinuierliche Datenströme, um benutzerdefinierte Queries auszuwerten. Die Herausforderung besteht darin, dass die Queryverarbeitung zustandsbehaftet ist und die Anzahl von Teilübereinstimmungen mit der Größe der verarbeiteten Events exponentiell anwächst. Die Dynamik von Streams und die Notwendigkeit, entfernte Daten zu integrieren, erschweren die Zustandsverwaltung. Erstens liefern heterogene Eventquellen Streams mit unvorhersehbaren Eingaberaten und Queryselektivitäten. Während Spitzenzeiten ist eine erschöpfende Verarbeitung unmöglich, und die Systeme müssen auf eine Best-Effort-Verarbeitung zurückgreifen. Zweitens erfordern Queries möglicherweise externe Daten, um ein bestimmtes Event für eine Query auszuwählen. Solche Abhängigkeiten sind problematisch: Das Abrufen der Daten unterbricht die Stream-Verarbeitung. Ohne eine Eventauswahl auf Grundlage externer Daten wird das Wachstum von Teilübereinstimmungen verstärkt. In dieser Dissertation stelle ich Strategien für optimiertes Zustandsmanagement von ESP Systemen vor. Zuerst ermögliche ich eine Best-Effort-Verarbeitung mittels Load Shedding. Dabei werden sowohl Eingabeeevents als auch Teilübereinstimmungen systematisch verworfen, um eine Latenzschwelle mit minimalem Qualitätsverlust zu garantieren. Zweitens integriere ich externe Daten, indem ich das Abrufen dieser von der Verwendung in der Queryverarbeitung entkoppele. Mit einem effizienten Caching-Mechanismus vermeide ich Unterbrechungen durch Übertragungslatenzen. Dazu werden externe Daten basierend auf ihrer erwarteten Verwendung vorab abgerufen und mittels Lazy Evaluation bei der Eventauswahl berücksichtigt. Dabei wird ein Kostenmodell verwendet, um zu bestimmen, wann welche externen Daten abgerufen und wie lange sie im Cache aufbewahrt werden sollen. Ich habe die Effektivität und Effizienz der vorgeschlagenen Strategien anhand von synthetischen und realen Daten ausgewertet und unter Beweis gestellt. / Event stream processing systems continuously evaluate queries over event streams to detect user-specified patterns with low latency. However, the challenge is that query processing is stateful and it maintains partial matches that grow exponentially in the size of processed events. State management is complicated by the dynamicity of streams and the need to integrate remote data. First, heterogeneous event sources yield dynamic streams with unpredictable input rates, data distributions, and query selectivities. During peak times, exhaustive processing is unreasonable, and systems shall resort to best-effort processing. Second, queries may require remote data to select a specific event for a pattern. Such dependencies are problematic: Fetching the remote data interrupts the stream processing. Yet, without event selection based on remote data, the growth of partial matches is amplified. In this dissertation, I present strategies for optimised state management in event pattern detection. First, I enable best-effort processing with load shedding that discards both input events and partial matches. I carefully select the shedding elements to satisfy a latency bound while striving for a minimal loss in result quality. Second, to efficiently integrate remote data, I decouple the fetching of remote data from its use in query evaluation by a caching mechanism. To this end, I hide the transmission latency by prefetching remote data based on anticipated use and by lazy evaluation that postpones the event selection based on remote data to avoid interruptions. A cost model is used to determine when to fetch which remote data items and how long to keep them in the cache. I evaluated the above techniques with queries over synthetic and real-world data. I show that the load shedding technique significantly improves the recall of pattern detection over baseline approaches, while the technique for remote data integration significantly reduces the pattern detection latency.

Das Erstellen von Unterrichtsentwürfen wird als Voraussetzung für effektiven, zielgerichteten Unterricht gesehen. Dies gilt insbesondere für angehende Lehrpersonen. Da viele Aspekte, wie z.B. Methoden, Fachinhalte, Standards und die Charakteristik der Lerngruppe, zur gleichen Zeit berücksichtigt und sinnvoll aufeinander abgestimmt werden müssen, handelt es sich um eine kreative und zugleich anspruchsvolle Aufgabe. Es liegt nahe, diesen aufwändigen Prozess der Planung durch spezialisierte Softwaresysteme zu unterstützen, die nicht nur Routineaufgaben erleichtern, sondern auch zur Reflexion anregen. Basierend auf einem Literatur-Review und Interviews mit Dozierenden, die Lehrpersonen ausbilden, werden Anforderungen an Unterrichtsentwürfe analysiert und diskutiert. Es werden dabei nicht nur die relevanten theoretischen Grundlagen betrachtet, sondern ebenfalls das Vorgehen bei der Planung, genutzte Hilfsmittel und besonders unterstützenswerte Aspekte aus der Praxis. Darauf aufbauend werden Anwendungsfälle und Anforderungen an ein Planungsunterstützungssystem systematisch abgeleitet. Existierende Planungssysteme werden vorgestellt und untersucht, wobei viele bereits elementare Anforderungen nicht erfüllen. Insbesondere gibt es kein System, das adaptives Feedback bereitstellt. Um diese Lücke zu schließen, wird eine graphische, zeitbasierte Notation zur Unterrichtsplanung vorgeschlagen. Weiterhin sind ein Ressourcen-Management, Analyse-Möglichkeiten und automatisches Feedback zentrale Bestandteile des Ansatzes. Der entwickelte Prototyp wurde mit über 100 Personen in mehreren Studien systematisch empirisch evaluiert. Im Fokus stand dabei nicht nur die Untersuchung der Gebrauchstauglichkeit des Ansatzes und des Prototyps, sondern auch wie sich die Nutzung des Prototyps auf die Qualität der Unterrichtsentwürfe auswirkt. Es wird aufgezeigt, dass der beschriebene Ansatz für die Planung von Unterricht geeignet ist und angehende Lehrpersonen auch zur Reflexion angeregt hat. / Developing a lesson plan is considered as a prerequisite for effective, targeted instruction. This is particularly true for prospective teachers. Since many aspects such as methods, subject content, standards, and the characteristics of the learner group have to be taken into account and reasonably compiled, it is a creative as well as a demanding task. It stands to reason that this complex process of planning can be supported by specialized software systems that do not only facilitate routine tasks, but also stimulate reflection. Based on a literature-review and interviews with instructors of prospective teachers, requirements for lesson plans are analyzed and discussed. Not only relevant theoretical principles of lesson planning are considered, but also individual planning steps, tools used and practical aspects that would benefit particularly from further support. Building upon this, use cases and requirements for a lesson planning support system are derived systematically. Existing planning systems are presented and analyzed. It is argued that many systems do not meet even basic requirements. Especially there is no system that offers adaptive feedback. In order to fill this gap, a graphical time-based representation is proposed for lesson planning. Further central aspects of this approach are resource management, analysis capabilities and automatic feedback. A software architecture for a planning support system is presented that implements the aforementioned approach and meets the requirements. The developed prototype was empirically evaluated in several systematic studies involving over 100 participants. The focus to study was the usability of the approach and the prototype on the one hand, and how the use of the prototype affects the quality of the lesson plans on the other hand. In this thesis it is shown that the described approach for lesson planning is adequate and suitable to promote reflective thinking about one''s own planning activities.

In den letzten Jahren erfreuen sich komplexe Netzwerke einer zunehmenden Beliebtheit, um Zusammenhänge und Strukturen in hoch-dimensionalen Datensätzen zu analysieren. Im Unterschied zu vielen anderen Forschungsgebieten wurden sie jedoch selten auf Paläoklima-Daten angewandt, obwohl die steigende Anzahl an veröffentlichen Zeitreihen die Nutzung effizienter Methoden multivariater Analyse ermöglicht. Die Resultate der wenigen Studien, in denen Netzwerkmethoden und Paläoklima-Daten kombiniert wurden, sind außerdem geprägt von niedriger Robustheit und hohen Unsicherheiten. Dies steht im Zusammenhang zu der niedrigen Anzahl und Auflösung der Zeitreihen als auch den Unsicherheiten, die den meisten Paläoklima-Rekonstruktionen zu eigen sind. In dieser Doktorarbeit schlage ich verschiedene Wege vor, um diese Probleme zu überwinden, indem verlässlichere, quantitative Resultate ermöglicht werden, unter anderem indem die Datenunsicherheiten explizit in die Analyse mit einbezogen werden. Zu diesem Zweck präsentiere ich vier Fallstudien mit einem Fokus auf zwei Zeiträume, das späte Holozän (die letzten zweitausend Jahre) und den Übergang von der letzten Kaltzeit zur aktuellen Warmzeit, die letzte glaziale Termination. Alle diese Studien legen einen räumlichen Fokus auf den Nordatlantik, eine Schlüsselregion globaler Klimavariabilität. Ich beschränke mich hierbei auf zwei Methoden, eine der netzwerkbasierten Zeitreihenanalyse, Sichtbarkeitsgraphen genannt, und eine der räumlichen Analyse, sogenannte Klimanetzwerke. Neben Erweiterungen von existierende Methoden, schlage ich auch neue Wege vor, um verlässliche Resultate auch für Zeitreihen mit hohen Unsicherheiten zu erhalten. Diese Fallstudien demonstrieren, dass Netzwerkmethoden auch für die Analyse von Paläoklima-Daten nützlich sein können. Sie sind daher ein weiterer Schritt hin zu einer künftigen Anwendung durch eine größere Anzahl an Forschenden. / In recent years, complex networks have become an increasingly popular tool to analyse relationships and structures in high-dimensional data sets in a variety of research fields. They have, however, rarely been applied to paleoclimate data sets, even though the growing number of published records demands efficient tools of multivariate analysis. The few published results that combine network methods and paleoclimate proxies are often not robust or have high uncertainty levels, linked tothe low dimensionality, resolution and the large uncertainties of most particulate time series. In this thesis, I propose several ways to overcome these issues in order to obtain reliable and quantitative results from network based tools by taking the particularities of paleoclimate data into account. For this purpose, I present four case studies, focusing on two time periods, the late Holocene (last two millennia) and the transition from the last ice age to the recent warm period, the last deglaciation. These studies are all related to the North Atlantic, a key region in multi-decadal to millennial scale climate variability. I primarily use two methods, one of network based time series analysis named visibility graphs and one of spatial analysis, so called limate networks. I have both further developed existing methods, but also propose new ways to yield reliable results when dealing with highly uncertain paleoclimate data. The case studies demonstrate the usefulness of network based data analysis to study patterns of regional climate variability. Hence, this work is another step in bringing network based approaches to a larger audience and towards a wider application of these methods.

Diese Dissertation hat die institutionalisierte Form des Sammelns in europäischen Museen zum Gegenstand. Mit dieser Arbeit analysiere ich die Auswirkungen des Einsatzes digitaler soziotechnischer Systeme für die Dokumentation von Museumssammlungen. Dafür kombiniere ich eine dezidiert theoretisch-kulturwissenschaftliche mit einer praxisorientierten Perspektive, die von der kritischen Museologie, der Human-Computer Interaction (HCI) und der Visualisierungsforschung informiert ist. Die zugrunde liegende Hypothese lautet, dass weder der Einsatz digitaler soziotechnischer Systeme zur Museumsdokumentation noch die daran anschließenden Formen der Veröffentlichung und Zugänglichmachung von Museumssammlungen zu einer »digitalen Transformation« des musealen Sammelns geführt haben. Diese Hypothese basiert auf der Beschreibung des musealen Sammelns als Kulturtechnik. Aufbauend auf diesem theoretischen Konzept betone ich das symmetrisch gedachte Zusammenspiel der technisch-medialen und der symbolischen Dimension kulturhervorbringender Praktiken. Um meine Hypothese zu überprüfen, analysiere ich Artikel, Handreichungen, Klassifzierungsstandards, technische Berichte und Software-Evaluierungen, die für und von Museumsfachleuten geschrieben wurden. Meine Analyse zeigt, dass die symbolische Dimension der Kulturtechnik des Sammelns - konkret die mit Sammlungen hergestellten und abgebildeten »epistemischen Ordnungen« - trotz der Nutzung von digitalen Technologien von Kontinuität geprägt ist. Die epistemischen Ordnungen werden bisher insbesondere durch die Dominanz und Priorisierung von standardisierter Wissensrepräsentation stabilisiert. Aufbauend auf diesen Erkenntnissen gehe ich der Frage nach, ob und wie digitale soziotechnische Systeme und algorithmische Verfahren im Kontext des musealen Sammelns so gestaltet werden können, dass sie der Destabilisierung und Pluralisierung von Museumsordnungen dienen und somit »Transformationsimpulse« verstärken oder auslösen können. / This dissertation is concerned with the institutionalised form of collecting in European museums. In this work, I analyse the effects of using digital socio-technical systems for documenting museum collections. For this, I combine a theoretical approach grounded in cultural studies with a practice-oriented perspective informed by critical museology, Human-Computer Interaction (HCI), and visualisation research. My guiding hypothesis is that neither the use of digital socio-technical systems for museum documentation nor the subsequent forms of publishing and access to museum collections have led to a »digital transformation« of museum collecting. This hypothesis is based on the description of museum collecting as a cultural technique (Kulturtechnik). Building on this theoretical concept, I emphasise the symmetrical interplay of the technological and the symbolic dimensions of culture-producing practices. To test my hypothesis, I analyse articles, guidelines, classification standards, technical reports, and software evaluations written for and by museum professionals. My analysis shows that the symbolic dimension of the cultural technique of collecting - specifically the »epistemic orders« produced and represented with collections - is characterised by continuity despite the use of digital technologies. The epistemic orders are stabilised, particularly by the dominance and prioritisation of standardised knowledge representation. Building on these findings, I explore the question of whether and in what way digital socio-technical systems and algorithmic processes can be designed in such a way that they serve to destabilise and pluralise museum orders and consequently can contribute to amplifying or triggering »transformation impulses« in the context of museum collecting.

Diese Arbeit befasst sich mit der Entwicklung eines echtzeitfähigen Systems zur Erstellung von Tiefeninformation aus Stereobildpaaren, das in einer Reihe von Anwendungen zur dreidimensionalen Vermessung des Raumes herangezogen werden kann. Als Hauptanwendungsgebiete sind in erster Linie mobile Robotikapplikationen vorgesehen, die sehr strenge Anforderungen sowohl bezüglich des Ressourcenverbrauchs als auch im Hinblick auf die Messeigenschaften und das Laufzeitverhalten stellen. Ein Merkmal des in dieser Arbeit entworfenen Systems ist die in Echtzeit stattfindende Ausführung der verwendeten Algorithmen in Kombination mit sehr guten Messeigenschaften. Das verwendete Stereo-Matching-Verfahren basiert auf einem globalen Ansatz und liefert im Vergleich zu den alternativen echtzeitfähigen Methoden sehr gute Ergebnisse. Im Vordergrund steht dabei der Semi-Global-Matching-Algorithmus. Aufgrund der Komplexität globaler Ansätze finden in Echtzeitapplikationen nur lokale Stereo-Verfahren Verwendung. Lokale Verfahren liefern jedoch im Vergleich zu den globalen Methoden qualitativ schlechte Disparitätskarten. Ein neuer globaler Matching-Algorithmus Efficient-Semi-Global-Matching (eSGM) wird vorgestellt und in das Konzept für mobile Robotikanwendungen umgesetzt. Wegen der begrenzten Ressourcen der realen Hardware wurde eine Weiterentwicklung des eSGM-Algorithmus für die Realisierung genutzt. Abschließend wird das System anhand der drei Kerneigenschaften Laufzeit, Ressourcenverbrauch und Qualität der Tiefeninformation gegenüber den Verfahren nach dem Stand der Technik bewertet. Der in dieser Arbeit vorgestellte FPGA-Ansatz, die eingesetzte Entwurfsmethode und die vorgestellten Algorithmen ermöglichten es, ein leistungsfähiges Stereo-Bildverarbeitungssystem zu entwickeln, das den hohen Anforderungen bezüglich des Laufzeitverhaltens und der Qualität des Ergebnisses gerecht wird. / This work presents a realtime stereo image matching system that takes advantage of a global image matching method. The system is designed to provide depth information for mobile robotic applications. Typical tasks of the proposed system are to assist in obstacle avoidance, SLAM and path planning of mobile robots, that pose strong requirements on the size, energy consumption, reliability, frame rate and quality of the calculated depth map. Current available systems either rely on active sensors or on local stereo-image matching algorithms. The first are only suitable in controlled environments while the second suffer from low quality depth-maps. Top ranking quality results are only achieved by an iterative approach using global image matching and colour segmentation techniques which are computationally demanding and therefore difficult to be executed in real time. Attempts were made to still reach real-time performance with global methods by simplifying the routines but led to degraded depth maps which are at the end almost comparable with local methods. An equally named semi-global algorithm was proposed earlier, that shows both very good image matching results and relatively simple execution at the same time. A memory efficient variant of the Semi-Global Matching algorithm is presented and adopted for an implementation based on reconfigurable hardware that is suitable for real-time operations in the field of robotics. It will be shown that the modified version of the efficient Semi-Global matching method is delivering equivalent result compared to the original algorithm. The complete design has been implemented within a hardware development framework that is also reviewed.

Informationsextraktions (IE) auf sehr großen Datenmengen erfordert hochkomplexe, skalierbare und anpassungsfähige Systeme. Obwohl zahlreiche IE-Algorithmen existieren, ist die nahtlose und erweiterbare Kombination dieser Werkzeuge in einem skalierbaren System immer noch eine große Herausforderung. In dieser Arbeit wird ein anfragebasiertes IE-System für eine parallelen Datenanalyseplattform vorgestellt, das für konkrete Anwendungsdomänen konfigurierbar ist und für Textsammlungen im Terabyte-Bereich skaliert. Zunächst werden konfigurierbare Operatoren für grundlegende IE- und Web-Analytics-Aufgaben definiert, mit denen komplexe IE-Aufgaben in Form von deklarativen Anfragen ausgedrückt werden können. Alle Operatoren werden hinsichtlich ihrer Eigenschaften charakterisiert um das Potenzial und die Bedeutung der Optimierung nicht-relationaler, benutzerdefinierter Operatoren (UDFs) für Data Flows hervorzuheben. Anschließend wird der Stand der Technik in der Optimierung nicht-relationaler Data Flows untersucht und herausgearbeitet, dass eine umfassende Optimierung von UDFs immer noch eine Herausforderung ist. Darauf aufbauend wird ein erweiterbarer, logischer Optimierer (SOFA) vorgestellt, der die Semantik von UDFs mit in die Optimierung mit einbezieht. SOFA analysiert eine kompakte Menge von Operator-Eigenschaften und kombiniert eine automatisierte Analyse mit manuellen UDF-Annotationen, um die umfassende Optimierung von Data Flows zu ermöglichen. SOFA ist in der Lage, beliebige Data Flows aus unterschiedlichen Anwendungsbereichen logisch zu optimieren, was zu erheblichen Laufzeitverbesserungen im Vergleich mit anderen Techniken führt. Als Viertes wird die Anwendbarkeit des vorgestellten Systems auf Korpora im Terabyte-Bereich untersucht und systematisch die Skalierbarkeit und Robustheit der eingesetzten Methoden und Werkzeuge beurteilt um schließlich die kritischsten Herausforderungen beim Aufbau eines IE-Systems für sehr große Datenmenge zu charakterisieren. / Information extraction (IE) on very large data sets requires highly complex, scalable, and adaptive systems. Although numerous IE algorithms exist, their seamless and extensible combination in a scalable system still is a major challenge. This work presents a query-based IE system for a parallel data analysis platform, which is configurable for specific application domains and scales for terabyte-sized text collections. First, configurable operators are defined for basic IE and Web Analytics tasks, which can be used to express complex IE tasks in the form of declarative queries. All operators are characterized in terms of their properties to highlight the potential and importance of optimizing non-relational, user-defined operators (UDFs) for dataflows. Subsequently, we survey the state of the art in optimizing non-relational dataflows and highlight that a comprehensive optimization of UDFs is still a challenge. Based on this observation, an extensible, logical optimizer (SOFA) is introduced, which incorporates the semantics of UDFs into the optimization process. SOFA analyzes a compact set of operator properties and combines automated analysis with manual UDF annotations to enable a comprehensive optimization of data flows. SOFA is able to logically optimize arbitrary data flows from different application areas, resulting in significant runtime improvements compared to other techniques. Finally, the applicability of the presented system to terabyte-sized corpora is investigated. Hereby, we systematically evaluate scalability and robustness of the employed methods and tools in order to pinpoint the most critical challenges in building an IE system for very large data sets.