Unternehmen sammeln mehr Daten als je zuvor und müssen auf diese Informationen zeitnah reagieren. Relationale Datenbanken eignen sich nicht für die latenzfreie Verarbeitung dieser oft unstrukturierten Daten. Um diesen Anforderungen zu begegnen, haben sich in der Datenbankforschung seit dem Anfang der 2000er Jahre zwei neue Forschungsrichtungen etabliert: skalierbare Verarbeitung unstrukturierter Daten und latenzfreie Datenstromverarbeitung. Skalierbare Verarbeitung unstrukturierter Daten, auch bekannt unter dem Begriff "Big Data"-Verarbeitung, hat in der Industrie schnell Einzug erhalten. Gleichzeitig wurden in der Forschung Systeme zur latenzfreien Datenstromverarbeitung entwickelt, die auf eine verteilte Architektur, Skalierbarkeit und datenparallele Verarbeitung setzen. Obwohl diese Systeme in der Industrie vermehrt zum Einsatz kommen, gibt es immer noch große Herausforderungen im praktischen Einsatz. Diese Dissertation verfolgt zwei Hauptziele: Zuerst wird das Laufzeitverhalten von hochskalierbaren datenparallelen Datenstromverarbeitungssystemen untersucht. Im zweiten Hauptteil wird das "Dual Streaming Model" eingeführt, das eine Semantik zur gleichzeitigen Verarbeitung von Datenströmen und Tabellen beschreibt. Das Ziel unserer Untersuchung ist ein besseres Verständnis über das Laufzeitverhalten dieser Systeme zu erhalten und dieses Wissen zu nutzen um Anfragen automatisch ausreichende Rechenkapazität zuzuweisen. Dazu werden ein Kostenmodell und darauf aufbauende Optimierungsalgorithmen für Datenstromanfragen eingeführt, die Datengruppierung und Datenparallelität einbeziehen. Das vorgestellte Datenstromverarbeitungsmodell beschreibt das Ergebnis eines Operators als kontinuierlichen Strom von Veränderugen auf einer Ergebnistabelle. Dabei behandelt unser Modell die Diskrepanz der physikalischen und logischen Ordnung von Datenelementen inhärent und erreicht damit eine deterministische Semantik und eine minimale Verarbeitungslatenz. / Modern companies are able to collect more data and require insights from it faster than ever before. Relational databases do not meet the requirements for processing the often unstructured data sets with reasonable performance. The database research community started to address these trends in the early 2000s. Two new research directions have attracted major interest since: large-scale non-relational data processing as well as low-latency data stream processing. Large-scale non-relational data processing, commonly known as "Big Data" processing, was quickly adopted in the industry. In parallel, low latency data stream processing was mainly driven by the research community developing new systems that embrace a distributed architecture, scalability, and exploits data parallelism. While these systems have gained more and more attention in the industry, there are still major challenges to operate them at large scale. The goal of this dissertation is two-fold: First, to investigate runtime characteristics of large scale data-parallel distributed streaming systems. And second, to propose the "Dual Streaming Model" to express semantics of continuous queries over data streams and tables. Our goal is to improve the understanding of system and query runtime behavior with the aim to provision queries automatically. We introduce a cost model for streaming data flow programs taking into account the two techniques of record batching and data parallelization. Additionally, we introduce optimization algorithms that leverage our model for cost-based query provisioning. The proposed Dual Streaming Model expresses the result of a streaming operator as a stream of successive updates to a result table, inducing a duality between streams and tables. Our model handles the inconsistency of the logical and the physical order of records within a data stream natively, which allows for deterministic semantics as well as low latency query execution.

In Laufe der letzten zehn Jahre haben Scientific Workflows als Werkzeug zur Erstellung von reproduzierbaren, datenverarbeitenden in-silico Experimenten an Aufmerksamkeit gewonnen, in die sowohl lokale Skripte und Anwendungen, als auch Web-Services eingebunden werden können. Über spezialisierte Online-Bibliotheken, sogenannte Repositories, können solche Workflows veröffentlicht und wiederverwendet werden. Mit zunehmender Größe dieser Repositories werden Ähnlichkeitsmaße für Scientific Workflows notwendig, etwa für Duplikaterkennung, Ähnlichkeitssuche oder Clustering von funktional ähnlichen Workflows. Die vorliegende Arbeit untersucht solche Ähnlichkeitsmaße für Scientific Workflows. Als erstes untersuchen wir ähnlichkeitsrelevante Eigenschaften von Scientific Workflows und identifizieren Charakteristika der Wiederverwendung ihrer Komponenten. Als zweites analysieren und reimplementieren wir existierende Lösungen für den Vergleich von Scientific Workflows entlang definierter Teilschritte des Vergleichsprozesses. Wir erstellen einen großen Gold-Standard Corpus von Workflowähnlichkeiten, der über 2400 Bewertungen für 485 Workflowpaare enthält, die von 15 Experten aus 6 Institutionen beigetragen wurden. Zum ersten Mal erlauben diese Vorarbeiten eine umfassende, vergleichende Evaluation verschiedener Ähnlichkeitsmaße für Scientific Workflows, in der wir einige vorige Ergebnisse bestätigen, andere aber revidieren. Als drittes stellen wir ein neue Methode für das Vergleichen von Scientific Workflows vor. Unsere Evaluation zeigt, dass diese neue Methode bessere und konsistentere Ergebnisse liefert und leicht mit anderen Ansätzen kombiniert werden kann, um eine weitere Qualitätssteigerung zu erreichen. Als viertes zweigen wir, wie die Resultate aus den vorangegangenen Schritten genutzt werden können, um aus Standardkomponenten eine Suchmaschine für schnelle, qualitativ hochwertige Ähnlichkeitssuche im Repositorymaßstab zu implementieren. / Over the last decade, scientific workflows have gained attention as a valuable tool to create reproducible in-silico experiments. Specialized online repositories have emerged which allow such workflows to be shared and reused by the scientific community. With increasing size of these repositories, methods to compare scientific workflows regarding their functional similarity become a necessity. To allow duplicate detection, similarity search, or clustering, similarity measures for scientific workflows are an essential prerequisite. This thesis investigates similarity measures for scientific workflows. We carry out four consecutive research tasks: First, we closely investigate the relevant properties of scientific workflows regarding their similarity and identify characteristics of re-use of their components. Second, we review and dissect existing approaches to scientific workflow comparison into a defined set of subtasks necessary in the process of workflow comparison, and re-implement previous approaches to each subtask. We create a large gold-standard corpus of expert-ratings on workflow similarity, with more than 2400 ratings provided for 485 pairs of workflows by 15 workflow experts from 6 institutions. For the first time, this allows comprehensive, comparative evaluation of different scientific workflow similarity measures, confirming some previous findings, but rejecting others. Third, we propose and evaluate a novel method for scientific workflow comparison. We show that this novel method provides results of both higher quality and higher consistency than previous approaches, and can easily be stacked and ensembled with other approaches for still better performance and higher speed. Fourth, we show how our findings can be leveraged to implement a search engine using off-the-shelf tools that performs fast, high quality similarity search for scientific workflows at repository-scale, a premier area of application for similarity measures for scientific workflows.

Eine der größten Herausforderungen in Data Science ist heutzutage, Daten miteinander in Beziehung zu setzen und ähnliche Daten zu finden. Hierzu kann der aus relationalen Datenbanken bekannte Join-Operator eingesetzt werden. Das Konzept der Ähnlichkeit wird häufig durch mengenbasierte Ähnlichkeitsfunktionen gemessen. Um solche Funktionen als Join-Prädikat nutzen zu können, setzt diese Arbeit voraus, dass Records aus Mengen von Tokens bestehen. Die Arbeit fokussiert sich auf den mengenbasierten Ähnlichkeitsjoin, Set Similarity Join (SSJ). Die Datenmenge, die es heute zu verarbeiten gilt, ist groß und wächst weiter. Der SSJ hingegen ist eine rechenintensive Operation. Um ihn auf großen Daten ausführen zu können, sind neue Ansätze notwendig. Diese Arbeit fokussiert sich auf das Mittel der Parallelisierung. Sie leistet folgende drei Beiträge auf dem Gebiet der SSJs. Erstens beschreibt und untersucht die Arbeit den aktuellen Stand paralleler SSJ-Ansätze. Diese Arbeit vergleicht zehn Map-Reduce-basierte Ansätze aus der Literatur sowohl analytisch als auch experimentell. Der größte Schwachpunkt aller Ansätze ist überraschenderweise eine geringe Skalierbarkeit aufgrund zu hoher Datenreplikation und/ oder ungleich verteilter Daten. Keiner der Ansätze kann den SSJ auf großen Daten berechnen. Zweitens macht die Arbeit die verfügbare hohe CPU-Parallelität moderner Rechner für den SSJ nutzbar. Sie stellt einen neuen daten-parallelen multi-threaded SSJ-Ansatz vor. Der vorgestellte Ansatz ermöglicht erhebliche Laufzeit-Beschleunigungen gegenüber der Ausführung auf einem Thread. Drittens stellt die Arbeit einen neuen hoch skalierbaren verteilten SSJ-Ansatz vor. Mit einer kostenbasierten Heuristik und einem daten-unabhängigen Skalierungsmechanismus vermeidet er Daten-Replikation und wiederholte Berechnungen. Der Ansatz beschleunigt die Join-Ausführung signifikant und ermöglicht die Ausführung auf erheblich größeren Datenmengen als bisher betrachtete parallele Ansätze. / One of today's major challenges in data science is to compare and relate data of similar nature. Using the join operation known from relational databases could help solving this problem. Given a collection of records, the join operation finds all pairs of records, which fulfill a user-chosen predicate. Real-world problems could require complex predicates, such as similarity. A common way to measure similarity are set similarity functions. In order to use set similarity functions as predicates, we assume records to be represented by sets of tokens. In this thesis, we focus on the set similarity join (SSJ) operation. The amount of data to be processed today is typically large and grows continually. On the other hand, the SSJ is a compute-intensive operation. To cope with the increasing size of input data, additional means are needed to develop scalable implementations for SSJ. In this thesis, we focus on parallelization. We make the following three major contributions to SSJ. First, we elaborate on the state-of-the-art in parallelizing SSJ. We compare ten MapReduce-based approaches from the literature analytically and experimentally. Their main limit is surprisingly a low scalability due to too high and/or skewed data replication. None of the approaches could compute the join on large datasets. Second, we leverage the abundant CPU parallelism of modern commodity hardware, which has not yet been considered to scale SSJ. We propose a novel data-parallel multi-threaded SSJ. Our approach provides significant speedups compared to single-threaded executions. Third, we propose a novel highly scalable distributed SSJ approach. With a cost-based heuristic and a data-independent scaling mechanism we avoid data replication and recomputation. A heuristic assigns similar shares of compute costs to each node. Our approach significantly scales up the join execution and processes much larger datasets than all parallel approaches designed and implemented so far.

Künstliche Intelligenz und selbst-lernende Systeme, die ihr Verhalten aufgrund vergangener Entscheidungen und historischer Daten adaptieren, spielen eine im- mer größer werdende Rollen in unserem Alltag. Wir sind umgeben von einer großen Zahl algorithmischer Entscheidungshilfen, sowie einer stetig wachsenden Zahl algorithmischer Entscheidungssysteme. Rankings und sortierte Listen von Suchergebnissen stellen dabei das wesentliche Instrument unserer Onlinesuche nach Inhalten, Produkten, Freizeitaktivitäten und relevanten Personen dar. Aus diesem Grund bestimmt die Reihenfolge der Suchergebnisse nicht nur die Zufriedenheit der Suchenden, sondern auch die Chancen der Sortierten auf Bildung, ökonomischen und sogar sozialen Erfolg. Wissenschaft und Politik sorgen sich aus diesem Grund mehr und mehr um systematische Diskriminierung und Bias durch selbst-lernende Systeme. Um der Diskriminierung im Kontext von Rankings und sortierten Suchergeb- nissen Herr zu werden, sind folgende drei Probleme zu addressieren: Zunächst müssen wir die ethischen Eigenschaften und moralischen Ziele verschiedener Sit- uationen erarbeiten, in denen Rankings eingesetzt werden. Diese sollen mit den ethischen Werten der Algorithmen übereinstimmen, die zur Vermeidung von diskri- minierenden Rankings Anwendung finden. Zweitens ist es notwendig, ethische Wertesysteme in Mathematik und Algorithmen zu übersetzen, um sämtliche moralis- chen Ziele bedienen zu können. Drittens sollten diese Methoden einem breiten Publikum zugänglich sein, das sowohl Programmierer:innen, als auch Jurist:innen und Politiker:innen umfasst. / Artificial intelligence and adaptive systems, that learn patterns from past behavior and historic data, play an increasing role in our day-to-day lives. We are surrounded by a vast amount of algorithmic decision aids, and more and more by algorithmic decision making systems, too. As a subcategory, ranked search results have become the main mechanism, by which we find content, products, places, and people online. Thus their ordering contributes not only to the satisfaction of the searcher, but also to career and business opportunities, educational placement, and even social success of those being ranked. Therefore researchers have become increasingly concerned with systematic biases and discrimination in data-driven ranking models. To address the problem of discrimination and fairness in the context of rank- ings, three main problems have to be solved: First, we have to understand the philosophical properties of different ranking situations and all important fairness definitions to be able to decide which method would be the most appropriate for a given context. Second, we have to make sure that, for any fairness requirement in a ranking context, a formal definition that meets such requirements exists. More concretely, if a ranking context, for example, requires group fairness to be met, we need an actual definition for group fairness in rankings in the first place. Third, the methods together with their underlying fairness concepts and properties need to be available to a wide range of audiences, from programmers, to policy makers and politicians.

Einzelzellomics bieten unvoreingenommene Einblicke in Transkriptionsprogramme und Genom-Zugänglichkeiten auf zellulärer Ebene, auch wenn der zelluläre Kontext verloren geht. Wir haben einen virtuellen Multi-omic Embryo der Drosophila melanogaster erstellt, basierend auf den Datentypen RNA (Transkriptom) und ATAC (Zugänglichkeit der DNA), welche gleichzeitig auf Einzelzell Ebene erhoben wurden. Mithilfe des Tools novoSpaRc, welches den räumlichen Ursprung der Zellen rekonstruiert, konnte ein regulatorischen Bauplan erstellt werden, der die Genexpression und die Zugänglichkeit von Enhancern widerspiegelt. Diese Ressource hilft beim Verständnis der regulatorischen Dynamik in der Entwicklung. Bei der Untersuchung von ATAC-Peaks konnten wir Überschneidungen zwischen den Mustern der Chromatin Zugänglichkeit und der Aktivität unabhängiger getesteter Enhancer feststellen, was die Bedeutung der Zugänglichkeit unterstreicht. Die nicht-negative Matrixfaktorisierung identifizierte Archetypen der Genexpression und der Chromatin-Zugänglichkeit. Archetypen, die möglicherweise durch Transkriptionsfaktoren (TFs) reguliert werden, wurden einer Motiv-Anreicherungsanalyse für Archetyp-assoziierte CRMs unterzogen. Ein Ansatz zur Vorhersage von Enhancern, ordnete die Enhancer den Genen auf der Grundlage partieller Ähnlichkeit der Muster zu. Zusammenfassend dient unser multimodaler virtueller Embryo als Ressource und präsentiert zum ersten Mal räumliche Chromatin-Zugänglichkeiten für genomische Regionen für einen ganzen Organismus. Die Ergebnisse geben Aufschluss über die Prinzipien der Genregulation und zeigen den regulatorischen Einfluss von Transkriptionsfaktoren auf den Chromatinzustand von Enhancern. / Single-cell-omics techniques provide unbiased insights into transcriptional programs and genomic accessibility patterns at the cellular level despite sacrificing spatial information. We created a multi-omic virtual Drosophila melanogaster stage 6 embryo by simultaneously assessing genome accessibility and transcriptional states in individual cells. Using novoSpaRc, a spatial mapping tool, we accurately reconstructed the spatial origin of cells, yielding a regulatory blueprint reflecting gene expression and enhancer accessibilities. This resource aids in understanding developmental regulatory dynamics. Examining ATAC-peaks, we observed overlapping chromatin accessibility patterns with the activity of independently testes enhancers, emphasizing accessibility's importance. Non-negative matrix factorization identified archetypes in gene expression and chromatin accessibility. Accessibility archetypes, potentially regulated by transcription factors (TFs), were subjected to motif enrichment analysis for archetype-associated CRMs. An enhancer prediction approach, utilizing a generalized linear model, assigned enhancers to genes based on partial pattern similarity. In summary our multi-modal virtual embryo serves as a resource and presents for the first time single-cell chromatin accessibilities for genomic regions reconstructed in space for a whole organism in a single developmental stage. The results shed light on gene regulatory principles, highlighting the regulatory impact of TFs on chromatin states of enhancers.

Machine Learning (ML) profitiert erheblich von der Verfügbarkeit großer Mengen an Trainingsdaten, sowohl im Bezug auf die Anzahl an Datenpunkten, als auch auf die Anzahl an Features pro Datenpunkt. Es ist allerdings oft weder möglich, noch gewollt, mehr Daten unter zentraler Kontrolle zu aggregieren. Multi-Party-Computation (MPC)-Protokolle stellen eine Lösung dieses Dilemmas in Aussicht, indem sie es mehreren Parteien erlauben, ML-Modelle auf der Gesamtheit ihrer Daten zu trainieren, ohne die Eingabedaten preiszugeben. Generische MPC-Ansätze bringen allerdings erheblichen Mehraufwand in der Kommunikations- und Laufzeitkomplexität mit sich, wodurch sie sich nur beschränkt für den Einsatz in der Praxis eignen. Das Ziel dieser Arbeit ist es, Privatsphäreerhaltendes Machine Learning mittels MPC praxistauglich zu machen. Zuerst fokussieren wir uns auf zwei Anwendungen, lineare Regression und Klassifikation von Dokumenten. Hier zeigen wir, dass sich der Kommunikations- und Rechenaufwand erheblich reduzieren lässt, indem die aufwändigsten Teile der Berechnung durch Sub-Protokolle ersetzt werden, welche auf die Zusammensetzung der Parteien, die Verteilung der Daten, und die Zahlendarstellung zugeschnitten sind. Insbesondere das Ausnutzen dünnbesetzter Datenrepräsentationen kann die Effizienz der Protokolle deutlich verbessern. Diese Beobachtung verallgemeinern wir anschließend durch die Entwicklung einer Datenstruktur für solch dünnbesetzte Daten, sowie dazugehöriger Zugriffsprotokolle. Aufbauend auf dieser Datenstruktur implementieren wir verschiedene Operationen der Linearen Algebra, welche in einer Vielzahl von Anwendungen genutzt werden. Insgesamt zeigt die vorliegende Arbeit, dass MPC ein vielversprechendes Werkzeug auf dem Weg zu Privatsphäre-erhaltendem Machine Learning ist, und die von uns entwickelten Protokolle stellen einen wesentlichen Schritt in diese Richtung dar. / Machine learning (ML) greatly benefits from the availability of large amounts of training data, both in terms of the number of samples, and the number of features per sample. However, aggregating more data under centralized control is not always possible, nor desirable, due to security and privacy concerns, regulation, or competition. Secure multi-party computation (MPC) protocols promise a solution to this dilemma, allowing multiple parties to train ML models on their joint datasets while provably preserving the confidentiality of the inputs. However, generic approaches to MPC result in large computation and communication overheads, which limits the applicability in practice. The goal of this thesis is to make privacy-preserving machine learning with secure computation practical. First, we focus on two high-level applications, linear regression and document classification. We show that communication and computation overhead can be greatly reduced by identifying the costliest parts of the computation, and replacing them with sub-protocols that are tailored to the number and arrangement of parties, the data distribution, and the number representation used. One of our main findings is that exploiting sparsity in the data representation enables considerable efficiency improvements. We go on to generalize this observation, and implement a low-level data structure for sparse data, with corresponding secure access protocols. On top of this data structure, we develop several linear algebra algorithms that can be used in a wide range of applications. Finally, we turn to improving a cryptographic primitive named vector-OLE, for which we propose a novel protocol that helps speed up a wide range of secure computation tasks, within private machine learning and beyond. Overall, our work shows that MPC indeed offers a promising avenue towards practical privacy-preserving machine learning, and the protocols we developed constitute a substantial step in that direction.

Die thermische Magnetresonanz (ThermalMR) integriert Radiofrequenz (RF)-induzierte Erwärmung, in vivo Temperaturkartierung mittels MR-Thermometrie, anatomische und funktionelle MR-Bildgebung (MRT) und die Option für die x-Kern-MRT in einem einzigen, vielseitig einsetzbaren RF-Applikator. Der Aufbau erlaubt eine gezielte und überwachte Temperaturmodulation und kann somit als Basis für Studien dienen, welche die Klärung grundlegender Fragen bezüglich der molekularen, biochemischen, sowie physiologischen und therapeutischen Auswirkungen der Temperatur in Organismen ermöglichen. In dieser Arbeit wurde ein kostengünstiges, automatisiertes Open-Source-3D-Mehrzweck-Messsystem mit Submillimeter-Genauigkeit implementiert und validiert, um technische Entwicklungen in der thermischen MR wie Antennendesign, Signalgeneratoren, und simulationsbasierte Methoden zu prüfen. Um den Anforderungen eines modernen ThermalMR-Systems gerecht zu werden, wird ein neuer auf einem Phasenregelkreis basierender RF-Signalgenerator für Hyperthermie entwickelt und über dessen Entwurf, Implementierung, Validierung und Anwendung berichtet. Der Signalgenerator ist in der Lage, 32 unabhängige RF-Signale mit präziser Einstellung der Parameter dieser Signale zu erzeugen. Das in dieser Arbeit entwickelte Mehrkanal-RF-Überwachungsmodul ermöglicht das Detektieren von Abweichungen bezogen auf die gewählten Einstellungen und ermöglicht eine Korrektur der RF-Signale in einem Regelkreis. Darüber hinaus ermöglicht das Überwachungsmodul das Erkennen von Bewegungen und ermöglicht zusätzliche Sicherheit in einem realen Behandlungssetup. In dieser Arbeit wurden Forschung und Entwicklung in Informatik, Physik und Biowissenschaften synergetisch miteinander verbunden. Die in dieser Arbeit entwickelte Infrastruktur bildet eine technologische Basis für zukünftige ThermalMR-Anwendungen. / Thermal magnetic resonance (ThermalMR) integrates radio frequency (RF)-induced heating, in vivo temperature mapping using MR thermometry, anatomic and functional MR imaging (MRI), and the option for x-nuclei MRI in a single, multi-purpose RF applicator. This permits supervised targeted temperature modulation, thus enables pioneering studies to clarify fundamental questions pertaining to the molecular, biochemical, broader physiological and therapeutic effects of temperature in organisms. In this work, a cost-effective, automated open source 3D multipurpose measurement system with submillimeter fidelity was implemented and validated to facilitate technical developments in ThermalMR such as RF antenna design and algorithm verification. The design, implementation, validation, and application of the first phase-locked loop based RF signal generator in hyperthermia that is capable of generating 32 channels of independent RF signals with fine-tuning resolutions of the signals’ parameters meet the demanding requirements of a state-of-the-art RF heating system. The multi-channel RF supervision module developed in this work outperforms state-of-the-art counterparts. The detection of head motion in a hyperthermia setting was demonstrated for the first time with the RF supervision module. This work synergistically connects research and development in computer science, physics, and life science. The infrastructure developed in this work forms a technological basis for future ThermalMR applications.

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.

Erdbeben gehören zu den zerstörerischsten Naturgefahren auf diesem Planeten. Obwohl Erdbeben seit Jahrtausenden dokumentiert sing, bleiben viele Fragen zu Erdbeben unbeantwortet. Eine Frage ist die Vorhersagbarkeit von Brüchen: Inwieweit ist es möglich, die endgültige Größe eines Bebens zu bestimmen, bevor der zugrundeliegende Bruchprozess endet? Diese Frage ist zentral für Frühwarnsysteme. Die bisherigen Forschungsergebnisse zur Vorhersagbarkeit von Brüchen sind widersprüchlich. Die Menge an verfügbaren Daten für Erdbebenforschung wächst exponentiell und hat den Tera- bis Petabyte-Bereich erreicht. Während viele klassische Methoden, basierend auf manuellen Datenauswertungen, hier ihre Grenzen erreichen, ermöglichen diese Datenmengen den Einsatz hochparametrischer Modelle und datengetriebener Analysen. Insbesondere ermöglichen sie den Einsatz von maschinellem Lernen und deep learning. Diese Doktorarbeit befasst sich mit der Entwicklung von Methoden des maschinellen Lernens zur Untersuchung zur Erbebenanalyse. Wir untersuchen zuerst die Kalibrierung einer hochpräzisen Magnitudenskala in einem post hoc Scenario. Nachfolgend befassen wir uns mit Echtzeitanalyse von Erdbeben mittels deep learning. Wir präsentieren TEAM, eine Methode zur Frühwarnung. Auf TEAM aufbauend entwickeln wir TEAM-LM zur Echtzeitschätzung von Lokation und Magnitude eines Erdbebens. Im letzten Schritt untersuchen wir die Vorhersagbarkeit von Brüchen mittels TEAM-LM anhand eines Datensatzes von teleseismischen P-Wellen-Ankünften. Dieser Analyse stellen wir eine Untersuchung von Quellfunktionen großer Erdbeben gegenüber. Unsere Untersuchung zeigt, dass die Brüche großer Beben erst vorhersagbar sind, nachdem die Hälfte des Bebens vergangen ist. Selbst dann können weitere Subbrüche nicht vorhergesagt werden. Nichtsdestotrotz zeigen die hier entwickelten Methoden, dass deep learning die Echtzeitanalyse von Erdbeben wesentlich verbessert. / Earthquakes are among the largest and most destructive natural hazards known to humankind. While records of earthquakes date back millennia, many questions about their nature remain open. One question is termed rupture predictability: to what extent is it possible to foresee the final size of an earthquake while it is still ongoing? This question is integral to earthquake early warning systems. Still, research on this question so far has reached contradictory conclusions. The amount of data available for earthquake research has grown exponentially during the last decades reaching now tera- to petabyte scale. This wealth of data, while making manual inspection infeasible, allows for data-driven analysis and complex models with high numbers of parameters, including machine and deep learning techniques. In seismology, deep learning already led to considerable improvements upon previous methods for many analysis tasks, but the application is still in its infancy. In this thesis, we develop machine learning methods for the study of rupture predictability and earthquake early warning. We first study the calibration of a high-confidence magnitude scale in a post hoc scenario. Subsequently, we focus on real-time estimation models based on deep learning and build the TEAM model for early warning. Based on TEAM, we develop TEAM-LM, a model for real-time location and magnitude estimation. In the last step, we use TEAM-LM to study rupture predictability. We complement this analysis with results obtained from a deep learning model based on moment rate functions. Our analysis shows that earthquake ruptures are not predictable early on, but only after their peak moment release, after approximately half of their duration. Even then, potential further asperities can not be foreseen. While this thesis finds no rupture predictability, the methods developed within this work demonstrate how deep learning methods make a high-quality real-time assessment of earthquakes practically feasible.

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.