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.

Process Mining ermöglicht die Analyse von Event Logs. Jede Aktivität ist durch ein Event in einem Trace recorded, welcher jeweils einer Prozessinstanz entspricht. Traces können sensible Daten, z.B. über Patienten enthalten. Diese Dissertation adressiert Datenschutzrisiken für Trace Daten und Process Mining. Durch eine empirische Studie zum Re-Identifikations Risiko in öffentlichen Event Logs wird die hohe Gefahr aufgezeigt, aber auch weitere Risiken sind von Bedeutung. Anonymisierung ist entscheidend um Risiken zu adressieren, aber schwierig weil gleichzeitig die Verhaltensaspekte des Event Logs erhalten werden sollen. Dies führt zu einem Privacy-Utility-Trade-Off. Dieser wird durch neue Algorithmen wie SaCoFa und SaPa angegangen, die Differential Privacy garantieren und gleichzeitig Utility erhalten. PRIPEL ergänzt die anonymiserten Control-flows um Kontextinformationen und ermöglich so die Veröffentlichung von vollständigen, geschützten Logs. Mit PRETSA wird eine Algorithmenfamilie vorgestellt, die k-anonymity garantiert. Dafür werden privacy-verletztende Traces miteinander vereint, mit dem Ziel ein möglichst syntaktisch ähnliches Log zu erzeugen. Durch Experimente kann eine bessere Utility-Erhaltung gegenüber existierenden Lösungen aufgezeigt werden. / Process mining analyzes business processes using event logs. Each activity execution is recorded as an event in a trace, representing a process instance's behavior. Traces often hold sensitive info like patient data. This thesis addresses privacy concerns arising from trace data and process mining. A re-identification risk study on public event logs reveals high risk, but other threats exist. Anonymization is vital to address these issues, yet challenging due to preserving behavioral aspects for analysis, leading to a privacy-utility trade-off. New algorithms, SaCoFa and SaPa, are introduced for trace anonymization using noise for differential privacy while maintaining utility. PRIPEL supplements anonymized control flows with trace contextual info for complete protected logs. For k-anonymity, the PRETSA algorithm family merges privacy-violating traces based on a prefix representation of the event log, maintaining syntactic similarity. Empirical evaluations demonstrate utility improvements over existing techniques.

Die Kernaufgabe der parameterisierten Komplexität ist zu verstehen, wie Eingabestruktur die Problemkomplexität beeinflusst. Wir untersuchen diese Fragestellung aus einer granularen Perspektive und betrachten Problem-Parameter-Kombinationen mit einfach exponentieller Laufzeit, d.h., Laufzeit a^k n^c, wobei n die Eingabegröße ist, k der Parameterwert, und a und c zwei positive Konstanten sind. Unser Ziel ist es, die optimale Laufzeitbasis a für eine gegebene Kombination zu bestimmen. Für viele Zusammenhangsprobleme, wie Connected Vertex Cover oder Connected Dominating Set, ist die optimale Basis bezüglich dem Parameter Baumweite bekannt. Die Baumweite gehört zu der Klasse der Weiteparameter, welche auf natürliche Weise zu Algorithmen mit dem Prinzip der dynamischen Programmierung führen. Im ersten Teil dieser Dissertation untersuchen wir, wie sich die optimale Laufzeitbasis für diverse Zusammenhangsprobleme verändert, wenn wir zu ausdrucksstärkeren Weiteparametern wechseln. Wir entwerfen neue parameterisierte Algorithmen und (bedingte) untere Schranken, um diese optimalen Basen zu bestimmen. Insbesondere zeigen wir für die Parametersequenz Baumweite, modulare Baumweite, und Cliquenweite, dass die optimale Basis von Connected Vertex Cover bei 3 startet, sich erst auf 5 erhöht und dann auf 6, wobei hingegen die optimale Basis von Connected Dominating Set bei 4 startet, erst bei 4 bleibt und sich dann auf 5 erhöht. Im zweiten Teil gehen wir über Weiteparameter hinaus und analysieren restriktivere Arten von Parametern. Für die Baumtiefe entwerfen wir platzsparende Verzweigungsalgorithmen. Die Beweistechniken für untere Schranken bezüglich Weiteparametern übertragen sich nicht zu den restriktiveren Parametern, weshalb nur wenige optimale Laufzeitbasen bekannt sind. Um dies zu beheben untersuchen wir Knotenlöschungsprobleme. Insbesondere zeigen wir, dass die optimale Basis von Odd Cycle Transversal parameterisiert mit einem Modulator zu Baumweite 2 den Wert 3 hat. / The question at the heart of parameterized complexity is how input structure governs the complexity of a problem. We investigate this question from a fine-grained perspective and study problem-parameter-combinations with single-exponential running time, i.e., time a^k n^c, where n is the input size, k the parameter value, and a and c are positive constants. Our goal is to determine the optimal base a for a given combination. For many connectivity problems such as Connected Vertex Cover or Connecting Dominating Set, the optimal base is known relative to treewidth. Treewidth belongs to the class of width parameters, which naturally admit dynamic programming algorithms. In the first part of this thesis, we study how the optimal base changes for these connectivity problems when going to more expressive width parameters. We provide new parameterized dynamic programming algorithms and (conditional) lower bounds to determine the optimal base, in particular, we obtain for the parameter sequence treewidth, modular-treewidth, clique-width that the optimal base for Connected Vertex Cover starts at 3, increases to 5, and then to 6, whereas the optimal base for Connected Dominating Set starts at 4, stays at 4, and then increases to 5. In the second part, we go beyond width parameters and study more restrictive parameterizations like depth parameters and modulators. For treedepth, we design space-efficient branching algorithms. The lower bound techniques for width parameterizations do not carry over to these more restrictive parameterizations and as a result, only a few optimal bases are known. To remedy this, we study standard vertex-deletion problems. In particular, we show that the optimal base of Odd Cycle Transversal parameterized by a modulator to treewidth 2 is 3. Additionally, we show that similar lower bounds can be obtained in the realm of dense graphs by considering modulators consisting of so-called twinclasses.