Search

Pathology is the final diagnostic step for a variety of diseases, such as cancer or neurological disorders. Driven by advances in deep learning-based computer vision paired with an increased digitalization of workflows, computational pathology has recently attracted interest by the machine learning community. This thesis develops several machine learning systems applied to pathology, ranging from biomedical research to its application in routine diagnostics. Here, a focus is put on explainable machine learning that aims at uncovering the intrinsic decision processes that learning machines infer from data. First, a method is proposed to learn the estrogen receptor status—an important biomarker for prognosis and therapy selection in breast cancer—from routine Haematoxylin-Eosin images, showing that an end-to-end feature learning approach outperforms state-of-the-art methods. By using explanation techniques, we are able to link the estrogen receptor status, that is usually measured with an additional immunohistochemical procedure, to the tumor morphology observed in the Haematoxylin-Eosin images. Our experiments show the model’s predictions are based on biologically meaningful morphological features, such as the histological subtype of the tumor. Moreover, the model also responds to unexpected features, e. g. the morphology of tumor stroma, thereby generating hypotheses for novel biomarkers. Secondly, we collect a large and diverse image dataset of diagnostically relevant cells and objects in cerebrospinal fluid samples, that are routinely used to diagnose neurological disorders. We show that an ensemble of convolutional neural networks is able to reliably classify these data and performs on par with 7 human raters without access to clinical information. Furthermore, we propose a novel data partitioning scheme for cross-validation with grouped, imbalanced datasets and apply it to develop our model. A thorough analysis of the model’s representation space and learned cytological features with the help of explanation methods suggests that the model employs plausible, generalizable decision strategies similar to humans. Lastly, we examine the diagnostic problem of discriminating primary lung cancer from metastases of head-and-neck cancer. This discrimination is crucial for prognosis and treatment but has been previously impossible for the majority of patients. Using DNA methylation profiles, we are able to solve this dilemma with high accuracy by machine learning classifiers and use explanation methods to show that the model focuses its prediction on plausible biological processes. In conclusion, this thesis contributes machine learning systems for the solution of research problems as well as clinically relevant diagnostic tasks in diverse branches of pathology. For all these applications, explainable machine learning is employed and used to validate the models and propose novel biomarkers., Der finale Schritt in der Diagnose verschiedenster Krankheiten wie Krebs oder neurologischer Leiden ist deren pathologische Einschätzung. Fortschritte auf dem Gebiet des Deep-Learning-gestützten maschinellen Sehens kombiniert mit einer fortschreitenden Digitalisierung der Arbeitsabläufe haben dazu geführt, dass die rechnerunterstützte Pathologie in den letzten Jahren das Interesse von KI-Forschern und -Entwicklern geweckt hat. Diese Dissertation entwickelt mehrere Anwendungen von maschinellem Lernen in der Pathologie und umfasst dabei den Einsatz in der biomedizinischer Forschung bis hin zur konkreten Nutzung in der Routinediagnostik. Dabei wird ein Schwerpunkt auf das erklärbare maschinelle Lernen gelegt, welches versucht, die durch Maschinen gelernten Entscheidungsprozesse für den Menschen transparent zu machen. Zunächst wird eine Methode beschrieben, wie sich der Östrogen-Rezeptor-Status – ein wichtiger Biomarker für die Prognose und Therapieauswahl bei Brustkrebs – aus Hämatoxylin-Eosin-Bildern lernen lässt. Hierbei zeigen unsere Experimente, dass ein Ende-zu-Ende trainiertes Modell anderen aktuellen Methoden überlegen ist. Erklärbarkeitsmethoden erlauben uns, die Verbindung zwischen Östrogen-Rezeptor-Status, der normalerweise durch zusätzliche immunhistochemische Verfahren bestimmt wird, und Tumormorphologie, dargestellt durch die routinemäßig verfügbaren Hämatoxylin-Eosin-Bilder, zu studieren. Unsere Analysen zeigen erstens, dass die Maschine sich bei ihrer Vorhersage auf plausible morphologische Merkmale stützt, wie z. B. den histologischen Subtypen des Tumors. Zweitens spricht die Maschine auch auf unerwartete Merkmale, wie die Morphologie des Tumorstroma, an, was eine Hypothese für die Forschung an neuartigen Biomarkern darstellt. Des Weiteren wird ein großer und diverser Datensatz diagnostisch relevanter Zellen und Objekten in Cerebrospinalflüssigkeit, die routinemäßig für die Diagnose neurologischer Symptome eingesetzt wird, akquiriert. Wir können zeigen, dass künstliche neuronale Netze diese Daten zuverlässig klassifizieren können und dabei eine ähnliche Genauigkeit aufweisen wie sieben Pathologen. Außerdem wird ein neues Verfahren vorgestellt, wie Daten für die Kreuzvalidierung aufgeteilt werden können, falls die Daten sowohl gruppiert sind als auch eine unbalancierte Klassenverteilung aufweisen, und zur Entwicklung der Maschine angewendet. Eine sorgfältige Analyse des Merkmalsraums des Modells sowie der gelernten zytologischen Merkmale mithilfe von Erklärbarkeitsmethoden zeigt, dass das Modell nachvollziehbare und generalisierbare Entscheidungsstrategien anwendet, die dem menschlichen Vorgehen nahekommen. Schließlich wird das diagnostische Problem der Unterscheidung zwischen einem primären Lungentumor und sekundären Metastasen eines Kopf-Hals-Tumors betrachtet. Diese Unterscheidung ist entscheidend für Prognose und Behandlung, jedoch war diese bisher für die Mehrheit der Patienten unmöglich. Basierend auf dem DNA-Methylierungsprofil des Tumors wird eine Lernmaschine entwickelt, die dieses Dilemma mit hoher Genauigkeit auflöst und mit Hilfe von Erklärbarkeitsmethoden kann gezeigt werden, dass die Vorhersage des Modells auf plausiblen biologischen Prozessen beruht. Der Beitrag dieser Dissertation besteht also aus mehreren intelligenten Systemen für die Lösung von sowohl forschungsnahen Fragestellungen wie auch klinisch relevanten diagnostischen Problemen in verschiedenen Zweigen der Pathologie. Alle vorgestellten Anwendungen werden dabei durch erklärbares maschinelles Lernen komplementiert, welches für die Validierung der Modelle einerseits sowie für die Suche nach neuen Biomarkern andererseits angewendet wird.

Das interdisziplinäre Foschungsprojekt „Decoding Antisemitism“ dient der Untersuchung von Antisemitismus im Internet. Seit Sommer 2020 ist dieses dreijährige Pilotprojekt am Zentrum für Antisemitismusforschung (ZfA) an der TU Berlin angesiedelt und wird in Zusammenarbeit mit der HTW Berlin und dem King’s College London (KCL) durchgeführt. Beim Untersuchungsgegenstand handelt es sich um Antisemitismus in den Kommentarbereichen von Medien-Webseiten des politischen Mainstream in Deutschland, Frankreich und Großbritannien sowie deren Social Media-Profile. Über einen Mixed Methods-Zugang werden diskursive Trends in den drei europäischen Ländern und unterschiedliche verbale und visuelle Ausformungen von Antisemitismus qualitativ, quantitativ sowie KI-gestützt analysiert. Das Interaktive Web bietet sich aufgrund seiner zentralen Rolle im gesellschaftlichen Diskurs als Untersuchungsgegenstand an. Mit der Analyse von Kommentarbereichen jener Medien, die dem politisch gemäßigten Feld zuzurechnen sind, erschließt das Forscher*innenteam ein bislang wenig beachtetes Feld – zudem eine drängende Aufgabe, da von der Normalisierung abwertender und ausgrenzender Rhetorik in ebensolchen Milieus eine enorme Gefahr ausgeht. Auf der Basis umfangreicher qualitativer Analysen wird ein Überblick über bisher unbekannte Erscheinungsformen und das tatsächliche Ausmaß von Antisemitismus in diesen europäischen Web-Communitys gewonnen. Die Ergebnisse bieten wiederum die Möglichkeit vielfältiger Gegenstrategien., The interdisciplinary research project "Decoding Antisemitism" aims to investigate antisemitism on the internet. Since summer 2020, this three-year pilot project has been based at the Centre for Research on Antisemitism (ZfA) at TU Berlin and is being carried out in cooperation with HTW Berlin and King's College London (KCL) . The object of study is antisemitism in the comment sections of mainstream political media websites in Germany, France and the UK, as well as their social media profiles. Using a mixed methods approach, discursive trends in the three European countries and different verbal and visual forms of antisemitism are analysed qualitatively, quantitatively and with the help of AI. The interactive web presents itself as an object of study due to its central role in social discourse. By analysing the comments sections of media that belong to the politically moderate field, the research team is opening up a field that has received little attention so far - an urgent task, since the normalisation of derogatory and exclusionary rhetoric in such milieus poses an enormous danger. On the basis of extensive qualitative analyses, an overview of previously unknown manifestations and the actual extent of antisemitism in these European web communities will be gained. The results in turn offer the possibility of diverse counter-strategies., «Decoding Antisemitism» est un projet de recherche interdisciplinaire hébergé par le Centre de Recherche sur l’Antisémitisme (ZfA) de TU Berlin, en collaboration avec HTW Berlin et le King’s College London (KCL). Depuis l’été 2020, et pour trois ans, ce projet pilote a pour objectif d’examiner la façon dont les contenus antisémites émergent et circulent dans les sections commentaires des médias mainstream en Allemagne, au Royaume-Uni et en France. S’inscrivant au croisement des Sciences du Langage et de l’Intelligence Artificielle, le projet étudie, d’un point de vue aussi bien qualitatif et quantitatif, les différentes formes verbales et visuelles de l’antisémitisme en ligne. Jouant un rôle central dans le discours social, le web interactif constitue l’objet d’étude de ce projet. Plus particulièrement, l’analyse de l’antisémitisme dans les sections commentaires des médias mainstream permet d’examiner un terrain jusqu’ici peu exploré - une tâche urgente, car la normalisation de la rhétorique dérogatoire et d'exclusion dans ces milieux représente un énorme danger. Sur la base d'analyses qualitatives, une vue d'ensemble des manifestations jusqu'à maintenant inconnues et de l'étendue réelle de l'antisémitisme dans ces communautés web européennes sera acquise. Les résultats offrent à leur tour la possibilité de développer diverses contre-stratégies.

Approximate data analysis trades off accuracy for faster or cheaper results. Instead of performing data analyses on the entire data, space-efficient summaries are constructed and evaluated. Applications from various domains, such as databases, computational biology, and machine learning, require accepting a loss in accuracy to gain the desired throughput and response times with limited resources. Specialized parallel processors, such as graphics processing units (GPUs) and field-programmable gate arrays (FPGAs), promise substantial gains in the efficiency of approximate analyses. However, exploiting these architectures is challenging as it requires considering an architecture's properties and explicitly designing and implementing for parallelism. In this thesis, we investigate novel approaches to maintaining and evaluating data summaries on parallel processors: First, we propose kernel density models for GPU-accelerated join selectivity estimation in relational databases. Our estimators do not require common error-prone assumptions and typically provide higher accuracy than the state of the art. Furthermore, the estimators fit the massively parallel computations supported by modern GPUs. In contrast to central processing units (CPUs), our approach allows for larger model sizes and more accurate estimates within the same time budget. Second, we propose Scotch, a holistic approach to implementing FPGA-accelerated sketching at the full rate of the interconnect. The framework generates hardware descriptions for a broad class of sketches based on a common abstraction and domain-specific language. Furthermore, Scotch automatically maximizes the sketch size to boost accuracy. As these tasks commonly require an FPGA expert, Scotch makes FPGA-accelerated sketching more accessible to software engineers. Third, we propose an optimistic data-parallel architecture for FPGA-accelerated sketch summary maintenance. We share resources among inputs instead of pessimistically replicating all resources for every input. Thus, our optimistic architecture reduces the resources required to achieve given throughput for applications that tolerate stalls in processing due to resource congestion. Overall, this thesis shows that specialized parallel processors can substantially increase the efficiency of approximate data analysis while the entry barrier for using them can be lowered substantially by systems and abstractions., Approximative Datenanalyse ermöglicht es die Genauigkeit von Ergebnissen gegen schnellere oder günstigere Berechnungen einzutauschen. Anstelle der Durchführung von Datenanalysen auf der Gesamtheit der Daten, werden speichereffiziente Zusammenfassungen erzeugt und ausgewertet. Anwendungen aus diversen Bereichen, wie Datenbanken, Bioinformatik und maschinellem Lernen, erfordern diesen Verlust von Genauigkeit, um Anforderungen bezüglich Durchsatz und Antwortzeiten mit begrenztem Ressourcenaufwand zu erreichen. Der aktuelle Trend zu spezialisierten parallelen Rechenarchitekturen wie Grafikprozessoren (GPUs) und Field-Programmable Gate Arrays (FPGAs) verspricht diesen Austausch zusätzlich zu verbessern. Jedoch ist die Verwendung dieser Architekturen nicht trivial, da sie es erfordert, die Eigenschaften der verwendeten Architektur einzubeziehen und Parallelität explizit beim Entwurf und der Implementierung zu berücksichtigen. In dieser Arbeit werden Ansätze zur Erzeugung und Auswertung von Datenzusammenfassungen mit Hilfe paralleler Rechenarchitekturen vorgestellt: Als Erstes stellen wir Kerndichtemodelle für GPU-beschleunigte Schätzung von Joinselektivitäten in relationalen Datenbanken vor. Unsere Schätzer benötigen hierzu keine der gängigen Annahmen und liefern bessere Ergebnisse als der Stand der Technik. Darüber hinaus passen die Schätzer gut zu den von modernen GPUs unterstützten massivparallelen Berechnungen, was im Vergleich zu Hauptprozessoren (CPUs) größere Modelle und dadurch genauere Schätzungen im selben Zeitbudget ermöglicht. Als Zweites stellen wir Scotch vor, einen holistischen Ansatz für die Implementierung FPGA-beschleunigter Erzeugung von Sketchzusammenfassungen mit der vollen Rate des verwendeten Interconnects. Das Framework generiert Hardwarebeschreibungen für eine umfassende Klasse von Sketchingalgorithmen basierend auf einer gemeinsamen Abstraktion und einer entsprechenden domänenspezifischen Sprache. Darüber hinaus maximiert Scotch die Größe der Sketchzusammenfassung automatisch, um die Genauigkeit der Ergebnisse zu maximieren. Da diese Aufgaben üblicherweise einen FPGA-Experten erfordern, macht Scotch das FPGA-beschleunigte Erzeugen von Sketchzusammenfassungen zugänglicher für Softwareentwickler. Als Drittes stellen wir eine optimistische Architektur für die FPGA-beschleunigte datenparallele Erzeugung von Sketchzusammenfassungen vor. Wir schlagen vor, Ressourcen zwischen parallelen Eingabewerten zu teilen, statt pessimistisch alle Ressourcen für jeden Eingabewert zu replizieren. Unsere optimistische Architektur verringert den Verbrauch von Ressourcen, um einen hohen Durchsatz über Datenparallelität zu erreichen, sofern die Anwendung Unterbrechungen durch Überlastung von Ressourcen toleriert. Insgesamt zeigt diese Arbeit, dass spezialisierte parallele Rechenarchitekturen die Effizienz von approximierten Datenanalysen erheblich verbessern können und dass die Eintrittsbarriere für ihre Nutzung durch geeignete Systeme und Abstraktionen gesenkt werden kann.

Vision is the most crucial sense that a human being cannot live independently without. Visual prosthesis has been proposed as a promising solution to restore partial vision to people who lost their vision. Visual prostheses exploit the functional parts in the eye and the brain to enable partial restoration of vision. Despite its initial success, some challenges arise that hinder the ability of the patients implanted with visual prostheses to correctly recognize and localize objects. In this thesis, we introduce a variety of solutions to enhance the ability of visual prostheses users to correctly recognize and localize objects. Image processing and deep learning techniques are proposed in this thesis to simplify and better represent objects for visual prostheses users. One crucial challenge that arises in a typical visual prosthetic device is electrodes dropout, where some electrodes malfunction throughout time. To address this challenge, an optimal solution is proposed by translating the object of interest to a location in the visual field of the user such that the minimum amount of dropout exists. Another challenge that visual prostheses users face is the complexity of the viewed scene that is barely recognizable due to the low spatial and radiometric resolutions available through visual prostheses. Accordingly, we propose the utilization of clip art representation of images instead of the actual real photo to ease the recognition of any arbitrary object. We propose the use of You Only Look Once (YOLO), a deep learning model to retrieve the clip art that corresponds to an object detected by YOLO in a high-resolution photo. In addition, a deep learning-based approach using Generative Adversarial Networks (GANs), named PVGAN, is proposed to generate clip art images from given high-resolution photos to allow better and easier perception of the images in a visual prosthetic device. Finally, we combine three enhancement techniques with the GAN-generated clip art which are edge sharpening, corners sharpening and dropout handling to enhance object recognition and localization. The combined approach is tested in a mixed reality environment to simulate the visual representation perceived by visual prostheses users. A number of prosthetic vision simulation experiments were conducted on normally/correctly sighted participants to measure the efficacy of the proposed approaches using both computer screen and mixed reality. The results demonstrate that the usage of the proposed techniques enhances the ability of people to correctly recognize and localize objects. This could allow visual prostheses users to regain back their confidence and independence., Das Sehen ist der wichtigste Sinn, ohne den ein Mensch nicht unabhängig leben kann. Sehprothesen wurden als viel versprechende Lösung vorgeschlagen, um Menschen, die ihre Sehkraft verloren haben, zu helfen und ihnen ein teilweises Sehvermögen zu geben. Sie nutzen die funktionellen Teile des Auges und des Gehirns, um eine teilweise Wiederherstellung des Sehvermögens zu erzielen. Trotz anfänglicher Erfolge gibt es einige Probleme hinsichtlich der Fähigkeit der mit Sehprothesen ausgestatteten Patienten, Objekte richtig zu erkennen und zu lokalisieren. In dieser Arbeit stellen wir eine Reihe von Lösungen vor, um die Fähigkeiten von Sehprothesenträgern zu verbessern, Objekte richtig zu erkennen und zu lokalisieren. Techniken der Bildverarbeitung und des Deep Learning zur vereinfachten Nutzung von Sehprothesen werden entwickelt. Eine entscheidende Herausforderung, die bei einer typischen Sehprothese auftritt, ist der Ausfall von einzelnen Elektroden im Laufe der Zeit der Benutzung. Zur Bewältigung dieser Herausforderung wird eine optimale Lösung vorgeschlagen, indem das Objekt des Interesses an eine Position des Implantats im Gesichtsfeld des Benutzers verschoben wird, so dass das die Fläche des Objektsegments von möglichst wenigen ausfallenden Elektroden betroffenist. Eine weitere Herausforderung für die Nutzer von Sehprothesen ist die Komplexität der betrachteten Szene, die aufgrund der geringen räumlichen und radiometrischen Auflösung, die mit Sehprothesen möglich ist, kaum erkennbar ist. Dementsprechend schlagen wir die Verwendung von clip art-Darstellungen der abgebildeten Objekte anstelle der realen Fotos vor, um die Erkennung beliebiger Objekte zu erleichtern. Wir schlagen die Verwendung von You Only Look Once (YOLO) vor, einem Modell für tiefes Lernen, um die clip art Darstellung abzurufen, die einem Objekt entspricht, das, auch mittles YOLO, in einem hochauflösenden Foto erkannt wurde. Darüber hinaus wird ein auf Deep Learning basierender Ansatz mit generativen adversarialen Netzwerken (GANs), genannt PVGAN, vorgeschlagen, um clip art-Bilder aus gegebenen hochauflösenden Fotos zu generieren, um eine bessere und einfachere Wahrnehmung der Bilder in einer Sehprothese zu ermöglichen. Schließlich kombinieren wir drei Methoden zur Verbesserung der Objekterkennung und lokalisierung mit den GAN-generierten Cliparts, nämlich Kantenschärfung, Eckenschärfung und Dropout. Der kombinierte Ansatz wird in einer Gemischte-Realität-Umgebung getestet, um die visuelle Darstellung zu simulieren, die von Prothesenbenutzern wahrgenommen wird. Eine Reihe von Experimenten zur Simulation des Sehvermögens von Prothesenträgern wurde an normalsichtigen Teilnehmern durchgeführt, um die Wirksamkeit der vorgeschlagenen Ansätze sowohl auf dem Computerbildschirm als auch in der gemischte Realität zu ermitteln. Die Ergebnisse zeigen, dass die Anwendung der vorgeschlagenen Techniken die Fähigkeit von Menschen verbessert, Objekte korrekt zu erkennen und zu lokalisieren. Dies könnte Nutzern von Sehprothesen ermöglichen, ihr Selbstvertrauen und ihre Unabhängigkeit wiederzuerlangen.

In this thesis, we derive models and algorithms for a large variety of collective choice problems, while placing our focus on scalability. That is, even though parts of the problem ― the number of outcomes, of decisions, or of agents ― may become very large, we aim to keep the cognitive effort for the agents and the computational effort of determining the outcome of collective choice rules low. Beyond that, we are particularly interested in properties of collective choice rules that capture (proportional) representation of the agents' preferences. This thesis is divided into three parts, each of which illustrates one perspective on scalability. In Part I, we study collective choice problems in which the number of outcomes is exponential in the size of the description of the problem. We study three different settings, all of which can be seen as variants of the well-studied apportionment setting. First, we introduce approval-based apportionment, a generalization in which voters indicate approval ballots over parties. We provide rules that can be computed efficiently and satisfy strong guarantees of proportional representation, i.e., core-stability, and extended justified representation in combination with committee monotonicity, respectively. Second, we study a subdomain of approval-based apportionment motivated by repeated matching markets. Despite the fact that the number of outcomes is even double-exponential in the size of the input, we show that most rules commonly used in approval-based committee voting can be computed efficiently in this setting. To this end, we provide new algorithms that exploit the structure of the subdomain. Third, we study weighted fair allocation, which can be seen as another generalization of apportionment. We focus on picking sequences derived from well-studied apportionment methods and analyze these with respect to envy-freeness, proportionality, and monotonicity. Part II studies liquid democracy, which is motivated by situations in which the same set of agents is confronted with a high number of collective decisions. To increase participation rates, liquid democracy gives agents the possibility to delegate their votes to other agents. We study an extension of liquid democracy in which agents can indicate a set of approved delegates and a preference relation among them. In order to implement this extension, we need to specify a so-called delegation rule. First, we carry out an extensive axiomatic and experimental analysis on the space of delegation rules. Second, we observe that an important subclass of delegation rules can be interpreted as selecting branchings in a directed graph. We suggest and characterize popular branchings (i.e., weak Condorcet winners among the set of branchings), and provide a polynomial-time algorithm for finding a popular branching if it exists. Part III is motivated by collective choice problems for which the number of agents may become very large. Here, instead of asking every agent for their full preferences, a natural approach lets agents answer pairwise comparison queries which induces an estimate of the majority relation. Based on this idea, we consider two approaches. First, we introduce the margin of victory for tournament solutions, which helps to evaluate how robust a winning alternative is with respect to small changes to the majority relation. We analyze this robustness measure for several well-studied tournament solutions with respect to computational complexity and structural properties. Second, we study a generalization of the dueling bandits problem, an online learning problem where the learner performs pairwise comparison queries in order to efficiently and accurately determine a good alternative. Even though the outcome space in this generalization is exponential in the number of alternatives, we develop learning algorithms that only perform a polynomial number of pairwise comparisons., In dieser Arbeit entwickeln wir Modelle und Algorithmen für eine Vielzahl von kollektiven Entscheidungsproblemen, wobei wir unseren Schwerpunkt auf die Skalierbarkeit legen. Das heißt, auch wenn Teile des Problems ― wie etwa die Anzahl der Ergebnisse, der Entscheidungen oder der Agenten ― sehr groß werden können, möchten wir den kognitiven Aufwand für die Agenten und den Rechenaufwand für die Algorithmen der kollektiven Entscheidungsregeln gering halten. Darüber hinaus sind wir besonders an Eigenschaften interessiert, die widerspiegeln, in welchem Maße kollektive Entscheidungsregeln die (proportionale) Repräsentation der Agenten gewährleisten. Diese Arbeit ist in drei Teile gegliedert, die jeweils eine Perspektive der Skalierbarkeit beleuchten. In Teil I untersuchen wir kollektive Entscheidungsprobleme, bei denen die Anzahl der potentiellen Ergebnisse exponentiell zur Größe der Problembeschreibung ist. Wir untersuchen drei verschiedene Szenarien, die alle als Varianten des gut untersuchten Sitzzuteilungsproblems (apportionment problem) betrachtet werden können. Als erstes führen wir approval-based apportionment ein, eine Verallgemeinerung, bei der Wähler eine beliebige Menge an Parteien wählen können. Wir zeigen die Existenz von Regeln, die effizient berechnet werden können und starke Garantien der proportionalen Repräsentation, nämlich core stability sowie extended justified representation in Kombination mit committee monotonicity erfüllen. Des Weiteren untersuchen wir eine Unterdomäne von approval-based apportionment, welche durch wiederholte Matching-Märkte motiviert ist. Trotz der Tatsache, dass die Anzahl der potentiellen Ergebnisse sogar zweifach exponentiell zur Größe der Eingabe ist, zeigen wir, dass ein Großteil der Regeln, die üblicherweise in Komiteewahlen verwendet werden, in dieser Unterdomäne effizient berechnet werden können. Zu diesem Zweck entwickeln wir neue Algorithmen, welche die Struktur der Unterdomäne ausnutzen. Zuletzt untersuchen wir weighted fair allocation, das eine weitere Verallgemeinerung des Sitzzuteilungsproblems darstellt. Wir konzentrieren uns auf Auswahlsequenzen (picking sequences), die von bekannten Apportionment-Methoden abgeleitet sind, und analysieren diese im Hinblick auf Neidfreiheit, Proportionalität und Monotonität. Teil II untersucht Liquid Democracy, ein neues Modell zur kollektiven Entscheidungsfindung, welches durch Situationen motiviert ist, in denen dieselbe Gruppe von Agenten mit einer großen Anzahl von Entscheidungen konfrontiert ist. Um die Partizipationsrate zu erhöhen, gibt Liquid Democracy den Agenten die Möglichkeit, ihre Stimmen an andere Agenten zu delegieren. Wir untersuchen eine Erweiterung von Liquid Democracy, in der Agenten eine Menge von ausgewählten Delegierten und eine Präferenzrelation zwischen diesen angeben können. Um diese Erweiterung zu implementieren, müssen wir jedoch eine sogenannte Delegationsregel festlegen. Zunächst führen wir eine umfangreiche axiomatische und experimentelle Analyse von Delegationsregeln durch. Darüber hinaus stellen wir fest, dass eine wichtige Unterklasse von Delegationsregeln insbesondere branchings in einem gerichteten Graphen auswählt. Wir schlagen die Betrachtung von populären branchings, die einem schwachen Condorcet-Gewinner auf der Menge der branchings entsprechen, vor und charakterisieren diese. Darauf aufbauend entwickeln wir einen Polynomialzeit-Algorithmus, der ein populäres branching findet, sofern dieses existiert. Teil III ist durch kollektive Entscheidungsprobleme motiviert, bei denen die Anzahl der Agenten groß werden kann. Anstatt jeden Agenten nach seinen vollständigen Präferenzen zu fragen, lassen wir die Agenten paarweise Vergleiche beantworten, welche eine Abschätzung der Mehrheitsrelation induzieren. Darauf aufbauend verfolgen wir zwei Ansätze. Erstens führen wir das Konzept der margin of victory für Turnierlösungen ein, welches dabei hilft zu bewerten wie robust die ausgewählte Menge der Turnierlösung in Bezug auf kleine Änderungen in der Mehrheitsrelation ist. Wir analysieren dieses Robustheitsmaß für mehrere bekannte Turnierlösungen im Hinblick auf die Berechnungskomplexität und strukturelle Eigenschaften. Zweitens untersuchen wir eine Verallgemeinerung des dueling bandits-Problems, ein Online-Lernproblem, bei dem der Lernende paarweise Vergleiche durchführt, um schnell eine gute Alternative zu identifizieren. Obwohl die Größe des Strategieraum des Lernalgorithmus in dieser Verallgemeinerung exponentiell in der Anzahl der Alternativen ist, entwickeln wir Lernalgorithmen, die nur eine polynomielle Anzahl von Vergleichen durchführen.

The analysis of textual variants allows us to explore how a given literary text came into being. This involves the analysis of the author’s writing process and aesthetic inspirations but also analysing others who influenced the history of the text, for example as a translator or as a publisher. This further involves the inquiry into the historical and social circumstances under which the text was carried forward. These investigations are particularly relevant to the humanities not only because important contributions can be attributed to the respective person, but also because together they are the basis on which literary scholars then constitute the text: By comparison they can decide which textual variant is most adequate in the context of their specific research. The path digital editors take to approach this question is that they gather source material to identify traces of alterations and compile a document with a complex annotation structure that contains all available textual variants. Machine learning and computational humanities methods have the potential to contribute to this type of research in several ways, because they can (1) improve data availability with automated enrichment, (2) examine a broader collection through their ability to process textual sources at high speed, and (3) expand the existing catalog of methodology in literary studies. The major challenge is that methods in natural language processing as a sub-field of machine learning assume a simplified, linear textual basis, and thus are not able to compare different textual variants with each other. In Part 1, it will be addressed how linear textual variants can be extracted from complex document structures so that existing text processing methods can be applied. In Part 2, it will be investigated how the methodologies of the different disciplines of machine learning and literary studies can be connected, to ensure that the proposed method and the obtained findings present a useful contribution in the respective disciplines. Here, we focus on the notion of text representation and introduce the new Word2Vec with Structure Prediction method for generating text representations in the context of structured corpora and show how it benefits the digital humanities. Finally in Part 3, novel, robust natural language processing methods that are capable of comparing different textual variants are presented and applied in two different research contexts: In the analysis of a historical collection of letters from individuals who shaped intellectual Berlin around 1800 and in the study of the famous Schlegel-Tieck Shakespeare translation, with its translatorship origin still partly unexplained today. Overall, this work aims to illustrate how transdisciplinary research between literary studies and machine learning leads to new insights and thus benefits both fields., Die Analyse von Textvarianten ermöglicht es zu erkunden, wie ein vorliegender, literarischer Text entstanden ist. Dies umfasst die Analyse der künstlerischen Inspirationen, aber auch die konkreten Personen, die in ihrer Rolle, sei es bspw. Autor, Übersetzer oder Verleger, Einfluss auf die Textgeschichte hatten, bis hin zur Untersuchung der historisch-sozialen Umstände, unter denen der Text weitergegeben wurde. Diese Untersuchungen sind so relevant für die Geisteswissenschaften, weil sie gemeinsam Grundlage sind, auf der Literaturwissenschaftler dann einen adäquaten Text konstituieren. Der Ansatz der digitalen Editionswissenschaften ist es, dafür Quelldokumente sammeln, die Spuren von Textänderungen einer bestimmten Person bzw. eines bestimmten Kontexts enthalten und diese in einer komplexen Dokumentstruktur festzuhalten. Methoden des maschinellen Lernens und der computergestützten Geisteswissenschaft haben das Potenzial auf verschiedene Weise einen Beitrag bei dieser Art der Forschung zu leisten, da sie mit automatisierter Anreicherung die Datenverfügbarkeit verbessern können, sie durch ihre hohe Geschwindigkeit im Verarbeiten von Textquellen eine breitere Quellensammlung untersuchen können und weil sie den existierenden Methodenkatalog der Literaturwissenschaften erweitern. Die große Herausforderung besteht darin, dass existierende Textverarbeitungsmethoden (NLP Methoden) üblicherweise von einer vereinfachten, linearen Textgrundlage ausgehen, also nicht in der Lage sind, verschiedene Textvarianten (textual variants) miteinander zu vergleichen. In dieser Arbeit wird deshalb in einem ersten Schritt erarbeitet, wie aus diesen komplexen Dokumentstrukturen lineare Textvarianten extrahiert werden können, sodass bestehende Textverarbeitungsmethoden angewandt werden können (Teil 1). In einem zweiten Schritt wird erarbeitet, welche Scharnierstellen es gibt, die die Methodiken der stark unterschiedlichen Disziplinen des maschinellen Lernens und der Literaturwissenschaft verbinden, sodass sichergestellt ist, dass die entwickelten Methoden und die damit erzielten Erkenntnisse in der jeweiligen Disziplin auch verwendbar sind. Dabei wird der Fokus auf den Begriff der Textrepräsentation gelegt und die neue Methode Word2Vec with Structure zur Erzeugung von Textrepräsentation im Kontext von strukturierten Korpora vorgestellt und gezeigt, wie diese in den digitalen Geisteswissenschaften verwendet werden kann (Teil 2). Zuletzt werden neue, robuste NLP Methoden vorgestellt, die in der Lage sind, Textvarianten zu vergleichen und diese werden in zwei verschiedenen Forschungskontexten angewandt: Bei der Analyse einer historischen Briefsammlung von Personen, die das intellektuelle Berlin um 1800 geprägt haben und bei der Untersuchung der berühmten Schlegel-Tieckschen Shakespeareübersetzung, mit ihrer bis heute teils ungeklärten Übersetzungsurheberschaft (Teil 3). Insgesamt soll diese Arbeit verdeutlichen, wie eine transdisziplinäre Forschung zwischen Literaturwissenschaft und maschinellem Lernen produktiv neue Ergebnisse in beiden Feldern liefern kann.

The demand for image and video content has increased rapidly over the past decades. In order to meet today’s transmission and storage constraints, efficient compression tools are needed which generate high coding gains. For the accomplishment of the last video coding standards such as H.265/HEVC and H.266/VVC, in-loop filters played an important role. In-loop filters do not only significantly improve the coding efficiency of a video codec, additionally, they often diminish occurring coding artifacts and therefore can restore subjective quality of a video sequence. In this doctoral thesis in-loop filter techniques utilizing Wiener filters are investigated. Wiener filters are the result of an optimization problem to find optimal filter coefficients such that the resulting filtered image, obtained by applying the derived filters to a noisy image, possesses the smallest mean square error compared to a target image among all possible filters for a fixed filter size and shape. The first in-loop tool utilizing successfully Wiener filters in a common video coding standard is the adaptive loop filter (ALF). ALF conducts a classification and a filtering process. The set of all sample locations of an image is partitioned into multiple classes based on local edge and directional information. This ensures the usage of multiple Wiener filters, one for each class. This technique can effectively improve the coding efficiency of a video codec. The performance of Wiener filter techniques seems to rely particularly on how its classification behaves. How does a classification process need to be designed in order to exploit the full potential of Wiener filters? Which image features need to be extracted and utilized for classification such that it benefits the filtering process? Can we also effectively improve visual quality by employing Wiener filters? This thesis tackles the mentioned questions by analyzing Wiener filtering in relation to the following aspects: - Applying multiple classifications by incorporating multiple image features - Classification in a sparse transform domain by utilizing shearlets - Signal-adaptive filtering methods by incorporating a data-driven classification process. In the first part of the thesis, the multiple feature-based classifications adaptive loop filter (MCALF) is presented. Every image is governed by some characteristics which cannot be generally described by only one feature. While the classifier in ALF mainly focuses on local geometric characteristics, many images contain different underlying features such as textures. Multiple classifiers are tested for each image, which lead to a better adaptation to predominant features of the input image. The main part of this thesis motivates and applies the shearlet transform for in-loop filtering, which leads to the development of the shearlet-based intensity classification loop filter (SCLF). SCLF uses an overcomplete and sparsifying transform, the shearlet transform. The basic idea is to achieve a signal-noise separation of the input image in the sparse shearlet domain. Each shearlet transform coefficient is classified into one of multiple classes. All coefficients with similar intensities are grouped into the same class, which eventually gives a partition of the set of all shearlet coefficients. This separates important structures from noise and ensures an accurate reconstruction of original information by performing an inverse shearlet transform combined with Wiener filtering separately for each class. SCLF effectively removes compression artifacts and therefore restores subjective visual quality. In the last part of the thesis a data-driven in-loop filter, the convolutional neural network based in-loop filter (CNNLF), is studied. Here, the classification and the filtering process are derived from a convolutional neural network. Then, a novel signaladaptive second filtering step on top of the CNN-based filtering process is proposed, including the application of Wiener filters. The combination of a learned filtering process with signal-adaptive Wiener filtering can significantly improve the coding efficiency of a video codec., In den letzten Jahrzehnten ist die Nachfrage nach digitalen Bildern und Videos stark gestiegen. Um die Übertragung und Speicherung zu gewährleisten werden effiziente Kompressionsalgorithmen benötigt, die hohe Kompressionsraten erziehen. In den letzten Kompressionsstandards für Videoinhalte, H.265/HEVC und H.266/VVC, spielen In-Loop Filter eine entscheidende Rolle. In-Loop Filter können nicht nur die Kodiereffizienz entscheidend verbessern, sie können auch visuell auffällige Kodierartefakte reduzieren und damit die subjektive Videoqualität verbessern. In dieser Doktorarbeit werden In-Loop Filtertechniken untersucht, die Wiener-Filter benutzen. Wiener-Filter sind das Resultat eines Optimierungsprozesses, welches unter allen Filtern mit gleicher Größe und Form den optimalen Filter sucht, sodass das gefilterte Bild den kleinstmöglichen mittleren quadratischen Fehler im Vergleich zum Originalbild besitzt. Das erste In-Loop Filtertool welches erfolgreich Wiener-Filter in einem Kompressionsstandard für Videoinhalte benutzt, ist der adaptive Loop Filter (ALF). ALF führt einen Klassifizierungs- und einen Filterprozess aus. Die Menge aller Pixel in einem Bild wird auf Grund von lokalen Kanten- und Richtungsinformationen in mehreren Klassen untergliedert. Für jede Klasse wird ein Wiener-Filter verwendet, der alle Pixel in einer Klasse filtert. Diese Technik führt zu hohen Kodiergewinnen. Wie gut Wiener-Filtertechniken funktionieren, hängt stark von der Klassifizierung ab. Wie muss ein Klassifizierungsalgorithmus entworfen werden, um das volle Potenzial von Wiener-Filtern auszuschöpfen? Welche Bildeigenschaften können für die Klassifizierung verwendet werden, sodass es dem Filterprozess dient? Können Wiener-Filter auch die wahrgenommene Bildqualität entscheidend verbessern? Die vorliegende Arbeit setzt sich mit den gestellten Fragen auseinander und analysiert Wiener-Filter unter Bezugnahme folgender Aspekte: - Verwendung von mehreren Klassifizierungsalgorithmen unter Berücksichtigung von mehreren Bildeigenschaften - Klassifizierung in dünnbesetzten Transformationsbereichen wie der Shearlet-Domäne - Signal-angepasste Filterprozesse unter Benutzung von maschinell gelernten Klassifizierern. Im ersten Teil der Arbeit wird das mehrfach klassifizierende adaptive Loop Filter (MCALF) vorgestellt. Jedes Bild wird von verschiedenen Charakteristiken dominiert, welche man nicht mit nur einer Eigenschaft beschreiben kann. Während der Klassifizierer in ALF lokale geometrische Eigenschaften des Bildes verwendet, gibt es Bildmerkmale wie zum Beispiel Texturen, die sich damit nur schwer beschreiben lassen. Mehrere Klassifizierer werden vorgeschlagen und der beste Klassifizierer für jedes Bild bestimmt. Dieses Verfahren führt zu einer besseren Anpassung an entsprechende Bildinhalte. Als nächstes wird die Shearlet-Transformation vorgestellt und ihre Anwendung für In-Loop Filter motiviert. Das führt zu der Entwicklung des shearletbasierten intensitätsklassifizierenden Loop Filters (SCLF). SCLF benutzt eine überbestimmte und dünnbesetzte Shearlet-Transformation. Das Ziel ist es, unter Verwendung der Shearlet-Transformation das Rauschen vom ursprünglichen Signal zu trennen. Jeder Shearlet-Transformationskoeffizient wird zu einer Klasse zugeordnet. Alle Koeffizienten mit der gleichen Intensität werden in die selbe Klasse eingeteilt. Dieser Algorithmus separiert wichtige Informationen von Rauschen und rekonstruiert Originalinformationen unter der Verwendung der inversen Shearlet-Transformation in Kombination mit einer Wiener-Filterung. SCLF entfernt Kompressionsartefakte und verbessert dadurch die subjektive Bildqualität. Im letzten Teil der Arbeit wird ein maschinell gelerntes In-Loop Filter beschrieben, das CNN basierte Loop Filter (CNNLF). Hier werden die Klassifizierung und der Filterprozess von einem faltenden neuronalen Netzwerk abgeleitet. Des Weiteren wird ein signal-angepasstes Wiener-Filter basierender zweiter Filterungsschritt vorgeschlagen, zusätzlich zu der CNN basierten Filterung. Die Kombination aus einem gelernten Filterprozess mit einer signal-angepassten Wiener-Filterung kann die Kodiereffizienz entscheidend steigern.

Over the past two decades, distributed stream processing engines (SPEs) have become a prominent component in the big data management tool-chain to support real-time, stateful data analytics applications on high-volume, high-velocity data streams in cloud deployments. To this end, current SPEs continuously execute Map/Reduce-like pipelines on continuous data and apply data-centric parallelism to scale-out on a cluster of servers.Current SPEs assume so-called commodity hardware as they follow Map/Reduce-like paradigms based on the shared-nothing architecture. Furthermore, SPEs are agnostic to hardware configuration as they rely on managed runtimes, such as a Java Virtual Machine. However, computing infrastructures have improved dramatically their hardware characteristics in the past years. As a result, the common wisdom that cloud providers mainly offer commodity hardware no longer holds. For instance, cloud platform vendors provide powerful compute and network capabilities as they offer servers with high-end CPUs with many cores and large caches as well as high-speed networks, such as Infiniband with Remote Direct Memory Access (RDMA) support. Furthermore, modern hardware infrastructure is highly flexible, as it provides ad-hoc provisioning of resources, which enables scaling the compute and storage capabilities as well as coping with failures, while a deployed application is executed. In this thesis, we show that the current generation of SPEs are hardware-agnostic and cannot leverage the above technology advancements. In fact, we experimentally demonstrate that they perform inefficiently when running on an infrastructure that provides HPC-grade CPUs, high-speed networks, as well as ad-hoc, flexible resource provisioning. To this end, we present solutions to efficiently execute stateful stream processing applications on the modern hardware infrastructure. First, we focus on the scale-up performance of current SPEs to leverage the compute capabilities of the modern hardware. Our analysis shows that SPEs suffer from inefficient memory access patterns that lead to sub-optimal code and data locality. Driven by our analysis, we provide design changes, such as specialized code generation, to the common architecture of an SPE to scale-up on modern hardware. We show that an SPE that follows our guidelines achieves up to two orders of magnitude higher single-node throughput compared to state-of-the-art SPEs. Second, we focus on the scale-out performance of the current SPEs to leverage the high-speed networks with RDMA support. In particular, RDMA hardware has invalidated the common assumption that network is often a bottleneck in distributed data processing systems. However, high-speed networks do not provide "plug-and-play" performance (e.g., using IP-over-InfiniBand) and require a careful co-design of system and application logic. Furthermore, the introduction of RDMA-based data structures in an SPE is challenged by real-time constraints and state consistency guarantees. To this end, we propose Slash, a novel stream processing engine that uses high-speed networks and RDMA to efficiently execute distributed streaming computations. Slash embraces a processing model suited for RDMA acceleration and omits expensive data pre-partitioning, which is the current approach of state-of-the-art SPE to distributed query execution. Overall, our solution achieves a throughput improvement up to two orders of magnitude over existing systems deployed on an InfiniBand network and it is up to a factor of 22 faster than a self-developed solution that relies on RDMA-based data pre-partitioning to scale out query processing. Finally, we focus on the runtime reconfiguration of running streaming applications of the current generation of SPEs to leverage the ad-hoc and flexible provisioning capabilities of the modern cloud computing infrastructure. SPEs need to transparently reconfigure stateful queries during runtime to recover from outages, adjust to varying data rates, and ensure low-latency processing, which are required by industrial setups. However, state-of-the-art SPEs are not ready yet to handle on-the-fly reconfiguration of queries with terabytes of state due to three problems: network overhead for state migration, consistency, and overhead on data processing. We propose Rhino, a library for efficient reconfiguration of running queries in the presence of distributed state of arbitrary size.Overall, our evaluation shows that Rhino scales with state sizes of up to terabytes, reconfigures a running query 15 times faster than the state-of-the-art solutions, and reduces latency by three orders of magnitude upon a reconfiguration. In sum, the thesis lays the foundation for efficient and reliable stateful stream processing via a hardware-conscious system design that can be applied to existing and future SPEs. Through our novel system design, the software prototypes proposed in this work achieve superior performance compared to state-of-the-art SPEs on common stream processing workloads., In den letzten zwei Jahrzehnten wurden verteilte Datenflussverarbeitungssysteme zu einer wichtigen Komponente in dem Big-Data-Verwaltungs-Toolkit, um zustandsabhängige Echtzeit- Datenanalyseanwendungen für hochvolumige Datenströme mit hoher Geschwindigkeit in Cloud- Bereitstellungen zu unterstützen. Zu diesem Zweck führen aktuelle Datenflussverarbeitungssysteme kontinuierlich Map/Reduce-ähnliche Pipelines auf kontinuierlichen Daten aus und wenden datenzentrische Parallelität zur Skalierung auf einem Server-Cluster an. Aktuelle Datenflussverarbeitungssysteme setzen sogenannte Commodity-Hardware voraus, da sie Map/Reduceähnlichen Paradigmen folgen, die auf der Shared-Nothing-Architektur basieren. Darüber hinaus sind Datenflussverarbeitungssysteme unabhängig von der Hardwarekonfiguration, da sie sich auf verwaltete Laufzeiten, wie z. B. eine Java Virtual Machine, stützen. Moderne Hardware-Infrastrukturen haben sich jedoch in den letzten Jahren dramatisch verbessert. Daher ist die gängige Meinung, dass Cloud-Anbieter hauptsächlich Standard-Hardware anbieten, nicht mehr gültig. So bieten die Anbieter von Cloud-Plattformen leistungsstarke Rechen- und Netzwerkfunktionen, da sie Server mit High-End-CPUs mit vielen Kernen und großen Caches sowie Hochgeschwindigkeitsnetzwerke wie Infiniband mit RDMA-Unterstützung (Remote Direct Memory Access) anbieten. Darüber hinaus sind moderne verteilte Recheninfrastrukturen äußerst flexibel, da sie eine Ad-hoc-Bereitstellung von Ressourcen ermöglichen, die eine Skalierung der Rechen- und Speicherkapazitäten sowie die Behandlung von Ausfällen ermöglichen, während eine Anwendung ausgeführt wird. In dieser Arbeit zeigen wir, dass die aktuelle Generation von Datenflussverarbeitungssysteme hardware-agnostisch ist und die oben genannten technologischen Fortschritte nicht nutzen kann. Wir zeigen experimentell, dass diese ineffizient arbeiten, wenn sie auf einer Infrastruktur ausgeführt werden, die CPUs auf dem Leistungsniveau für HPC-Anwendungen, Hochgeschwindigkeitsnetzwerkkommunikation sowie eine flexible Ad-hoc-Ressourcenbereitstellung bietet. Zu diesem Zweck stellen wir Lösungen zur effizienten Ausführung von zustandsabhängigen Stream-Processing-Anwendungen auf einer modernen Recheninfrastrukturen vor. Zunächst konzentrieren wir uns auf die Skalierungsleistung aktueller Datenflussverarbeitungssysteme, um die Rechenkapazitäten der modernen Hardware zu nutzen. Unsere Analyse zeigt, dass Datenflussverarbeitungssysteme unter ineffizienten Speicherzugriffsmustern leiden, die zu einer suboptimalen Code- und Datenlokalität führen. Auf der Grundlage unserer Analyse schalgen wir Designänderungen, wie z. B. eine spezialisierte Codegenerierung, vor um die allgemeinen Architektur dahingehend zu ändern das ein SPE eine Skalierung auf moderner Hardware ermöglicht. Zweitens konzentrieren wir uns auf die Scale-out-Leistung der aktuellen Datenflussverarbeitungssysteme, um die Hochgeschwindigkeitsnetzwerke mit RDMA-Unterstützung zu nutzen. Insbesondere die RDMA-Hardware hat die gängige Annahme entkräftet, dass das Netzwerk in verteilten Datenverarbeitungssystemen oft ein Engpass ist. Hochgeschwindigkeitsnetze bieten jedoch keine Plug-and-PlayLeistung (z. B. bei der Verwendung von IP-over-InfiniBand) und erfordern eine sorgfältige gemeinsame Entwicklung von System- und Anwendungslogik. Insgesamt erreicht unsere Lösung eine Durchsatzverbesserung um bis zu zwei Größenordnungen gegenüber bestehenden Systemen, die in einem InfiniBand-Netzwerk eingesetzt werden, und sie ist bis zu einem Faktor von 22 schneller als eine selbst entwickelte Lösung, die auf RDMA-basierter Datenvorpartitionierung zur Skalierung der Abfrageverarbeitung beruht. Abschließend konzentrieren wir uns auf die Laufzeit-Rekonfiguration laufender Streaming-Anwendungen der aktuellen Generation von Datenstromverarbeitungssystemen, um die Adhoc- und flexiblen Bereitstellungsmöglichkeiten der modernen Cloud-Computing-Infrastruktur zu nutzen. Datenflussverarbeitungssysteme müssen zustandsbehaftete Abfragen während der Laufzeit rekonfigurieren, um sich von Ausfällen zu erholen, sich an schwankende Datenraten anzupassen und eine Verarbeitung mit geringer Latenz zu gewährleisten, was in industriellen Umgebungen erforderlich ist. Modernste Datenflussverarbeitungssysteme sind jedoch noch nicht in der Lage, Abfragen mit Terabytes an Zuständen während der Laufzeit zu rekonfigurieren, was auf drei Probleme zurückzuführen ist: Netzwerk-Overhead für Zustandsmigration, Konsistenz und Mehrkosten bei der Datenverarbeitung. Wir schlagen Rhino vor, ein System für die effiziente Rekonfiguration laufender Abfragen in Anwesenheit eines verteilten Zustands beliebiger Größe. Insgesamt zeigt unsere Untersuchung, dass Rhino mit Zustandsgrößen von bis zu mehreren Terabytes skaliert, eine laufende Abfrage 15-mal schneller rekonfiguriert als die modernsten Lösungen und die Latenz bei einer Rekonfiguration um drei Größenordnungen reduziert. Zusammenfassend lässt sich sagen, dass diese Arbeit die Grundlage für eine effiziente und zuverlässige zustandsbehaftete Stream-Verarbeitung durch ein hardwarebewusstes Systemdesign legt, das auf bestehende und zukünftige SPEs angewendet werden kann. Durch unser neuartiges Systemdesign erreichen unsere Software-Prototypen, die in dieser Arbeit vorgeschlagen wurden, eine überlegene Leistung im Vergleich zu modernen Datenstromverarbeitungssystemen bei gängigen Datenstromverarbeitungsaufgaben.

The interdisciplinary research project "Decoding Antisemitism" aims to investigate antisemitism on the internet. Since summer 2020, this three-year pilot project has been based at the Centre for Research on Antisemitism (ZfA) at TU Berlin and is being carried out in cooperation with HTW Berlin and King's College London (KCL) . The object of study is antisemitism in the comment sections of mainstream political media websites in Germany, France and the UK, as well as their social media profiles. Using a mixed methods approach, discursive trends in the three European countries and different verbal and visual forms of antisemitism are analysed qualitatively, quantitatively and with the help of AI. The interactive web presents itself as an object of study due to its central role in social discourse. By analysing the comments sections of media that belong to the politically moderate field, the research team is opening up a field that has received little attention so far - an urgent task, since the normalisation of derogatory and exclusionary rhetoric in such milieus poses an enormous danger. On the basis of extensive qualitative analyses, an overview of previously unknown manifestations and the actual extent of antisemitism in these European web communities will be gained. The results in turn offer the possibility of diverse counter-strategies., Das interdisziplinäre Foschungsprojekt „Decoding Antisemitism“ dient der Untersuchung von Antisemitismus im Internet. Seit Sommer 2020 ist dieses dreijährige Pilotprojekt am Zentrum für Antisemitismusforschung (ZfA) an der TU Berlin angesiedelt und wird in Zusammenarbeit mit der HTW Berlin und dem King’s College London (KCL) durchgeführt. Beim Untersuchungsgegenstand handelt es sich um Antisemitismus in den Kommentarbereichen von Medien-Webseiten des politischen Mainstream in Deutschland, Frankreich und Großbritannien sowie deren Social Media-Profile. Über einen Mixed Methods-Zugang werden diskursive Trends in den drei europäischen Ländern und unterschiedliche verbale und visuelle Ausformungen von Antisemitismus qualitativ, quantitativ sowie KI-gestützt analysiert. Das Interaktive Web bietet sich aufgrund seiner zentralen Rolle im gesellschaftlichen Diskurs als Untersuchungsgegenstand an. Mit der Analyse von Kommentarbereichen jener Medien, die dem politisch gemäßigten Feld zuzurechnen sind, erschließt das Forscher*innenteam ein bislang wenig beachtetes Feld – zudem eine drängende Aufgabe, da von der Normalisierung abwertender und ausgrenzender Rhetorik in ebensolchen Milieus eine enorme Gefahr ausgeht. Auf der Basis umfangreicher qualitativer Analysen wird ein Überblick über bisher unbekannte Erscheinungsformen und das tatsächliche Ausmaß von Antisemitismus in diesen europäischen Web-Communitys gewonnen. Die Ergebnisse bieten wiederum die Möglichkeit vielfältiger Gegenstrategien., «Decoding Antisemitism» est un projet de recherche interdisciplinaire hébergé par le Centre de Recherche sur l’Antisémitisme (ZfA) de TU Berlin, en collaboration avec HTW Berlin et le King’s College London (KCL). Depuis l’été 2020, et pour trois ans, ce projet pilote a pour objectif d’examiner la façon dont les contenus antisémites émergent et circulent dans les sections commentaires des médias mainstream en Allemagne, au Royaume-Uni et en France. S’inscrivant au croisement des Sciences du Langage et de l’Intelligence Artificielle, le projet étudie, d’un point de vue aussi bien qualitatif et quantitatif, les différentes formes verbales et visuelles de l’antisémitisme en ligne. Jouant un rôle central dans le discours social, le web interactif constitue l’objet d’étude de ce projet. Plus particulièrement, l’analyse de l’antisémitisme dans les sections commentaires des médias mainstream permet d’examiner un terrain jusqu’ici peu exploré - une tâche urgente, car la normalisation de la rhétorique dérogatoire et d'exclusion dans ces milieux représente un énorme danger. Sur la base d'analyses qualitatives, une vue d'ensemble des manifestations jusqu'à maintenant inconnues et de l'étendue réelle de l'antisémitisme dans ces communautés web européennes sera acquise. Les résultats offrent à leur tour la possibilité de développer diverses contre-stratégies.

Machine learning (ML) has become an essential tool for solving problems that have traditionally been challenging for computers, for example in the fields of natural language processing, computer vision, and recommender systems. For large ML tasks, distributed training has become a necessity for keeping up with increasing dataset sizes and model complexity. A key challenge in distributed training is to synchronize model parameters among cluster nodes and to do so efficiently. Parameter servers (PSs) facilitate the implementation of distributed training by providing cluster-wide read and write access to the parameters, and transparently handling partitioning and synchronization in the background (either among the cluster nodes directly or via physically separate server nodes). In this thesis, we study the efficiency of PSs for ML tasks with sparse parameter access, i.e., tasks in which each update step reads and writes only a small (or tiny) part of the model. In a first step, we find that existing PSs are inefficient for such tasks: in our experiments, distributed implementations were slower than efficient single node implementations due to communication overhead. This inefficiency dramatically limits the utility of PSs and distributed training in general. With such inefficiency, distributed training in practice will be used only when it is indispensable, e.g., for very large models. And when distributed training is indeed employed, its inefficiency squanders hardware and energy resources. Starting from this observation, we investigate whether and how PS efficiency can be improved. The main idea of this thesis is to increase efficiency by making the PS adapt to the underlying ML task. We first present and evaluate a series of potential performance improvements in this direction, each making the PS more adaptive. In particular, we explore (i) to dynamically adapt the allocation of model parameters, i.e., to relocate parameters among nodes during training, according to where they are accessed, (ii) to adapt the management technique of the PS to the access patterns of individual parameters, i.e., to employ a suitable management technique for each parameter, and (iii) to adapt to the type of a parameter access, by supporting sampling (i.e., randomized) access directly. We find empirically that each of these aspects can improve PS efficiency. However, each aspect also makes the PS more complex to use, because the application (i.e., the component that interacts with the PS) needs to control adaptivity manually. To reduce complexity, we develop a mechanism that enables automatic adaptivity, i.e., adaptivity without requiring the application's manual control. With this mechanism, the application merely provides information about parameter accesses, in a way that naturally integrates into common ML systems. We describe a novel PS system—called AdaPS—that adapts to ML tasks automatically based on the information provided by this mechanism. AdaPS incorporates all adaptivity aspects presented in this thesis. It decides what to do (i.e., which management technique to use for a specific parameter and where to allocate each parameter) and when to do so. It does so automatically, i.e., without further user input, and dynamically, i.e., based on the current situation. In our experiments, AdaPS enabled efficient distributed ML training for multiple ML tasks: in contrast to previous PSs, it provided near-linear speed-ups over efficient single node implementations. With these results, we argue that PSs can be efficient for sparse ML tasks, and that this efficiency can be reached with limited additional effort from application developers. Efficient and easy-to-use PSs make distributed training (i) attractive for a wide range of use cases—thus enabling solutions to challenging problems—and (ii) squander fewer of our planet's resources., Maschinelles Lernen (ML) ist inzwischen ein essentielles Werkzeug, um Probleme zu lösen, die für Computer traditionell herausfordernd waren, zum Beispiel zur Verarbeitung natürlicher Sprache, für Bilderkennung und zum Generieren von Empfehlungen. Um mit steigenden Datenmengen und Modellkomplexitäten Schritt zu halten, ist für komplizierte ML-Aufgaben verteiltes Training notwendig, das heißt, paralleles Training auf mehreren Computern eines Clusters. Eine zentrale Herausforderung in verteiltem Training ist die effiziente Synchronisierung der Modellparameter zwischen den Computern des Clusters. Parameter Server erleichtern die Implementierung von verteiltem Training, indem sie clusterweiten Lese- und Schreibzugriff auf die Modellparameter ermöglichen, und im Hintergrund transparent Partitionierung und Synchronisation handhaben (entweder direkt zwischen den Computern des Clusters oder via physisch separate Computer). In dieser Arbeit untersuche ich die Effizienz von Parameter Servern für ML-Aufgaben mit dünnbesetztem (engl. "sparse") Parameterzugriff, also Aufgaben, bei denen jeder Modell-Update-Schritt nur einen kleinen (oder winzigen) Teil des Modells liest und schreibt. In einem ersten Schritt stelle ich fest, dass bestehende Parameter Server für solche Aufgaben ineffizient sind: In meinen Experimenten waren verteilte Implementierungen (mit 8 Computern) langsamer als effiziente Implementierungen auf einem einzelnen Computer. Diese Ineffizienz limitiert den Nutzwert von Parameter Servern und verteiltem Training drastisch. Mit solch hoher Ineffizienz wird verteiltes Lernen in der Praxis nur eingesetzt wenn es unvermeidbar ist, zum Beispiel für sehr große Modelle. Und immer wenn verteiltes Training eingesetzt wird, vergeudet es Hardware- und Energieressourcen. Auf der Grundlage dieser Beobachtung untersuche ich, ob und wie die Effizienz von Parameter Servern verbessert werden kann. Die zentrale Idee dieser Arbeit ist, die Effizienz zu verbessern indem der Parameter Server sich an die zugrunde liegende ML-Aufgabe anpasst. Ich präsentiere und evaluiere zunächst eine Reihe von potenziellen Verbesserungen in dieser Richtung, die den Parameter Server jeweils adaptiver machen. Insbesondere versuche ich, (i) die Allokation der Modellparameter dynamisch anzupassen, das heißt, die Parameter während des Trainings zwischen den Knoten zu verschieben, je nachdem, wo auf sie zugegriffen wird, (ii) die Parameter-Management-Techniken des Parameter Servers an die Zugriffsmuster der einzelnen Parameter anzupassen, also für jeden Parameter eine für den Parameter geeignete Technik einzusetzen, und (iii) den Parameter Server an die Art des Parameterzugriffs anzupassen, indem er stichprobenartige (randomisierte) Zugriffe direkt unterstützt. In einer Reihe von Experimenten stelle ich fest, dass jeder dieser Aspekte die Effizienz von Parameter Servern verbessern kann. Allerdings verkompliziert jeder Aspekt auch die Nutzung des Parameter Servers, weil die Anwendung (die Komponente, die mit dem Parameter Server interagiert) die Anpassungen manuell steuern muss. Aus diesem Grund entwickle ich einen Mechanismus, der automatische Anpassung ermöglicht. Die Anwendung stellt über diesen Mechanismus Informationen über die Parameterzugriffe bereit, und zwar auf eine Art, die sich nahtlos in gängige ML-Systeme integriert. Darüber hinaus präsentiere ich einen neuartigen Parameter Server (AdaPS), der sich basierend auf den von diesem Mechanismus bereitgestellten Informationen automatisch an ML-Aufgaben anpasst. AdaPS vereint alle in dieser Arbeit vorgestellten Aspekte der Adaptivität. Der Parameter Server entscheidet, was zu tun ist (das heißt, welche Technik für einen bestimmten Parameter zu verwenden ist und wo jeder Parameter alloziert werden soll) und wann dies zu tun ist. Dies geschieht automatisch, also ohne zusätzliche Informationen, und dynamisch, also basierend auf der aktuellen Situation. In Experimenten ermöglicht AdaPS effizientes verteiltes ML-Training: Im Gegensatz zu früheren Parameter Servern liefert AdaPS nahezu lineare Geschwindigkeitssteigerungen gegenüber Implementierungen für einzelne Computer. Aufgrund dieser Ergebnisse argumentiere ich, dass Parameter Server für dünnbesetzte ML-Aufgaben effizient sein können, und dass diese Effizienz mit begrenztem zusätzlichem Aufwand für Anwendungsentwickler:innen erreicht werden kann. Effiziente und einfach zu verwendende Parameter Server sorgen dafür, dass verteiltes Training (i) für ein breites Spektrum von Anwendungsfällen attraktiv wird (und so Lösungen für anspruchsvolle Probleme ermöglicht) und (ii) weniger der Ressourcen unseres Planeten verschwendet.

This thesis studies selected structural and algorithmic aspects of temporal graphs, which are graphs whose edges are present only at specific points in time. Temporal graphs are well suited to model a range of real-world networks whose connections frequently vary over time, such as public transport, physical proximity, or communication networks. We are particularly interested in structures related to reachability between vertices. In temporal graphs, this is a more complex concept than in static graphs, because reaching some vertex b from another vertex a requires not only a sequence of edges that forms a path from a to b, but additionally the times at which these edges are present must be in monotonically increasing order. Specifically, we investigate the following four individual aspects of temporal graphs. Temporal Voronoi games: Voronoi games, which have in the past been studied on static graphs and in Euclidean space, model a scenario in which two actors compete to reach as many vertices as possible before the other. We now define and study Voronoi games on temporal graphs. By analyzing the structure induced by these games, we discover sufficient conditions for the existence (and efficient construction) of Nash equilibria, that is, stable situations in which neither player wishes to change their current position. Connectivity in random temporal graphs: We study reachability in a simple model of random temporal graphs, which is inspired by Erdős-Rényi graphs. In this model, we find that various fine-grained degrees of temporal reachability are attained at distinct sharp density thresholds, i.e., a large random temporal graph possesses a certain reachability property (with high probability) if and only if its density is above a property-specific threshold. We further obtain thresholds for the existence of certain types of temporal spanners, i.e., subgraphs providing pairwise temporal reachability between all vertices. Temporal feedback edge sets: We consider the computational problem of removing a minimum number of connections in order to break all temporal cycles, that is, vertices reaching themselves through a circular path. On the one hand, we prove that this problem is NP-hard, even in some very restricted settings. On the other hand, we find that it becomes fixed-parameter tractable when parameterized by certain parameter combinations. Isolated cliques: We study the algorithmic complexity of finding temporal cliques, that is, sets of vertices and time intervals such that these vertices are pairwise directly connected during said time interval. Here, we focus on isolated temporal cliques, that is, temporal cliques which are only sparsely connected to the remainder of the graph. We find that for five out of six possible notions of isolation, the enumeration of these cliques is fixed-parameter tractable when parameterized by the degree of isolation., Diese Arbeit beschäftigt sich mit ausgewählten strukturellen und algorithmischen Aspekten von temporalen Graphen, d.h. Graphen deren Kanten nur zu gewissen Zeitpunkten vorhanden sind. Temporale Graphen eignen sich zur Modellierung zahlreicher Netzwerke, deren Verbindungen stark zeitabhängig sind, wie dies z.B. im öffentlichen Personenverkehr, bei Kontaktgraphen oder Kommunikationsnetzen oft der Fall ist. Unsere Interesse gilt insbesondere der Erreichbarkeit zwischen Knoten. Dieses Konzept ist in temporalen Graphen komplexerer Natur als in statischen Graphen, denn einen Knoten b von einem anderen Knoten a aus zu erreichen, erfordert nicht nur eine Folge von Kanten, die einen Pfad von a nach b bilden, sondern zusätzlich dass die Verfügbarkeitszeiten dieser Kanten entlang des Pfades monoton steigen. Im Einzelnen werden hier die folgenden vier Aspekte temporaler Graphen näher untersucht. Temporale Voronoi-Spiele: Voronoi-Spiele wurden in der Vergangenheit auf statischen Graphen und im Euklidischen Raum analysiert. Sie modellieren ein Szenario, in dem zwei konkurrierende Akteure versuchen, möglichst viele Knoten jeweils zuerst zu erreichen. In dieser Arbeit werden Voronoi-Spiele auf temporalen Graphen eingeführt und untersucht. Eine genaue Analyse der diesen Spielen innewohnenden Struktur erlaubt es uns, hinreichende Bedingungen für die Existenz von Nash-Gleichgewichten (d.h. stabilen Situationen von denen keiner der Spieler abweichen möchte) zu finden (und diese effizient zu bestimmen). Erreichbarkeit in zufälligen temporalen Graphen: Wir untersuchen die Erreichbarkeit in einem einfachen Modell von zufälligen temporalen Graphen, das an Erdős-Rényi-Graphen angelehnt ist. Es stellt sich heraus, dass in diesem Modell verschiedene Abstufungen von temporaler Erreichbarkeit an spezifischen scharfen Dichte-Schwellwerten erreicht werden. Das bedeutet, dass ein großer zufälliger temporaler Graph gewisse Erreichbarkeitseigenschaften (mit hoher Wahrscheinlichkeit) genau dann besitzt, wenn seine Dichte den jeweiligen Schwellwert überschreitet. Ferner ermitteln wir solche Dichte-Schwellwerte auch für die Existenz verschiedener Arten von Subgraphen, die temporale Erreichbarkeit zwischen allen Knoten herstellen. Temporale Feedback-Kanten-Mengen: Es geht hier um das (algorithmische) Problem, eine kleinstmögliche Anzahl an Verbindungen aus einem gegebenen temporalen Graphen zu entfernen um damit alle temporalen Kreise zu unterbrechen, d.h. sodass anschließend kein Knoten mehr sich selbst über einen Rundweg erreichen kann. Zum einen stellen wir fest, dass dieses Problem selbst in einigen sehr eingeschränkten Szenarien NP-schwer ist, zum anderen zeigen wir aber auch fixed-parameter tractability für gewisse Parameterkombinationen. Isolierte Cliquen: Eine temporale Clique besteht aus einer Knotenmenge und einem Zeitintervall mit der Eigenschaft, dass ebendiese Knoten während des besagten Zeitintervalls paarweise durch Kanten verbunden sind. Wir betrachten insbesondere isolierte temporale Cliquen, d.h. temporale Cliquen, die nur schwach mit dem restlichen Graphen verbunden sind. Wir zeigen für fünf der sechs möglichen Isolationsbegriffe, dass eine Auflistung isolierter temporaler Cliquen fixed-parameter tractable bzgl. des Parameters Isolationsgrad ist.

The development of highly automated driving requires dynamic approaches that anticipate the cognitive state of the driver. In this paper, a cognitive model is developed that simulates a spectrum of cognitive processing and the development of situation awareness and attention guidance in different takeover situations. In order to adapt cognitive assistance systems according to individuals in different situations, it is necessary to understand and simulate dynamic processes that are performed during a takeover. To validly represent cognitive processing in a dynamic environment, the model covers different strategies of cognitive and visual processes during the takeover. To simulate the visual processing in detail, a new module for the visual attention within different traffic environments is used. The model starts with a non-driving-related task, attends the takeover request, makes an action decision and executes the corresponding action. It is evaluated against empirical data in six different driving scenarios, including three maneuvers. The interaction with different dynamic traffic scenarios that vary in their complexity is additionally represented within the model. Predictions show variances in reaction times. Furthermore, a spectrum of driving behavior in certain situations is represented and how situation awareness is gained during the takeover process. Based on such a cognitive model, an automated system could classify the driver’s takeover readiness, derive the expected takeover quality and adapt the cognitive assistance for takeovers accordingly to increase safety.

In this paper, we propose to leverage the Bayesian uncertainty information encoded in parameter distributions to inform the learning procedure for Bayesian models. We derive a first principle stochastic differential equation for the training dynamics of the mean and uncertainty parameter in the variational distributions. On the basis of the derived Bayesian stochastic differential equation, we apply the methodology of stochastic optimal control on the variational parameters to obtain individually controlled learning rates. We show that the resulting optimizer, StochControlSGD, is significantly more robust to large learning rates and can adaptively and individually control the learning rates of the variational parameters. The evolution of the control suggests separate and distinct dynamical behaviours in the training regimes for the mean and uncertainty parameters in Bayesian neural networks.

We apply the framework of nonlinear optimal control to a biophysically realistic neural mass model, which consists of two mutually coupled populations of deterministic excitatory and inhibitory neurons. External control signals are realized by time-dependent inputs to both populations. Optimality is defined by two alternative cost functions that trade the deviation of the controlled variable from its target value against the “strength” of the control, which is quantified by the integrated 1- and 2-norms of the control signal. We focus on a bistable region in state space where one low- (“down state”) and one high-activity (“up state”) stable fixed points coexist. With methods of nonlinear optimal control, we search for the most cost-efficient control function to switch between both activity states. For a broad range of parameters, we find that cost-efficient control strategies consist of a pulse of finite duration to push the state variables only minimally into the basin of attraction of the target state. This strategy only breaks down once we impose time constraints that force the system to switch on a time scale comparable to the duration of the control pulse. Penalizing control strength via the integrated 1-norm (2-norm) yields control inputs targeting one or both populations. However, whether control inputs to the excitatory or the inhibitory population dominate, depends on the location in state space relative to the bifurcation lines. Our study highlights the applicability of nonlinear optimal control to understand neuronal processing under constraints better.

We present an eye typing interface with one-point calibration, which is a two-stage design. The characters are clustered in groups of four characters. Users select a cluster by gazing at it in the first stage and then select the desired character by following its movement in the second stage. A user study was conducted to explore the impact of auditory and visual feedback on typing performance and user experience of this novel interface. Results show that participants can quickly learn how to use the system, and an average typing speed of 4.7 WPM can be reached without lengthy training. The subjective data of participants revealed that users preferred visual feedback over auditory feedback while using the interface. The user study indicates that this eye typing interface can be used for walk-up-and-use interactions, as it is easily understood and robust to eye-tracking inaccuracies. Potential areas of application, as well as possibilities for further improvements, are discussed.

Sustainability in tourism is a topic of global relevance, finding multiple mentions in the United Nations Sustainable Development Goals. The complex task of balancing tourism’s economic, environmental, and social effects requires detailed and up-to-date data. This paper investigates whether online platform data can be employed as an alternative data source in sustainable tourism statistics. Using a web-scraped dataset from a large online tourism platform, a sustainability label for accommodations can be predicted reasonably well with machine learning techniques. The algorithmic prediction of accommodations’ sustainability using online data can provide a cost-effective and accurate measure that allows to track developments of tourism sustainability across the globe with high spatial and temporal granularity.

Physical Unclonable Functions (PUFs) have been proposed as a way to identify and authenticate electronic devices. Recently, several ideas have been presented that aim to achieve the same for quantum devices. Some of these constructions apply single-qubit gates in order to provide a secure fingerprint of the quantum device. In this work, we formalize the class of Classical Readout Quantum PUFs (CR-QPUFs) using the statistical query (SQ) model and explicitly show insufficient security for CR-QPUFs based on single qubit rotation gates, when the adversary has SQ access to the CR-QPUF. We demonstrate how a malicious party can learn the CR-QPUF characteristics and forge the signature of a quantum device through a modelling attack using a simple regression of low-degree polynomials. The proposed modelling attack was successfully implemented in a real-world scenario on real IBM Q quantum machines. We thoroughly discuss the prospects and problems of CR-QPUFs where quantum device imperfections are used as a secure fingerprint., Comment: 12 pages, 9 figures

Many organizations leverage Distributed Stream processing systems (DPSs) to get insights from the data generated by different users/devices, e.g., the Internet of Things (IoT) devices or user clicks on a website, on geographically distributed datacenters. The worker nodes in such environments are connected through Wide Area Network (WAN) links with various delays and bandwidth. Therefore, minimizing the execution latency of a task on the worker nodes while using the links with enough bandwidth and lower cost to steer the traffic of the applications is a challenging task. In this paper, we formulate the worker node placement for a geo-distributed DSPs network as a multi-criteria decision-making problem. Then, we propose an additive weighting-based approach to solve it. The users can prioritize the worker node placement according to the network-relevant parameters. We also propose a framework that can be integrated with the current DPSs to execute the tasks. We test our placement approach on three widely used stream processing systems, i.e., Apache Spark, Apache Storm, and Apache Flink, on three custom graphs adopted from the real cloud providers. We run the streaming query of the Yahoo! streaming benchmark on these three DPSs. The experimental results show that our approach improves the performance of Spark up to 2.2x-7.2x, Storm up to 1.2x-3.4x, and Flink up to 1.4x-3.3x compared with other placement approaches, which makes our framework useful for use in practical environments.

Window aggregations and windowed joins are central operators of modern real-time analytic workloads and significantly impact the performance of stream processing systems.This paper gives an overview of state-of-the-art research in this area conducted by the Berlin Institute for the Foundations of Learning and Data (BIFOLD) and the Technische Universität Berlin. To this end, we present different algorithms for efficiently processing windowed operators and discuss techniques for distributed stream processing. Recently, several approaches have leveraged modern hardware for windowed stream processing, which we will also include in this overview. Additionally, we describe the integration of windowed operators into various stream processing systems and diverse applications that use specialized window operations.

Sleep manifests itself by the spontaneous emergence of characteristic oscillatory rhythms, which often time-lock and are implicated in memory formation. Here, we analyze a neural mass model of the thalamocortical loop in which the cortical node can generate slow oscillations (approximately 1 Hz) while its thalamic component can generate fast sleep spindles of σ-band activity (12–15 Hz). We study the dynamics for different coupling strengths between the thalamic and cortical nodes, for different conductance values of the thalamic node's potassium leak and hyperpolarization-activated cation-nonselective currents, and for different parameter regimes of the cortical node. The latter are listed as follows: (1) a low activity (DOWN) state with noise-induced, transient excursions into a high activity (UP) state, (2) an adaptation induced slow oscillation limit cycle with alternating UP and DOWN states, and (3) a high activity (UP) state with noise-induced, transient excursions into the low activity (DOWN) state. During UP states, thalamic spindling is abolished or reduced. During DOWN states, the thalamic node generates sleep spindles, which in turn can cause DOWN to UP transitions in the cortical node. Consequently, this leads to spindle-induced UP state transitions in parameter regime (1), thalamic spindles induced in some but not all DOWN states in regime (2), and thalamic spindles following UP to DOWN transitions in regime (3). The spindle-induced σ-band activity in the cortical node, however, is typically the strongest during the UP state, which follows a DOWN state “window of opportunity” for spindling. When the cortical node is parametrized in regime (3), the model well explains the interactions between slow oscillations and sleep spindles observed experimentally during Non-Rapid Eye Movement sleep. The model is computationally efficient and can be integrated into large-scale modeling frameworks to study spatial aspects like sleep wave propagation.

Eine zentrale Herausforderung der digitalen Transformation ist es, diese in Einklang mit gesellschaftlichen Normen und Werten zu bringen. Verschiedene Ansätze, dies zu erreichen, wurden in den vergangenen Jahren entwickelt und erprobt. In der Entwicklung von informationstechnischen Systemen wird beispielsweise das technische Design im Einklang mit ethischen Werten und Prinzipien (ethics by design) zunehmend als wichtiger Baustein diskutiert. Value Sensitive Design (VSD) ist ein Ansatz, um ethische Werte in einer systematischen Weise während eines Entwicklungsprozesses zu berücksichtigen. Der Begriff „digitale Transformation“ umfasst aber mehr als die Entwicklung von informationstechnischen Systemen. Er beschreibt den Einsatz von Informationstechnik als einen Prozess, durch den ein Mehrwert für ein Unternehmen oder für die Gesellschaft erzielt wird. Vier Dimensionen, die es bei einer digitalen Transformation zu beachten gilt, sind Informationstechnik, Organisation, Wertschöpfung und Compliance. Dieser Artikel stellt die Hypothese auf, dass VSD geeignet ist, nicht nur Entwicklungsprojekte, sondern auch die digitale Transformation in einem Unternehmen zu gestalten. Hierzu müssen allerdings Orientierungshilfen wie beispielsweise Methodensammlungen, die AnwenderInnen in der einschlägigen Literatur zur Verfügung gestellt werden, erweitert werden. Dieser Artikel diskutiert, wie und mithilfe der Integration welcher Methoden, die einzelnen Dimensionen in VSD berücksichtigt werden können. Der Artikel leistet hierdurch einen doppelten Beitrag. Einerseits zeigt er auf konzeptueller Ebene auf, wie VSD für die Gestaltung einer digitalen Transformation genutzt werden kann. Andererseits erläutert er, wie die Integration von Methoden der Wirtschaftsinformatik den Einsatz von VSD unterstützen kann., A central challenge of digital transformations is to align them with social norms and values. Various approaches to achieving this have been developed and put to the test in recent years. In the developmet of informations systems, ethics by design is increasingly being discussed as an essential building block. Value Sensitive Design (VSD) is an approach to consider ethical values systematically in such development processes. However, the term “digital transformation” encompasses more than the development of information systems. It describes the use of information systems as a process through which added value is achieved for an enterprise or society. This article hypothesizes that VSD is suitable for shaping not only the development of information systems but also digital transformations. However, to do this, guidance such as method collections provided by the pertinent literature on VSD needs to be extended. This article discusses how and with the help of the integration of which methods this can be achieved. The contribution of the article is twofold. On the one hand, it outlines how VSD can be used to shape digital transformations. On the other hand, it explains how the integration of business informatics methods can support the use of VSD.

Due to the rapid change of population structure, leading to lower birth rates and quick aging rates, the demand for blood supply is increasing significantly. In most countries, blood quality and origin are managed by blood management information systems, such as national authorities. Nevertheless, the traditional system has limitations in this field, such as a lack of detailed blood information, making it challenging to manage blood quality, supply, and demand. Hence, to solve these issues, this paper proposes a blockchain-based system called BloodChain, an improved system to support blood information management, providing more detailed information about blood, such as blood consumption and disposal. BloodChain exploits private blockchain techniques with a limited number of relatively fast and reliable participants, making them suitable for B2B (Business to Business) transactions. In this paper, we also develop a proposed system based on the architecture of Hyperledger Fabric. The evaluation of BloodChain is performed in several scenarios to prove our proposed model’s effectiveness.

In this work, we propose a novel denoising technique, the icosahedral mesh denoising network (IMD-Net) for closed genus-0 meshes. IMD-Net is a deep neural network that produces a denoised mesh in a single end-to-end pass, preserving and emphasizing natural object features in the process. A preprocessing step, exploiting the homeomorphism between genus-0 mesh and sphere, remeshes an irregular mesh using the regular mesh structure of a frequency subdivided icosahedron. Enabled by gauge equivariant convolutional layers arranged in a residual U-net, IMD-Net denoises the remeshing invariant to global mesh transformations as well as local feature constellations and orientations, doing so with a computational complexity of traditional conv2D kernel. The network is equipped with carefully crafted loss function that leverages differences between positional, normal and curvature fields of target and noisy mesh in a numerically stable fashion. In a first, two large shape datasets commonly used in related fields, ABC and ShapeNetCore , are introduced to evaluate mesh denoising. IMD-Net’s competitiveness with existing state-of-the-art techniques is established using both metric evaluations and visual inspection of denoised models. Our code is publicly available at https://github.com/jjabo/IMD-Net.

In platooning multiple vehicles are organized in convoys driving autonomously with a minimized safety gap. In order to support the global deployment of platooning, an integrated multi-brand approach is required. The European HORIZON 2020 project ENSEMBLE tries to address this issue by unifying and standardizing platooning within Europe. To this end, ENSEMBLE published a new communication protocol and within proposed a concrete implementation of communication for truck platooning in Europe. We conduct an extensive simulation study of the proposed communication protocol, showing that the protocol, even with packet loss, works reliable in all tested scenarios and guarantees a certain level of road safety. Considering the protocol performance from the application layer perspective, we evaluate how effective the protocol fulfills the requirements of the controller. By doing that, we additionally provide a key performance indicator to measure how well the protocol ensures constant information flow. That can be used to determine whether a different controller would be reliable with the proposed communication protocol., Beim Platooning werden mehrere Fahrzeuge in Konvois organisiert, die autonom und mit möglichst geringem Sicherheitsabstand fahren. Um den globalen Einsatz von Platooning zu unterstützen, ist ein integrierter Mehrmarkenansatz erforderlich. Das europäische HORIZON 2020 Projekt ENSEMBLE versucht, dieses Problem durch Vereinheitlichung und Standardisierung von Platooning in Europa zu lösen. Zu die- sem Zweck hat ENSEMBLE ein neues Kommunikationsprotokoll veröffentlicht und eine konkrete Implementierung der Kommunikation für LKW-Platooning in Europa vorgeschlagen. Wir führen eine umfassende Simulationsstudie des vorgeschlagenen Kommunikationsprotokolls durch, die zeigt, dass das Protokoll selbst bei Nachrich- tenverlusten in allen getesteten Szenarien zuverlässig funktioniert und ein gewisses Maß an Verkehrssicherheit gewährleistet. Wir betrachten die Leistung des Protokolls aus der Perspektive der Anwendungsschicht und bewerten, wie effektiv das Protokoll die Anforderungen des Controllers erfüllt. Auf diese Weise stellen wir zusätzlich einen Leistungsindikator bereit, um zu messen, wie gut das Protokoll einen kon- stanten Informationsfluss gewährleistet. Damit lässt sich feststellen, ob eine andere Steuerung mit dem vorgeschlagenen Kommunikationsprotokoll zuverlässig wäre.

Modern database management systems (DBMSs) are tasked with analyzing terabytes of data, employing a rich set of relational and machine learning operators. To process data at large scales, research efforts have strived to leverage the high computational throughput and memory bandwidth of specialized co-processors such as graphics processing units (GPUs). However, scaling data management on GPUs is challenging because (1) the on-board memory of GPUs has too little capacity for storing large data volumes, while (2) the interconnect bandwidth is not sufficient for ad hoc transfers from main memory. Thus, data management on GPUs is limited by a data transfer bottleneck. In practice, CPUs process large-scale data faster than GPUs, reducing the utility of GPUs for DBMSs. In this thesis, we investigate how a new class of fast interconnects can address the data transfer bottleneck and scale GPU-enabled data management. Fast interconnects link GPU co-processors to a CPU with high bandwidth and cache-coherence. We apply our insights to process stateful and iterative algorithms out-of-core by the examples of a hash join and k-means clustering. We first analyze the hardware properties. Our experiments show that the high interconnect bandwidth enables the GPU to efficiently process large data sets stored in main memory. Furthermore, cache-coherence facilitates new DBMS designs that tightly integrate CPU and GPU via shared data structures and pageable memory allocations. However, irregular accesses from the GPU to main memory are not efficient. Thus, the operator state of, e.g., joins does not scale beyond the GPU memory capacity. We scale joins to a large state by contributing our new Triton join algorithm. Our main insight is that fast interconnects enable GPUs to efficiently spill the join state by partitioning data out-of-core. Thus, our Triton join breaks through the GPU memory capacity limit and increases throughput by up to 2.5× compared to a radix-partitioned join on the CPU. We scale k-means to large data sets by eliminating two key sources of overhead. In existing strategies, execution crosses from the GPU to the CPU on each iteration, which results in the cross-processing and multi-pass problems. In contrast, our solution requires only a single data pass per iteration and speeds-up throughput by up to 20×. Overall, GPU-enabled DBMSs are able to overcome the data transfer bottleneck by employing new out-of-core algorithms that take advantage of fast interconnects., Moderne Datenbankverwaltungssysteme (DBMS) werden verwendet um Terabytes von Daten zu analysieren, wobei eine Vielzahl von relationalen und maschinell lernenden Operatoren eingesetzt werden. Um Daten in großen Massen zu verarbeiten, strebten Forschungsversuche an, den hohen Rechendurchsatz und Speicherbandbreite von spezialisierten Coprozessoren wie beispielsweise Grafikprozessoren (GPUs) zu nutzen. Jedoch stellt die Skalierung der Datenverwaltung auf GPUs eine Herausforderung dar, weil (1) der integrierte Speicher von GPUs zu wenig Kapazität für die Speicherung großer Datenmengen hat, wohingegen (2) die Bandbreite des Interconnects nicht für eine Ad-hoc-Übertragung aus dem Hauptspeicher ausreicht. Somit ist die Datenverwaltung auf GPUs durch einen Datentransfer-Engpass begrenzt. In der Praxis verarbeiten daher Hauptprozessoren (CPUs) große Datenmengen schneller als GPUs, was die Nützlichkeit von GPUs für DBMSs verringert. In dieser Dissertation untersuchen wir, wie eine neue Klasse von schnellen Interconnects den Datentransfer-Engpass beheben und die GPU-gestützte Datenverwaltung skalieren kann. Schnelle Interconnects verbinden GPU-Coprozessoren zu einer CPU mit hoher Bandbreite und Cache-Kohärenz. Wir wenden unsere Erkenntnisse an, um zustandsbehaftete und iterative Algorithmen aus dem Coprozessor ausgelagert zu verarbeiten, beispielshalber an einem Hash Join und an dem k-Means Clustering-Verfahren. Wir analysieren zunächst die Hardware-Eigenschaften. Unsere Experimente zeigen, dass die hohe Transferbandbreite der GPU ermöglicht, große, im Hauptspeicher gespeicherte Datensätze effizient zu verarbeiten. Zudem fördert die Cache-Kohärenz neue DBMS-Designs, welche die CPU und die GPU über gemeinsam genutzte Datenstrukturen und auslagerbare Speicherallokationen eng integrieren. Allerdings sind ungleich verteilte Zugriffe von der GPU aus auf den Hauptspeicher nicht effizient. Deshalb lässt sich der Operator-Zustand von z.B. Joins nicht über die Speicherkapazität der GPU hinaus skalieren. Wir skalieren Joins auf einen großen Zustand, indem wir unseren neuen Triton Join-Algorithmus einführen. Unsere wichtigste Erkenntnis ist, dass schnelle Interconnects GPUs befähigen, den Join-Zustand durch ein externes Datenpartitionierungverfahren effizient auszulagern. Somit durchbricht unser Triton Join die durch die GPU-Speicherkapazität gegebene Begrenzung und steigert den Durchsatz um bis zu dem 2,5-fachen im Vergleich zu einem Radix-partitionierten Join auf der CPU. Wir skalieren k-Means auf große Datensätze, indem wir zwei Hauptlimitationen beseitigen. Bei bestehenden Strategien wechselt die Ausführung bei jeder Iteration zwischen der GPU und der CPU hin und her, was zu den Cross-Processing- und Multi-Pass-Problemen führt. Im Gegensatz dazu erfordert unsere Lösung nur einen einzigen Datendurchlauf pro Iteration und beschleunigt den Durchsatz um bis zu 20 Mal. Insgesamt sind GPU-gestützte DBMSs in der Lage, den Datentransfer-Engpass zu überwinden, indem sie neue, Zustands-auslagerbare Algorithmen einsetzen, die die Vorteile schneller Interconnects ausnutzen.

Microservices have emerged as a popular pattern for developing large-scale applications in cloud environments for its benefits of flexibility, scalability, and agility. A microservices-based cloud system (named as \emph{cloud microservices}) comprises hundreds or thousands of disparate services that communicate via lightweight messaging protocols, share a finite set of hardware and software resources, and are frequently updated to meet customer requirements. In such a complex and dynamic environment, the occurrence of performance problems (e.g., slow application responses) has become the norm rather than the exception, resulting in decreased revenue, damaged reputation, and significant human effort spent on performance diagnosis and recovery. Moreover, manual operation and maintenance of cloud microservices tend to be error-prone or even impracticable. Therefore, there is an urgent need for an automatic performance problem management system that can not only detect anomalous behaviors (performance anomalies) but also uncover the root causes and recommend recovery actions. In this thesis, we investigate methods for automatic performance diagnosis and recovery in cloud microservices. The core objectives of this thesis are to identify \emph{where} and \emph{why} a performance anomaly occurs, and further to decide \emph{how} to mitigate it. To this end, this thesis contributes: (1) a method for locating the faulty service from which a performance anomaly originates, including a graphical model for capturing the propagation of the anomaly in the system; (2) two methods for identifying the anomalous metrics that cause a performance anomaly, using deep learning and Spatio-temporal causal inference (CI). In addition, we evaluate the performance of CI techniques on performance diagnosis in cloud microservices through extensive experiments; (3) a method for selecting the most appropriate recovery action to mitigate an identified performance anomaly. Overall, the methods presented in this thesis diagnose root causes and recommend remedies in real-time without requiring any application instrumentation and historical failure instances. Our methods were implemented in prototypes and experimentally evaluated on representative microservices benchmarks. The evaluations show that they can support automatic performance diagnosis and recovery in cloud microservices and improve service reliability and end-user experience. The results have been peer-reviewed and published at renowned international conferences., Microservices haben sich aufgrund ihrer Flexibilität, Skalierbarkeit und Agilität zu einem beliebten muster für die Entwicklung umfangreicher Anwendungen in Cloud-Umgebungen entwickelt. Ein auf Microservices basierendes Cloud-System (auch als \emph{Cloud-Microservices bezeichnet}) besteht aus Hunderten oder Tausenden von unterschiedlichen Diensten, die über leichtgewichtige Nachrichtenprotokolle miteinander kommunizieren, häufig aktualisiert werden, und sich eine begrenzte Anzahl von Hardware- und Softwareressourcen teilen. In einer derart komplexen und dynamischen Umgebung ist das Auftreten von Leistungsproblemen (z. B. langsame Anwendungsreaktionen) eher die Regel als die Ausnahme. Darüber hinaus sind der manuelle Betrieb und die Wartung von Cloud-Microservices oft fehleranfällig. Daher besteht ein dringender Bedarf an einem automatischen System zur Verwaltung von Leistungsproblemen, das abnormales Verhalten erkennen, die Ursachen aufdecken und Abhilfemaßnahmen empfehlen kann. In dieser Arbeit werden Methoden zur automatischen Ursachenlokalisierung und Behebung von Leistungsproblemen in Cloud-Microservices erforscht. Das Hauptziel dieser Arbeit ist es, zu identifizieren, wo und warum ein Leistungsproblem auftritt, und dann zu entscheiden, wie es behoben werden kann. Zu diesem Zweck bietet diese Arbeit (1) eine Methode zur Lokalisierung des fehlerhaften Dienstes, von dem ein Leistungsproblem ausgeht; (2) zwei Methoden zur Identifizierung der anomalen Metriken, die ein Leistungsproblem verursachen, unter Verwendung von Deep Learning bzw. räumlich-zeitlicher kausaler Inferenz (CI); (3) eine Methode zur Auswahl der am besten geeigneten Wiederherstellungsmaßnahmen zur Entschärfung des Leistungsproblems. Insgesamt diagnostizieren die in dieser Arbeit vorgestellten Methoden die Grundursachen und empfehlen Abhilfemaßnahmen in Echtzeit, ohne dass eine Anwendungsinstrumentierung und historische Fehlerfälle erforderlich sind. Unsere Methoden wurden in Prototypen implementiert und experimentell an repräsentativen Microservices-Benchmarks evaluiert. Die Auswertungen zeigen, dass sie zur Unterstützung der automatischen Leistungsdiagnose und -wiederherstellung in Cloud-Microservices, zur Verbesserung der Servicezuverlässigkeit und der Endbenutzererfahrung eingesetzt werden können. Die Ergebnisse wurden auf renommierten internationalen Konferenzen veröffentlicht.

This thesis presents and evaluates two novel methods for the object shape estimation from point clouds. Both methods use prior knowledge of the expected object shape. In the first part of this thesis a novel robust mesh-based shape estimation method is presented. The estimation method uses the prior knowledge from a statistical shape model. The statistical shape model is used to define a similarity error. This similarity error is used to stabilize the estimation procedure. Different functions for a similarity error are evaluated and it is shown that a quadratic similarity error function achieved the lowest error in dependency of the noise in the point cloud. It is shown that the implemented method achieves more accurate results for noisy point clouds than other reconstruction methods like the Poisson, SSD and Wavelet reconstruction. It is shown that the implemented method achieves a smaller reconstruction error for incomplete point clouds than other reconstruction methods like the Poisson, SSD and Wavelet reconstruction. It is evaluated how the weight of the similarity error influences the achieved accuracy. It is shown how a point cloud uncertainty value can be computed to set the weight of the similarity error. In addition the runtime behaviour, the influence of the number of used shapes, the influence of the object pose error and the estimation for missing areas in point clouds is evaluated. In the second part of this thesis a novel volumetric-based shape estimation method is presented. The estimation method uses the prior knowledge from a Gaussian process latent variable model. The latent space of the Gaussian process latent variable model is used for the optimization. Two different similarity errors are introduced to stabilize the estimation procedure. It is shown how the similarity errors can reduce possible distortions on the estimated object surface. It is evaluated how the number of DCT coefficients and the size of the latent space influence the estimated shape. It is demonstrated how different artifacts can occur on the object surface during the interpolation between multiple shapes. It is also shown how these artifacts can be reduced. In addition different failure cases during the interpolation between multiple shapes are evaluated. It is shown how the estimated shape can be used to increase the accuracy and completeness of the measured point cloud. In addition the runtime behaviour is evaluated., Diese Arbeit präsentiert und evaluiert zwei neue Methoden zur Schätzung von Formen aus Punktwolken. Beide Methoden nutzen Vorwissen über die erwartete Objektform. Im ersten Teil der Arbeit wird eine neue robuste mesh-basierte Schätzungsmethode präsentiert. Die Schätzungsmethode nutzt das Vorwissen von einem Statistical Shape Model. Das Statistical Shape Model wird verwendet, um einen Ähnlichkeitsfehler zu definieren, mit dem der Schätzungsprozess stabilisiert wird. Mehrere Ähnlichkeitsfehlerfunktionen werden evaluiert und es wird gezeigt, dass eine quadratische Ähnlichkeitsfehlerfunktion den geringesten Fehler in Abhängigkeit des Rauschens in der Punktwolke aufweist. Die Methode erreicht genauere Resultate für verrauschte Punktwolken, als die Poisson, SSD und Wavelet Rekonstruktion. Weiterhin erreicht die Methode einen geringeren Rekonstruktionsfehler für unvollständige Punktwolken, als die Poisson, SSD und Wavelet Rekonstruktion. Es wird evaluiert, wie das Gewicht des Ähnlichkeitsfehlers die erreichbare Genauigkeit beeinflusst. Weiterhin wird gezeigt, wie ein Unsicherheitswert für eine Punktwolke berechnet werden kann, um das Gewicht des Ähnlichkeitsfehlers zu setzen. Zusätzlich wird das Laufzeitverhalten, der Einfluss von der Anzahl der Formen, der Einfluss des Posenfehlers und die Schätzung für fehlende Bereiche in der Punktwolke evaluiert. Im zweiten Teil der Arbeit wird eine neue volumetrisch-basierte Schätzungsmethode präsentiert. Die Schätzungsmethode nutzt das Vorwissen von einem Gaussian Process Latent Variable Model. Der latente Raum des Gaussian Process Latent Variable Models wird für die Optimierung genutzt. Zwei verschiedene Ähnlichkeitsfehler werden eingeführt, um den Schätzungsprozess zu stabilisieren. Es wird gezeigt, wie die Ähnlichkeitsfehler mögliche Verzerrungen auf der geschätzten Oberfläche reduzieren. Weiterhin wird evaluiert, wie die Anzahl der DCT Koeffizienten und die Größe des latenten Raumes die geschätzte Form beeinflussen. Es wird gezeigt, wie verschiedene Artefakte auf der Objektoberfläche während der Interpolation zwischen Formen auftreten können. Dabei wird gezeigt, wie diese Artefakte reduziert werden können. Zusätzlich werden mehrere verschiedene Fehlerfälle während der Interpolation zwischen Formen evaluiert. Weiterhin wird gezeigt, wie die geschätzte Form verwendet werden kann, um die Genauigkeit und Vollständigkeit der gemessenen Punktwolke zu verbessern. Zusätzlich wird das Laufzeitverhalten evaluiert.

When a high-ranking British politician was falsely accused of child abuse by the BBC in November 2012, a wave of short messages followed on the online social network Twitter leading to considerable damage to his reputation. However, not only did the politician’s image suffer considerable damage, moreover, he was also able to sue the BBC for £185,000 in damages. On the relatively new media of the internet and specifically in online social networks, digital wildfires, i.e., fast spreading, counterfactual or even intentionally misleading information occur on a regular basis and lead to severe repercussions. Although the example of the British politician is a simple digital wildfire that only damaged the reputation of a single person, there are more complex digital wildfires whose consequences are more far-reaching. This thesis deals with the capture, automatic processing, and investigation of a complex digital wildfire, namely, the Corona and 5G misinformtionsevent - the idea that the COVID-19 outbreak is somehow connected to the introduction of the 5G wireless technology. In this context, we present a system whose application allows us to acquire large amounts of data from the online social network Twitter and thus create the database from which we extract the digital wildfire in its entirety. Furthermore, we present a framework that provides the playing field for investigating the spread of digital wildfires. The main findings that emerge from the study of the 5G and corona misinformation event can be summarised as follows. Although published work suggests that a purely structure-based analysis of the information spread allows for early detection, there is no way of predictively labelling spreading information as probably leading to a digital wildfire. Digital wildfires do not emerge out of nowhere but find their origin in a multitude of already existing ideas and narratives that are reinterpreted and recomposed in the light of a new situation. It does not matter if ideas and explanations contradict each other. On the contrary, it seems that it is the existence of contradictory explanations that unites supporters from different camps to support a new idea. Finally, it has been shown that the spread of a digital wildfire is not the result of an information cascade in the sense of single, particularly influential short messages within a single medium. Rather, a multitude of small cascades with partly contradictory statements are responsible for the rapid spread. The dissemination media are diverse, and even more so, it is precisely the mix of different media that makes a digital wildfire possible., Als ein hochrangiger britischer Politiker im November 2012 von der BBC fälschlicherweise des Kindesmissbrauchs beschuldigt wurde, folgte eine Welle von Kurznachrichten im sozialen Online-Netzwerk Twitter, die zu einer erheblichen Schädigung seines Rufs führte. Doch nicht nur das Image des Politikers erlitt erheblichen Schaden, er konnte die BBC auch auf 185.000 Pfund Schadensersatz verklagen. In den relativ neuen Medien des Internets und speziell in den sozialen Online-Netzwerken kommt es regelmäßig zu sogenannten Digital Wildfires, d.h. zu sich schnell verbreitenden, kontrafaktischen oder sogar bewusst irreführenden Informationen, mit schwerwiegenden Folgen. Obwohl es sich bei dem Beispiel des britischen Politikers um ein einfaches Digital Wildfire handelt, welches nur den Ruf einer einzelnen Person schädigte, gibt es komplexere Digital Wildfires, deren Folgen weitreichender sind. Diese Arbeit befasst sich mit der Erfassung, automatischen Verarbeitung und Untersuchung eines komplexen Digital Wildfires, nämlich dem Corona- und 5G-Misinformationsevent - der Idee, dass der COVID-19-Ausbruch irgendwie mit der Einführung der 5GMobilfunktechnologie zusammenhängt. In diesem Zusammenhang stellen wir ein System vor, dessen Anwendung es uns ermöglicht, große Datenmengen aus dem sozialen Online-Netzwerk Twitter zu erfassen und so die Datenbank zu erstellen, aus der wir den digitalen Flächenbrand in seiner Gesamtheit extrahieren. Außerdem stellen wir ein Framework vor, welches das Spielfeld für die Untersuchung der Ausbreitung von Digital Wildfires bietet. Die wichtigsten Erkenntnisse, die sich aus der Untersuchung des 5G- und Corona-Misinformationevents ergeben, lassen sich wie folgt zusammenfassen. Obwohl veröffentlichte Arbeiten darauf hindeuten, dass eine rein strukturbasierte Analyse der Informationsausbreitung eine frühzeitige Erkennung ermöglicht, gibt es keine Möglichkeit, die Informationsausbreitung im Voraus als wahrscheinlich zu einem digitalen Flächenbrand führend zu kennzeichnen. Digital Wildfires entstehen nicht aus dem Nichts, sondern haben ihren Ursprung in einer Vielzahl bereits bestehender Ideen und Erzählungen, die im Lichte einer neuen Situation neu interpretiert und zusammengesetzt werden. Dabei spielt es keine Rolle, ob sich Ideen und Erklärungen gegenseitig widersprechen. Im Gegenteil, es scheint, dass gerade das Vorhandensein widersprüchlicher Erklärungen die Befürworter aus verschiedenen Lagern dazu bringt, eine neue Idee zu unterstützen. Schließlich hat sich gezeigt, dass die Ausbreitung eines digitalen Flächenbrandes nicht das Ergebnis einer Informationskaskade im Sinne einzelner, besonders einflussreicher Kurznachrichten innerhalb eines einzigen Mediums ist. Vielmehr ist eine Vielzahl von kleinen Kaskaden mit zum Teil widersprüchlichen Aussagen für die rasante Ausbreitung verantwortlich. Die Verbreitungsmedien sind vielfältig, mehr noch, es ist gerade der Mix aus verschiedenen Medien, der zu einem Digital Wildfire führt.

Today's Internet serves a huge variety of different applications with diverse and ever increasing demands on the underlying network. Among others, current trends towards immersive entertainment, like 8K video streaming or VR gaming, pose new challenges on end-to-end bandwidth volume and have stringent delay requirements. At the same time, the number of users is growing, as well as the users' expectations on the delivered service quality. As a consequence, delivering good Quality of Experience (QoE) becomes an ever more challenging task and - due to the steadily increasing number of providers - the satisfaction of subscribers and users is a substantial factor to remain competitive on the market. As a consequence, QoE management has emerged as a key research topic over the past years and constantly gains importance for several stakeholders in the Internet ecosystem. This monograph examines relevant research questions related to QoE management on the example of HTTP Adaptive Streaming (HAS), which is to date the application contributing the most to the global IP traffic. One of the major challenges of QoE management is to understand the complex interplay of application- and network-specific parameters and their impact on the user satisfaction. The first part of this thesis shows how QoE-relevant performance metrics for HAS can efficiently be retrieved for a given - and potentially huge - input parameter space by means of analytical modeling. More specifically, we use an existing approach relying on discrete-time analysis, which models an HAS client's video buffer, and we extend it so to reflect the HAS-typical quality adaptation behavior. For given input network characteristics, such as the available bandwidth and its variation, as well as for various video- and player-specific settings, like the quality switching thresholds, the model yields probabilistic outputs for the video buffer's filling state. From that, all relevant HAS metrics, e.g., the stalling behavior and the delivered video quality, can be derived, allowing to efficiently tune HAS parameters in accordance with each other, so as to optimize the QoE. The second part quantifies possible positive effects of using variable segment durations for HAS. Instead of relying on a content-agnostic video segmentation strategy with fixed segment durations, the variable approach - proposed by Netflix as shot-based encoding - takes the video content into account by segmenting the video at scene-cuts. This results in segments of different lengths, but promises to reduce the number of costly I-frames during the encoding and hence, to increase the encoding efficiency. However, no comparative study highlighting the impact of this technique on the HAS ecosystem has been conducted, yet. Thus, we first provide a broad investigation on the bitrate reduction that can be achieved with the variable approach. In a second step, we evaluate by means of a measurement study its impact on the streaming performance, taking into account three different adaptation heuristics. Our results show that variable segment durations can significantly reduce the bitrate requirements and - as a result - are capable of increasing the HAS QoE. The third part of this thesis focuses on how mobile network operators (MNOs) can exploit new features provided by the 5G networking architecture, so to overcome current QoE monitoring limitations. More specifically, we propose to make use of Network Functions (NFs) which are introduced with 5G and dedicated for improved analytics, complex computations, and for the interaction with third parties, such as content providers. These capabilities enable a variety of potentials, like, for example, estimating the QoE by applying Machine Learning (ML) techniques. From the perspective of an MNO, we elaborate on the involved challenges of introducing such an ML-based QoE estimation in 5G networks and by means of a simulation-based feasibility study, we demonstrate that the QoE can reliably be estimated solely based on network KPIs. In this scope, we perform a quantitative comparison, addressing the estimation accuracy of different state-of-the-art regression techniques, and discuss them with respect to different relevant qualitative aspects., Das heutige Internet wird für eine Vielzahl verschiedenartiger Anwendungen genutzt. Diese haben zum einen sehr diverse Anforderungen an das zugrundeliegende Netz, welche zum anderen auch stetig steigen. Besonders stark ist dieser Trend bei den Unterhaltungsmedien zu beobachten. Ultrahochauflösendes Video Streaming, zum Beispiel in 8K, fordert immer höhere Bandbreiten ein, während Onlinespiele zusätzlich immer striktere Bedingungen bezüglich der maximal auftretenden Paketverzögerungen haben. Können diese Anforderungen vom Netz nicht erfüllt werden, so wird die vom Nutzer subjektiv wahrgenommene Qualität der Anwendung beeinträchtigt. Beispielsweise führt eine zu geringe Bandbreite im Fall von Video Streaming zu Wiedergabeunterbrechungen und schlechter Bildqualität. Wenn bei Voice-over-IP Telefonaten Paketverlust oder -verzögerung auftreten, so wird die Qualität der Sprachübertagung wesentlich gestört. Um die subjektive Wahrnehmung zu quantifizieren, hat sich in den letzten Jahren in der Forschung das Konzept "Quality of Experience" (QoE) etabliert, welches den Grad der (Un)-zufriedenheit des Nutzers eines Services beschreibt. Dieser resultiert aus der Erfüllung der individuellen Erwartung an den Service. Während zum einen die Erwartungshaltung der einzelnen Nutzer stetig dahingehend zunimmt, dass die Anwendungen stabil und ohne Qualitätseinbußen laufen, werden auch die Angebote selbst, wie zum Beispiel Video-on-Demand Plattformen, immer beliebter. So nimmt die tägliche Nutzung von Video Streaming, virtuellen Konferenzen oder auch Cloud Gaming weltweit zu. Diese Trends, gepaart mit den kontinuierlich steigenden Anforderungen heutiger Services an das Netz, stellen sowohl Anwendungs- als auch Netzanbieter vor große Herausforderungen. Zum einen muss die Infrastruktur entsprechend skaliert sein, so dass Applikationen flüssig laufen und den Nutzern eine größtmögliche Zufriedenheit geboten wird, um sie nicht an die Konkurrenz zu verlieren. Zum anderen aber müssen die Anbieter kostengünstig agieren, um wirtschaftlich rentabel zu bleiben, um so am stetig wachsendem Markt konkurrenzfähig zu sein. Um diese Ziele zu vereinen, benötigt es intelligente Mechanismen auf Netz- und Anwendungsebene, die es erlauben, vorhandene Ressourcen möglichst effizient zu nutzen, aber dennoch den verschiedenen Anwendungsanforderungen gerecht zu werden. "Quality of Service" (QoS) Management erlaubt es, relevante Netzwerkparameter wie zum Beispiel Durchsatz oder Paketverzögerungen zu messen und bei Bedarf diese Parameter mit Hilfe verschiedener Steuerungsmechanismen, wie zum Beispiel Bandbreitenreservierung für einzelne Verbindungen, zu verbessern. Zwar ist durch die Verbesserung der Netzwerkparameter von einer Verbesserung der Anwendungsqualität auszugehen, die genaue Auswirkung auf die vom Nutzer wahrgenommene Dienstgüte kann jedoch nur schwer quantifiziert werden. Aus diesem Grund geht QoE Management -- im Vergleich zu QoS Management -- einen Schritt weiter und berücksichtigt bei der Umsetzung von Steuerungsmechanismen weitere Kontextinformationen, wie die spezifischen Anforderungen der laufenden Anwendung, oder das vom Nutzer verwendete Endgerät und dessen Eigenschaften. Somit ermöglicht QoE Management eine gezieltere Anpassung des Netzwerks und der Anwendung, so dass vorhandene Ressourcen effizient genutzt werden, und die Nutzerzufriedenheit maximiert wird. Allerdings ist das eine sehr komplexe Aufgabe, gekoppelt mit einer Vielzahl an Herausforderungen, weshalb sich QoE Management in den letzten Jahren zu einem wichtigen Forschungsfeld entwickelt hat. Elementares Ziel ist es, leistungsfähige und optimierte Lösungen in Bezug auf die drei folgenden Grundbausteine zu entwickeln: Der erste ist die Modellierung und die Abschätzung von QoE. Dieser Baustein befasst sich damit, zu quantifizieren, wie Netzwerkparameter, anwendungsspezifische Einstellungen und die Erwartungshaltung des Nutzers dessen wahrgenommene Dienstgüte beeinflussen. Der zweite nötige Baustein, das QoE Monitoring, beschreibt die Fähigkeit, relevante Parameter im Netz und in der Anwendung, oder direkt die QoE, messen zu können. Schließlich, und das formt den dritten Grundbaustein, benötigt man noch Mechanismen, um das Netz und die Anwendung gezielt steuern zu können, um am Ende die QoE zu verbessern oder ein bestimmtes Level an Nutzerzufriedenheit garantieren zu können. Diese Arbeit adressiert die verschiedenen Herausforderungen von QoE Management, stellt unterschiedliche Lösungsansätze in Bezug auf alle drei Bausteine vor und evaluiert diese im Hinblick auf ihre Umsetzbarkeit und Leistungsfähigkeit. Zunächst stellen wir ein analytisches Modell vor, welches auf Warteschlangentheorie basiert und in der Lage ist, QoE-relevante Metriken für adaptives Video Streaming effizient zu berechnen. Das Modell nimmt als Eingabe verschiedene netz-, video- und anwendungsspezifische Parameter entgegen. Dazu gehören unter anderem die vorhandene Bandbreite und deren Schwankung, die verfügbaren Videobitraten und die maximale Kapazität des Videopuffers. Die hohe Effizienz des Modells erlaubt es, mit überschaubarem Zeitaufwand eine Vielzahl an verschiedenen Parameterkombinationen zu testen und somit deren Zusammenspiel und Einfluss auf die QoE zu evaluieren. Es kann also benutzt werden, um die einzelnen Einstellungsparameter von adaptivem Streaming so zu optimieren, dass unter verschiedenen Netzwerkbedingungen die vom Nutzer erfahrene Dienstgüte maximiert wird. Des Weiteren untersuchen wir in dieser Arbeit, inwiefern eine effizientere Strategie zur Videosegmentierung die QoE von Streaminganwendungen verbessern kann. Typischerweise wird ein Video für adaptives Streaming - ohne jegliche Berücksichtigung des Videoinhalts - in gleichlange Segmente von wenigen Sekunden Dauer unterteilt und jedes dieser Segmente mit verschiedenen Bitraten codiert. Während der Wiedergabe kann somit die Qualität dynamisch an die aktuell verfügbare Bandbreite angepasst werden. Allerdings verringert eine solche, von der Videostruktur unabhängige Segmentierung, die Effizienz beim Encoding. Berücksichtigt man jedoch die Charakteristiken des zugrundeliegenden Videos und unterteilt das Video an den Stellen, an welchen ein Szenenwechsel stattfindet, dann kann das die Effizienz des Encodings steigern, liefert aber Segmente von variabler Dauer. Zunächst quantifizieren wir unter Einbeziehung verschiedener encodingspezifischer Einflussfaktoren, wie viel Bitrate der variable Ansatz im Vergleich zum konventionellen Ansatz einsparen kann. Wir zeigen, dass das Potenzial von variablen Segmentdauern am stärksten vom gewählten Videoclip selbst abhängt, und dass die Videobitrate bei gleichbleibender Qualität signifikant reduziert werden kann. In einem zweiten Schritt evaluieren wir die Leistungsfähigkeit von variablen Segmentdauern beim Video Streaming selbst. Wir stellen fest, dass die reduzierte Bitrate vor allem in solchen Situationen die QoE deutlich verbessern kann, in denen nur wenig Bandbreite zur Verfügung steht. Der dritte Teil dieser Arbeit bezieht sich auf den Baustein QoE Monitoring und untersucht, wie sich Netzwerkbetreiber maschinelles Lernen zu Nutze machen können, um die QoE basierend auf Telemetriedaten aus dem Netzwerk zu schätzen. Die 5G Netzwerkarchitektur führt neue, dedizierte Netzfunktionen für die Datenanalyse, komplexe Berechnungen, sowie für den Informationsaustausch mit Dritten, zum Beispiel einem Inhaltsanbieter, ein. Diese Netzfunktionen eröffnen eine Vielzahl neuartiger Möglichkeiten, wie zum Beispiel eine zuverlässige Schätzung der QoE im Netz durch die Integration von maschinellem Lernen. Zunächst diskutieren wir die Herausforderungen eines solchen Ansatzes in 5G Netzen und untersuchen die Anwendbarkeit und Leistungsfähigkeit verschiedener Regressionstechniken. Unsere Ergebnisse zeigen, dass gängige Techniken des maschinellen Lernens für QoE Monitoring, welches rein auf Telemetriedaten aus dem Netz beruht, mit hoher Effizienz und Genauigkeit eingesetzt werden können. Der vorgestellte Ansatz kann somit die Grundlage für ein wirkungsvolles QoE Management in zukünftigen Netzwerken bilden.

The thesis studies temporal graph problems and multistage problems. Since these problems typically are computationally hard, the focus is on developing fast exact (FPT-)algorithms. Temporal graph problems. A temporal graph is a graph whose edge set changes over time. Here, an edge at a specific time step is called time-edge. One of our main contributions is the introduction of a set of parameters tailored for temporal graph problems. We focus mainly on four problems on temporal graphs. Minimizing Reachability by Delaying. Given a temporal graph, a set of source vertices, and three integers k, r, and δ, the problem Minimizing Temporal Reachability by Delaying asks whether we can delay at most k time-edges by δ time steps (i.e., moving the edges δ time steps into the future) such that the sources can reach at most r vertices via temporal paths (i.e., paths using edges appearing in non-decreasing time-order). Our main contribution here is an algorithm running in O(r!k|G|) time, where |G| is the size of the temporal graph. This stands in contrast to the W[1]-hardness when parameterized by r for the problem of deleting instead of delaying time-edges. Restless Temporal Paths. A restless temporal path is a temporal path that can stay only a bounded amount of time at one vertex. Our main contribution here is a randomized algorithm to find a length-at-most-k restless temporal path from vertex s to vertex z in 4^ℓ |G|^O(1) time, where ℓ is the difference between k and the length of the shortest temporal path from s to z. Moreover, we show that finding these restless temporal paths is fixed-parameter tractable when parameterized by the timed feedback vertex number (that is, a temporal version of the classical feedback vertex number introduced in this thesis). This stands in contrast to the W[1]-hardness when parameterized by the feedback vertex number of the underlying graph. Temporal Separation. A temporal separator is a vertex set that intersects the vertices of all temporal paths between two distinguished vertices. We contribute two algorithms to find minimum temporal separators. The first algorithm runs in ω^ω |G|^O(1) time, where ω is the temporal core size—another parameter for temporal graphs introduced here. The second algorithm runs in 4^x |G|^O(1) time, where x is the timed feedback vertex number. This stands in contrast to the W[1]-hardness when parameterized by the feedback vertex number of the underlying graph. Temporal Matching. A δ-temporal matching in a temporal graph is a set of time-edges such that two distinct time-edges either do not share an endpoint or they are at least δ time steps apart. We present two algorithms to find δ-temporal matchings of size k. The first algorithm runs in O((2k − 1)^k |G|) time. Previously, only the fixed-parameter tractability for k + δ was known due to kernelization. The second algorithm runs in δ^O(ν) |G| time, where ν is the δ-vertex cover number—another new parameter we introduce here. Multistage problems. Many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the “multistage” view on computational problems, where the input contains a sequence of instances of a computational problem, and we are asked to find a sequence of solutions (one for each instance) under (dis)similarity constraints. We study two different variants. First, we study a “diverse multistage” variant, where consecutive solutions shall differ by at least ℓ elements, e.g., for reasons of fairness or wear minimization. We introduce a general framework allowing to prove that several diverse multistage problems are fixed-parameter tractable when parameterized by ℓ, namely Perfect Matching, s-t Path, and Plurality Voting. Second, we study Multistage Vertex Cover—a (non-diverse) “multistage” variant of Vertex Cover where we are given a sequence of instances of Vertex Cover, all instances asking for a vertex cover of size at most k. In contrast to the diverse multistage variant, consecutive vertex covers shall differ by at most ℓ vertices. In general, this multistage variant is motivated by scenarios where the adaptation of the current solution generates reconfiguration costs which shall not exceed ℓ. We show that Multistage Vertex Cover parameterized by k is W[1]-hard, already when ℓ = 2., Die Arbeit untersucht temporale Graphenprobleme und mehrstufige Probleme. Da diese Probleme typischerweise berechnungsschwer sind, liegt der Schwerpunkt auf der Entwicklung schneller, exakter (FPT-)Algorithmen. Temporale Graphenprobleme. Ein temporaler Graph ist ein Graph, dessen Kantenmenge sich im Laufe der Zeit verändert. Dabei wird eine Kante zu einem bestimmten Zeitpunkt als Zeitkante bezeichnet. Einer der wichtigsten Beiträge dieser Arbeit ist die Einführung einer Reihe von Parametern für temporale Graphenprobleme. Wir konzentrieren uns hauptsächlich auf vier temporale Graphenprobleme. Minimierung der Erreichbarkeit durch Verzögern. Gegeben ein temporaler Graph, eine Menge von Quellknoten und drei natürliche Zahlen k, r und δ, so fragt das Problem Minimierung der temporalen Erreichbarkeit durch Verzögern, ob wir höchstens k Zeitkanten um δ verzögern (d. h. die Zeitkante um δ Zeitschritte in die Zukunft verschieben) können, so dass die Quellen höchstens r Knoten über temporale Pfade erreichen können (d. h. Pfade mit Kanten, die in nicht abnehmender zeitlicher Reihenfolge auftreten). Hier ist unser Hauptbeitrag ein Algorithmus mit einer Laufzeit von O(r!k|G|), wobei |G| die Größe des temporalen Graphen ist. Dies steht im Gegensatz zu der W[1]-Schwere mit Parameter r, wenn wir Zeitkanten löschen statt verzögern. Rastlose temporale Pfade. Ein rastloser temporaler Pfad ist ein temporaler Pfad, der nur eine begrenzte Zeit an einem Knoten verweilen kann. Unser Hauptbeitrag ist ein randomisierter Algorithmus zum Finden eines rastlosen temporalen Pfades der Länge höchstens k von einem Knoten s zu einem Knoten z mit einer Laufzeit von 4^ℓ |G|^O(1) , wobei ℓ die Differenz zwischen k und der Länge eines kürzesten temporalen Pfades von s nach z ist. Außerdem zeigen wir, dass das Finden dieser rastlosen temporalen Pfade in FPT liegt, wenn das Problem mit der temporalen kreiskritischen Knotenzahl (das ist eine temporale Version der klassischen kreiskritischen Knotenzahl, die in dieser Arbeit eingeführt wird) parametrisiert wird. Dies steht im Gegensatz zu der W[1]-Schwere, wenn das Problem mit der kreiskritischen Knotenzahl des zugrundeliegenden Graphen parametrisiert wird. Temporale Trennung. Ein temporaler Trenner ist eine Knotenmenge, die die die Knotenmenge aller zeitlichen Pfade zwischen zwei bestimmten Knoten schneidet. Wir präsentieren zwei Algorithmen, um minimale temporale Trenner zu finden. Der erste Algorithmus hat eine Laufzeit von ω^ω |G|^O(1) , wobei ω die temporale Kerngröße ist – ein weiterer hier eingeführter Parameter für temporale Graphen. Der zweite Algorithmus hat eine Laufzeit von 4^x |G|^O(1) , wobei x die temporale kreiskritische Knotenzahl ist. Dies steht im Gegensatz zur der W[1]-Schwere, wenn das Problem mit der kreiskritischen Knotenzahl des zugrundeliegenden Graphen parametrisiert wird. Temporale Paarung. Ein δ-temporale Paarung in einem temporalen Graphen ist eine Menge von Zeitkanten, in der zwei unterschiedliche Zeitkanten entweder keinen gemeinsamen Endpunkt haben oder mindestens δ Zeitschritte voneinander entfernt sind. Wir entwickeln zwei Algorithmen, um δ-temporale Paarungen der Größe k zu finden. Der erste Algorithmus hat eine Laufzeit von O((2k − 1)^k |G|). Bislang war nur bekannt, dass dieses Problem in FPT liegt, wenn es mit k + δ parametrisiert wird. Der zweite Algorithmus hat eine Laufzeit von δ^O(ν) |G|, wobei ν die δ-Knotenüberdeckungszahl ist – ein weiterer neuer Parameter, der hier eingeführt wird. Mehrstufige Probleme. Viele Probleme müssen nicht nur einmal gelöst werden, sondern öfter und unter wechselnden Bedingungen. Dieser Umstand wird durch die „mehrstufige“ Betrachtung von Problemen adressiert, wobei die Eingabe eine Sequenz von Instanzen eines Problems enthält und wir nach einer Sequenz von Lösungen (für jede Instanz eine) unter (Un-)Ähnlichkeitsbeschränkungen suchen. Wir untersuchen zwei verschiedene Varianten. Erstens untersuchen wir eine „diverse mehrstufige“ Variante, bei der sich aufeinanderfolgende Lösungen um mindestens ℓ Elemente unterscheiden, z. B. aus Gründen der Gerechtigkeit oder der Verschleißminimierung. Wir führen ein allgemeines Werkzeug ein, welches erlaubt zu beweisen, dass mehrere diverse mehrstufige Probleme in FPT liegen, wenn sie mit ℓ parametrisiert werden. Wir wenden das Werkzeug für die Probleme Perfekte Paarung, s-t Pfad und Pluralitätsabstimmung an. Zweitens untersuchen wir die Mehrstufige Knotenüberdeckung – eine (nicht-diverse) „mehrstufige“ Variante von der Knotenüberdeckung, wobei alle Instanzen nach einer Knotenüberdeckung der Größe höchstens k fragen. Im Gegensatz zu der diversen mehrstufigen Variante dürfen aufeinanderfolgende Knotenüberdeckungen sich um höchstens ℓ Knoten unterscheiden. Im Allgemeinen ist diese mehrstufige Variante motiviert durch Szenarien, in denen die Anpassung der aktuellen Lösung Rekonfigurationskosten verursacht, die ℓ nicht überschreiten dürfen. Wir zeigen, dass Mehrstufige Knotenüberdeckung W[1]-schwer ist, wenn es mit k parametrisiert wird, selbst wenn ℓ = 2 gilt.

neurolib is a computational framework for whole-brain modeling written in Python. It provides a set of neural mass models that represent the average activity of a brain region on a mesoscopic scale. In a whole-brain network model, brain regions are connected with each other based on biologically informed structural connectivity, i.e., the connectome of the brain. neurolib can load structural and functional datasets, set up a whole-brain model, manage its parameters, simulate it, and organize its outputs for later analysis. The activity of each brain region can be converted into a simulated BOLD signal in order to calibrate the model against empirical data from functional magnetic resonance imaging (fMRI). Extensive model analysis is made possible using a parameter exploration module, which allows one to characterize a model’s behavior as a function of changing parameters. An optimization module is provided for fitting models to multimodal empirical data using evolutionary algorithms. neurolib is designed to be extendable and allows for easy implementation of custom neural mass models, offering a versatile platform for computational neuroscientists for prototyping models, managing large numerical experiments, studying the structure–function relationship of brain networks, and for performing in-silico optimization of whole-brain models.

Complementors accumulate reputation on an ever-increasing number of online platforms. While the effects of reputation within individual platforms are well-understood, its potential effectiveness across platform boundaries has received much less attention. This research note considers complementors’ ability to increase their trustworthiness in the eyes of prospective consumers by importing reputational data from another platform. The study evaluates this potential lever by means of an online experiment, during which specific combinations of on-site and imported rating scores are tested. Results reveal that importing reputation can be advantageous – but also detrimental, depending on ratings’ values. Implications for complementors, platform operators, and regulatory bodies concerned with online reputation are considered.

Inertial-sensor-based attitude estimation is a crucial technology in various applications, from human motion tracking to autonomous aerial and ground vehicles. Application scenarios differ in characteristics of the performed motion, presence of disturbances, and environmental conditions. Since state-of-the-art attitude estimators do not generalize well over these characteristics, their parameters must be tuned for the individual motion characteristics and circumstances. We propose RIANN, a ready-to-use, neural network-based, parameter-free, real-time-capable inertial attitude estimator, which generalizes well across different motion dynamics, environments, and sampling rates, without the need for application-specific adaptations. We gather six publicly available datasets of which we exploit two datasets for the method development and the training, and we use four datasets for evaluation of the trained estimator in three different test scenarios with varying practical relevance. Results show that RIANN outperforms state-of-the-art attitude estimation filters in the sense that it generalizes much better across a variety of motions and conditions in different applications, with different sensor hardware and different sampling frequencies. This is true even if the filters are tuned on each individual test dataset, whereas RIANN was trained on completely separate data and has never seen any of these test datasets. RIANN can be applied directly without adaptations or training and is therefore expected to enable plug-and-play solutions in numerous applications, especially when accuracy is crucial but no ground-truth data is available for tuning or when motion and disturbance characteristics are uncertain. We made RIANN publicly available.

We study combinatorial structures in large-scale mixed-integer (nonlinear) programming problems arising in gas network optimization. We propose a preprocessing strategy exploiting the observation that a large part of the combinatorial complexity arises in certain subnetworks. Our approach analyzes these subnetworks and the combinatorial structure of the flows within these subnetworks in order to provide alternative models with a stronger combinatorial structure that can be exploited by off-the-shelve solvers. In particular, we consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. We propose a refined model that allows to precompute tighter bounds for each operation mode and a number of model variants based on the refined model exploiting these tighter bounds. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode. We evaluate our model variants on reference benchmark data, showing that they reduce the average running time between 10% for easy instances and 46% for hard instances. Moreover, for three of four considered networks, the average number of search tree nodes is at least halved, showing the effectivity of our model variants to guide the solver’s search.

In this chapter, we consider realizing a reservoir computer on an electronic chip that allows for many tens of network nodes whose connection topology can be quickly reconfigured. The reservoir computer displays analog-like behavior and has the potential to perform computations beyond that of a classic Turning machine. In detail, we present our preliminary results of using a physical reservoir computer for performing the task of identifying written digits. The reservoir is realized on a commercially available electronic device known as a field-programmable gate array on which we create an autonomous Boolean network for information processing. Even though the network nodes are Boolean logic elements, they display analog behavior because there is no master clock that controls the nodes. In addition, the electronic signals related to the written-digit images are injected into the reservoir at high speed, leading to the possibility of full-image classification on the nanosecond time scale. We explore the dynamics of the autonomous Boolean networks in response to injected signals and, based on these results, investigate the performance of the reservoir computer on the written-digit task. For a wide range of reservoir structures, we obtain a typical performance of \(\sim \)90% for correctly identifying a written digit, which exceeds that obtained by a linear classifier. This work paves the way for achieving low-power, high-speed reservoir computing on readily available field-programmable gate arrays, which are well matched to existing computing infrastructure.

Applications of Software-Defined Networking (SDN) to the Internet Routing hold great promises for supporting the ever-growing performance requirements of Internet applications. The inherent centralization of these SDN approaches on the Internet routing comes with the following concerns: 1) privacy , the operators are reluctant to share private routing information, 2) separation of responsibilities , the Internet eXchange Point (IXP) running the centralized controller is involved in the routing and forwarding at too many levels, and 3) scalability , the growing number of IP prefixes routed on the Internet (i.e., hundreds of thousands) pose extremely high requirements at both the control- and data-planes, e.g., several minutes for policy compilations and a large number of forwarding rules, in SDN. In this paper, we propose DeSI to apply SDN at IXPs by considering the above concerns. We break this centralization by devising an SDN-enabled IXP architecture in which each member connects to an SDN-enabled IXP through its SDN controller and SDN switches, thus tackling privacy, scalability, and separation of concerns issues. To spur adoption, we introduce an expressive, yet simple, language to configure the routing policies of the members. Our evaluation shows that DeSI needs n times fewer forwarding table entries for an IXP in which n is the number of IXP members. DeSI also gives the possibility of slowly migrating to the SDN-enabled IXPs.

ZusammenfassungWährend Universitäten mit ihrer Infrastruktur und Kompetenz ideale Bedingungen für den Betrieb von Tor-Knoten bieten, ist ihr Anteil am Tor-Netz erstaunlich gering. Wir berichten über unsere Erfahrungen beim Betrieb von zwei Exit-Knoten an Universitäten und geben Empfehlungen für deren Betrieb.

Two-dimensional (2D) radiographs are widely used for diagnosis, treatment planning, and follow-up in orthopedics. The images depict bone at high contrast to surrounding tissue and capture weight-bearing situations when taken in upright position. Compared to three-dimensional (3D) computed tomography (CT), 2D radiographs further expose the patient to relatively low radiation doses. Projectional radiography does, however, currently not allow for a full 3D assessment of anatomical structures. Measurements on 2D radiographs are inherently limited to the 2D plane only, and it is often difficult for an observer to resolve ambiguities in 3D anatomical shape and pose due to perspective distortion and overlapping structures in a given image. This dissertation addresses the issue of clinical 3D assessment of anatomical shape, position, and spatial relation from 2D X-ray images through computer-aided reconstruction techniques. For this purpose, a fully automated method is proposed to derive the patient-specific 3D shape and pose of bony structures from a single or a few clinical 2D radiographs by means of intensity-based 2D/3D registration. The method generates different variations of 3D volumetric meshes from articulated statistical shape and intensity models (A-SSIMs), with each mesh representing a plausible candidate of the patient-specific shape and bone-interior radiodensity according to a training population of CT datasets. The aim is to find the model instance that matches the depiction in the given 2D radiograph best, as it is assumed to represent a good approximation of the true, patient-specific anatomy. This is achieved by means of an optimization process, in which virtual X-ray images that mimic real X-rays of the anatomical structures of interest are projected from the 3D mesh variations until the similarity between virtual images and the given clinical images is maximized. The individual processing steps of the 2D/3D reconstruction framework are evaluated in detail based on clinical radiographs as well as artificially generated digitally reconstructed radiographs (DRRs) from CTs. Furthermore, the reconstruction method as a whole is evaluated in context of clinical applications in hip-joint replacement and osteosynthesis, showing the benefit of the proposed approach for treatment planning and postoperative follow-up in orthopedics., Die konventionelle Röntgenuntersuchung mittels Projektionsradiographie spielt eine wichtige Rolle in der medizinischen Diagnose, Behandlungsplanung und der Nachuntersuchung von orthopädischen Eingriffen. Röntgenbilder stellen Knochen in hohem Kontrast zu umliegenden Gewebe dar, können in stehender Position unter Last aufgenommen werden, und setzen den Patienten einer relativ geringen Strahlendosis im Vergleich zur Computertomographie (CT) aus. Die Projektionsradiographie erlaubt allerdings keine vollständige Bewertung anatomischer Strukturen im dreidimensionalen (3D-) Raum. Messungen auf Röntgenbilder sind naturgemäß nur auf eine zweidimensionale (2D-) Ebene beschränkt, und es ist selbst für Experten oft schwierig, Mehrdeutigkeiten bezüglich der anatomischen Form und Lage in einer gegebenen Röntgenaufnahme aufzulösen. In dieser Arbeit wird ein vollautomatisches, computergestütztes Verfahren vorgestellt, um die patientenspezifische 3D-Form und Lage von knöchernen Strukturen aus einer oder wenigen klinischen 2D-Röntgenaufnahmen zu rekonstruieren. Die Methode wählt 3D-Repräsentationen der Knochen aus artikulierten, statistischen Form- und Intensitätsmodellen (A-SSIMs), welche die Variation anatomischer Strukturen in Form, Röntgendichte und relativer Lage in einer gegebenen Population von CT-Datensätzen ausdrücken. In einem Optimierungsprozess werden die Modelle an die klinischen Röntgenbilder angepasst, bis ein Ähnlichkeitsmaß zwischen virtuellen Röntgenprojektionen aus den 3D-Repräsentationen und den klinischen Aufnahmen maximiert ist. Die Repräsentation, deren Darstellung in den virtuellen Röntgenbildern am besten den klinischen Röntgenaufnahmen entspricht, stellt dann eine Annäherung an die tatsächliche patientenspezifische 3D-Anatomie dar. Die einzelnen Verarbeitungsschritte des Rekonstruktionsverfahrens werden eingehend anhand klinischer Röntgenbilder und synthetischer Röntgenaufnahmen aus CTs evaluiert. Darüber hinaus wird die Rekonstruktionsmethode als Ganzes im Kontext klinischer Anwendungen wie dem Hüftgelenkersatz und der Osteosynthese ausgewertet. Die Ergebnisse zeigen den potentiellen Nutzen der intensitätsbasierten Rekonstruktionsmethode für eine Vielzahl von Anwendungen in der präoperativen Planung und Nachuntersuchung.

Artificial Intelligence for IT Operations (AIOps) combines big data and machine learning to replace a broad range of IT Operations tasks. The task of anomaly detection has a prominent position in ensuring the required reliability and safe operation in distributed software systems. However, the frequent software and hardware updates, system heterogeneity, and massive amount of data create a challenging environment. The detection of anomalies in these systems predominantly relies on metric, log, and trace data. Each of them provides a different view of the internal states of the systems. By induction, improving the detection in every data source increases the overall anomaly detection performance in the system. This thesis provides the following contributions. (1) We present a method based on variational inference and recurrent neural network to address the detection of anomalies in system metric data that possibly exhibit multiple modes of normal operation. (2) We propose a novel log parsing through language modelling that enables learning of log representations for downstream anomaly detection. We identify the learning of log representations as a major challenge toward a robust anomaly detection. Therefore, we additionally design a method that learns log representations by distinguishing between normal data from the system of interest and easily accessible anomaly samples obtained through the internet. (3) We describe a self-supervised anomaly detection task that utilizes the entire trace information to robustly detect anomalies that propagate through system components. (4) In a rule-based approach, we combine the presented methods for a multi-view anomaly detection. The methods presented in this thesis were implemented in prototypes and evaluated on various datasets including production data from a cloud provider. They provided (1) an F1 score of 0.85 on metric data, (2) parsing accuracy of 99% and F1 score improvement of 0.25 in log anomaly detection, (3) increase in F1 score of 7% in trace anomaly detection over the state of the art, and (4) broadened spectrum of detected anomalies. The results were peer-reviewed and published at renowned international conferences., Für den Betrieb großer und komplexer IT-Infrastrukturen in Rechenzentren werden immer häufiger KI-gestützte Methoden und Werkzeuge eingesetzt. Durch das Kombinieren von großen Mengen an Daten mit Machine Learning Prinzipien, können viele klassische Aufgaben in dem Betrieb und der Wartung von IT-Systemen ersetzt werden. Die Anomalieerkennung nimmt dabei eine besondere Stellung ein, um die geforderte Zuverlässigkeit und den sicheren Betrieb in verteilten Softwaresystemen zu gewährleisten. Die große Anzahl von heterogenen Komponenten und Diensten, häufige Software- und Hardware-Updates, die steigende Anzahl von Benutzern und Anwendungen sowie die riesigen zu verarbeitenden Datenmengen stellen eine signifikante Herausforderung dar. Die Anomalieerkennung in diesen Systemen basiert an mehreren komplementären Datenquellen (Metriken, Logs, Traces) zur Beschreibung und Analyse des aktuellen Systemzustandes, die zusammen einen einen gesamtheitlichen Einblick in das laufende System ermöglichen. Die Verbesserung der Anomalieerkennung in jeder der Datenquellen würde daher die Leistung der Anomalieerkennung im gesamten System verbessern. In dieser Arbeit liefern wir die folgenden Beiträge. (1) Wir stellen eine Methode zur Anomalieerkennung in metrischen Daten (von Monitoringsystemen) vor, die auf Variationsinferenz und rekurrenten neuronalen Netzen basiert, um eine zuverlässige Detektion trotz des wechselnden Systemmodi und des Vorhandenseins von Rauschen zu ermöglichen. (2) Wir erwähnen eine neuartige Log-Parsing Methode die auf Sprachmodellierung basiert ist. Diese Methode ermöglicht das Lernen von Log-Repräsentationen für die Anomalieerkennung, was einen wichtigen Meilenstein für eine robuste Anomalieerkennung darstellt. Aus diesem Grund haben wir im Zusatz einen klassifikation-basierten Ansatz entwickelt, der Log-Repräsentationen durch die Unterscheidung zwischen normalen Daten des untersuchten Systems und online verfügbaren Anomalie-Muster lernen kann. (3) Wir beschreiben eine sich selbst überwachende Pseudo-Anomalie-Erkennungsaufgabe, welche die gesamten Trace-Information nutzt, um robust Anomalien zu erkennen, die sich auf mehrere Systemkomponenten verteilen. (4) In einem regelbasierten Ansatz kombinieren wir die vorgestellten Methoden, um Anomalieerkennung mittels mehrere Datenquellen zu ermöglichen. Die in dieser Arbeit vorgestellten Methoden wurden in Prototypen implementiert und auf verschiedenen Datensätzen, in experimentellen Testbeds und auf Produktionsdaten einer großen kommerziell eingesetzten Cloud-Infrastruktur evaluiert. Die Ergebnisse zeigten (1) einen F1-Score von durchschnittlich 0,85 auf Metrik-Daten, (2) eine Genauigkeit von 99\% beim Log-Parsing und eine Verbesserung des F1-Scores um 0,25 gegenüber dem Stand der Technik bei der Erkennung von Log-Anomalien, sowie (3) eine Steigerung des F1-Scores um 7\% gegenüber dem aktuellen Stand der Technik in Trace basierten Anomalieerkennung und (4) eine Erweiterung der Spektrum der erkennbaren Anomalien. Die Gesamterkennung von Anomalien durch eine Kombination der Methoden führte ebenfalls zur Steigerung der Ergebnisse im Vergleich zu den Einzelmethoden. Die Erkenntnisse wurden auf renommierten internationalen Konferenzen veröffentlicht.

The growing trend towards high-mix and low-volume production demands more flexible and reconfigurable control for assembly systems. In unstructured or less structured environments, object detection and pose estimation is a key capability to enable industrial robotics applications such as grasping, handling and assembling. The integration and interconnectivity of such automation functions is fostered by Industry 4.0 through the adoption of service-based ecosystems. The main objective of this thesis is to create a service-based framework for robust object detection and pose estimation in manufacturing environments. This could resemble a viable alternative to traditional machine vision systems such as smart cameras and embedded PCs, which are challenged by the high diversity and fast-paced progress in the field of object detection and pose estimation. We approach this problem in three steps. In the first step, we propose a framework and demonstrate that it is realizable. It has a REST / gRPC interface that allows to handle all detection methods uniformly. A virtualization strategy enables upscaling and easy deployment, and the new OPC UA vision specification is exploited for integration of the detector services into the production environment. In a second step, we examine three exemplary object detection and pose estimation methods and prove that they can be integrated into the framework. This boils down to automatic training from a CAD model and parameterization without expert knowledge, which is possible for two of the three methods. Regarding the third method – a Deep Learning approach – we demonstrate that synthetic images can be generated from the model to enable training, but further measures are required to attain the desired pose accuracy. Finally, in a third step, we characterize the framework to identify its strengths and weaknesses compared to conventional machine vision systems. We perform a scenario-based analysis to determine certain quality attributes and find that both system types have their justification. The proposed service-based framework enables more efficient resource utilization, has a better configurability, maintainability and availability. On the other hand, conventional systems have better timing behavior and do not require such elaborate security measures. Timing, resource utilization and reusability are moreover strongly affected by the chosen detection method. Given a particular application, our characterization helps to identify the most suitable system type. Altogether, in this work we have contributed a novel type of vision system and demonstrated that it is a viable alternative for object detection and pose estimation applications. The framework structure as well as the identified architectural trade-offs can furthermore be generalized to other machine vision or automation tasks. Promising future research directions include facilitating the training of Deep Learning methods, quantifying architectural trade-offs in case studies, and integrating other vision applications to create an ecosystem of vision services., Der Trend zur Produktion von kleineren Losgrößen und mehr Varianten erfordert flexible und rekonfigurierbare Montagesysteme. Die Objekterkennung und Posenschätzung ist eine Schlüsseltechnologie, um Roboteranwendungen wie Handhabung und Montage in weniger strukturierten Umgebungen zu ermöglichen. Im Rahmen von Industrie 4.0 wird vorgeschlagen, die Integration und Vernetzung solcher Technologien durch Dienste-Plattformen zu fördern. Das Ziel dieser Arbeit ist die Schaffung einer Dienste-Plattform für robuste Objekterkennung und Posenschätzung in der Industrie. Dies wäre eine mögliche Alternative zu traditionellen Bildverarbeitungssystemen wie intelligenten Kameras oder PC-Systemen, die mit der großen Vielfalt und dem schnellen Fortschritt im Bereich Objekterkennung und Posenschätzung zu kämpfen haben. Diese Aufgabe gehen wir in drei Schritten an. Zuerst konzipieren wir eine Dienste-Plattform und zeigen, dass sie umsetzbar ist. Sie hat eine einheitliche REST / gRPC Schnittstelle für alle Objekterkennungsmethoden. Das Virtualisierungskonzept ermöglicht einfache Skalierung und Bereitstellung und die neue OPC UA Vision Spezifikation wird für die Integration in das Produktionsumfeld genutzt. In einem zweiten Schritt zeigen wir die beispielhafte Integration von drei repräsentativen Methoden zur Objekterkennung und Posenschätzung in die Plattform. Dazu müssen die Detektoren auf Basis eines CAD Modells trainiert und ohne Expertenwissen konfiguriert werden können. Für zwei der drei Methoden war dies ohne Weiteres möglich, für die dritte – einen Deep Learning Ansatz – nicht. Wir zeigen hier, wie synthetisch generierte Trainingsbilder genutzt werden können, um das Training dennoch zu ermöglichen. Im dritten Schritt untersuchen wir schließlich die Stärken und Schwächen der vorgeschlagenen Dienste-Plattform im Vergleich zu einem konventionellen System. Die Analyse verschiedenster Szenarien ergibt, dass beide Systeme ihre Berechtigung haben. Zu den Vorteilen der Plattform gehören effizientere Ressourcennutzung sowie bessere Konfigurierbarkeit, Wartbarkeit und Verfügbarkeit. Konventionelle Systeme punkten mit ihrem Zeitverhalten und bergen weniger Sicherheitsrisiken. Zeitverhalten, Ressourcennutzung und Wiederverwendbarkeit sind jedoch auch stark von der gewählten Detektionsmethode abhängig. Unsere Charakterisierung hilft, um für eine spezifische Anwendung den geeignetsten Systemtyp auszuwählen. In dieser Arbeit haben wir einen neuen Typ Bildverarbeitungssystem vorgeschlagen und gezeigt, dass er eine lohnende Alternative für Objekterkennungs- und Posenschätzungsanwendungen sein kann. Die Struktur der Plattform sowie Erkenntnisse zu architektonischen Abwägungen können auch auf andere Bildverarbeitungsanwendungen übertragen werden. Zukünftige Forschungsarbeiten könnten sich auf eine Vereinfachung des Trainings von Deep Learning Methoden, die Quantifizierung der architektonischen Abwägungen in Fallstudien, oder die Integration anderer Bildverarbeitungsaufgaben konzentrieren.

The progressing global digitalization is driving innovative network technologies, computation platforms, and data-driven services. The number of components such as sensors, actuators, computing, storage, and network nodes, as well as a variety of service applications increases and results in IT systems of high complexity. A complex system is prone to errors or failures, but users expect services always to be available. Furthermore, high availability is essential for utilizing IT systems in critical areas such as medicine, logistics, energy, or the manufacturing industry. There, failures that are not immediately resolved can lead to hazardous situations. Consequently, system operators are increasingly overwhelmed with the task of keeping complex IT systems at an operational state. Solutions that support the operation and maintenance of complex IT systems are required to support humans. For this purpose, artificial intelligence for IT system operations (AIOps) is being explored to improve the availability, maintainability, and reliability of IT systems. It combines the research areas of artificial intelligence, machine learning, and system operation to monitor relevant components, analyze the monitoring data, and automatically select and execute operations to maintain an efficient operational state. The automation should enable improved robustness against failures. This thesis introduces methods to increase the availability of IT systems by reducing the time required to resolve errors and failures. Thereby, system components whose operational state deviates from a known norm are referred to as anomalies. We employ pattern recognition to search monitoring data from anomalous components for specific patterns. The identification of these anomaly symptoms allows a comparison to historical occurrences of anomalies and an automatic selection of feasible operations to resolve them. Further, our implemented methods can identify patterns that are representing yet unknown anomalies. Such cases are delegated to human experts. This "human-in-the-loop" approach represents a step-by-step transfer of knowledge from human experts into our system., Die fortschreitende globale Digitalisierung treibt die Entwicklung von Netzwerktechnologien, Analyseplattformen und datengetriebenen Diensten voran. Damit einhergehend ist eine steigende Anzahl an Komponent wie Sensoren, Aktoren, Rechen- und Netzwerkknoten sowie unterschiedlichen Applikationen. Infolgedessen nimmt die Komplexit��t von IT Infrastrukturen stetig zu. Ein System mit hoher Komplexit��t ist anf��llig f��r Fehler oder Ausf��lle jedoch erwarten Anwender, dass die Dienste immer verf��gbar sind. Dar��ber hinaus ist eine hohe Verf��gbarkeit unerl��sslich f��r die Nutzung von IT Systemen in kritischen Bereichen wie Medizin, Logistik, Energie oder der Fertigungsindustrie. Dort haben Ausf��lle, die nicht schnell genug behoben werden, katastrophale Folgen. Die Konsequenz daraus ist, dass Betreiber zunehmend mit der Aufgabe ��berfordert sind die notwendige Verf��gbarkeit zu gew��hrleisten. Dies erfordert L��sungen, die den Betrieb und die Wartung von komplexen IT Systemen unterst��tzen. Daf��r wird der Einsatz KI-gest��tzter Methoden erforscht, die die Wartbarkeit, Verf��gbarkeit und Zuverl��ssigkeit von IT Systemen verbessern sollen. Diese werden eingesetzt um Systemkomponenten zu ��berwachen, die ��berwachungsdaten zu analysieren und bei Bedarf automatisch Operationen auszuw��hlen und auszuf��hren, um einen effizienten Betriebszustand aufrechtzuerhalten. Durch diese Automatisierung von Wartungs- und Administrationsaufgaben soll eine h��here Robustheit gegen��ber Ausf��llen realisiert werden. In dieser Arbeit erforschen wir Methoden, die die Verf��gbarkeit von IT Systemen erh��hen sollen, indem die notwendige Zeit f��r die Behebung von Fehlern und Ausf��llen reduziert wird. Dazu werden Daten von Systemkomponenten, deren Betriebszustand von einer bekannten Norm abweicht, nach spezifischen Mustern durchsucht. Diese als Anomaliesymptome bezeichneten Muster dienen dazu Fehlerf��lle zu identifizieren. Falls diese bereits in der Vergangenheit aufgetreten sind und erfolgreich Behoben wurden, erm��glicht das eine automatisierte und somit schnelle Wiederherstellung eines normalen Systemzustands. Die von uns entwickelten Erkennungsmethoden sind in der Lage Muster, die noch nicht bekannt sind, zu identifizieren und deren Behandlung an menschliche Experten zu delegieren. Dieser "Human-in-the-Loop"- Ansatz stellt eine schrittweise ��bertragung des Wissens von menschlichen Experten in unser System dar.

One of the great challenges in modern biology is understanding the genome and its translation into biological structures and function. In this context, the aim of this dissertation is to show that combinatorial approaches of traditional methods and novel machine learning ideas can be developed and successfully applied to analyze large-scale biological datasets and provide novel insights into genetic and transcriptomic variation. This proposed thesis is validated in two fields of biological research: genome-wide association studies (GWAS) and single-cell RNA sequencing (scRNA-Seq). For the analysis of such data, we propose three novel methods, each consisting of traditional methods on the one hand and state-of-the-art machine learning algorithms on the other. It is shown that these combinatorial approaches outperform both their individual methodological components and existing techniques on suitable corresponding datasets in terms of statistical power and accuracy. The standard approach to the evaluation of GWAS is based on testing each position in the genome individually for statistical significance of its association with the phenotype under investigation. To improve the analysis, we propose a combination of machine learning and statistical testing that takes correlation structures within the set of single-nucleotide polymorphisms (SNP) under investigation in a mathematically well-controlled manner into account. The general idea is to train an appropriate state-of-the-art classification algorithm, selecting a subset of candidate locations that are most relevant for the classifier’s decisions and examining only those for significant associations via multiple statistical hypothesis testing. This dissertation’s first methodological contribution, the two-step algorithm, COMBI, first trains a support vector machine to determine a subset of candidate SNPs and then performs hypothesis tests for these SNPs together with an adequate threshold correction. Applying COMBI to generated datasets as well as data from a WTCCC study (2007), we show that the novel method outperforms ordinary raw p-value thresholding and other state-of-the-art methods. COMBI presents higher power and precision than the examined alternatives while yielding fewer false (i.e. non-replicated) and more true (i.e. replicated) discoveries when its results are validated on later GWAS. Deep learning has become one of the leading methodologies in data science, which oftentimes greatly improves prediction performances in comparison to conventional approaches. Recently, explainable artificial intelligence has emerged as a novel area of research that goes beyond pure prediction improvement by extracting knowledge from deep learning methodologies through the interpretation of their results. Following these developments, we present the second methodological contribution of this dissertation, DeepCOMBI - an improved, deep learning- and explanation-based extension of the previously proposed method COMBI. The three-step algorithm of DeepCOMBI first trains a neural network to classify subjects into their respective phenotypes. Second, it explains the classifier’s decisions by applying layer-wise relevance propagation as one example from the pool of explanation techniques. The resulting importance scores are eventually used to determine a subset of the most relevant locations for multiple hypothesis testing in the third step, which remains unchanged as in the original COMBI method. DeepCOMBI is shown to outperform COMBI, raw p-value thresholding and other baseline methods on generated datasets and the 2007 WTCCC study. Beyond improving the identification of associations between phenotypes and genotypes, in this dissertation, we contribute to understanding how genetic information is translated into physical structures and biological function. When exploring the flow of sequential information from DNA to mRNA to proteins, we interpret the genome in the context of cell types and aim to identify the genes that are active in certain cells. Within this frame of reference, the goal of scRNA-Seq experiments is to define and catalog cell types from the transcriptional output of individual cells, which refers to an unsupervised clustering problem. To improve the clustering of small disease- or tissue-specific datasets, for which the identification of rare cell types is often problematic, we propose to combine conventional clustering algorithms with the machine learning concept of transfer learning to utilize large and well-annotated reference datasets. This dissertation’s third methodological contribution modifies the target dataset while incorporating key information from the reference dataset via non-negative matrix factorization before providing the modified dataset to a traditional downstream clustering algorithm. We empirically evaluate the benefits of the novel approach on simulated scRNA-Seq data as well as on publicly available datasets. Finally, we present results for analyzing a recently published small dataset and find improved clustering when transferring knowledge from a large independent reference dataset. To summarize, this dissertation contributes to a better understanding of the genome and the processes around its translation into biological structures and function. By proposing three approaches for the analysis of large-scale biological datasets combining traditional methods and state-of-the-art machine learning algorithms, it is shown that, in this regard, too, “the whole is greater than the sum of its parts” (indirect quote derived from Aristotle, 4th century BC)., Eine der größten Herausforderungen der modernen Biologie besteht darin, das Genom und seine Umwandlung in biologische Strukturen und Funktionen zu verstehen. In diesem Zusammenhang wird in dieser Dissertation gezeigt, dass kombinatorische Ansätze traditioneller Methoden und neuartiger Ideen des maschinellen Lernens entwickelt und erfolgreich angewendet werden können, um große biologische Datensätze zu analysieren und neue Einblicke in genetische und transkriptomische Variationen zu erhalten. Diese für diese Arbeit aufgestellte These wird in zwei Bereichen der biologischen Forschung validiert: genomweite Assoziationsstudien (GWAS) und Einzelzell-RNA-Sequenzierung (scRNA-Seq). Es werden insgesamt drei neue Methoden vorgeschlagen, die jeweils aus traditionellen Methoden auf der einen Seite und modernen maschinellen Lernalgorithmen auf der anderen Seite bestehen. Es wird gezeigt, dass diese kombinatorischen Ansätze sowohl ihre einzelnen methodischen Komponenten als auch andere bereits existierende Konkurrenzmethoden bei der Anwendung auf entsprechenden Datensätzen hinsichtlich statistischer Power und Accuracy übertreffen. Der Standardansatz für die Auswertung von GWAS basiert darauf, jede Position im Genom einzeln auf statistische Signifikanz ihrer Assoziation mit dem untersuchten Phänotyp zu testen. Um die Analyse zu verbessern, schlagen wir eine Kombination aus maschinellem Lernen und statistischem Testen vor, bei der Korrelationsstrukturen zwischen den untersuchten Einzelnukleotid-Polymorphismen (SNP) mathematisch kontrolliert berücksichtigt werden. Die zugrundeliegende Idee besteht darin, zunächst einen geeigneten Klassifizierungsalgorithmus zu trainieren, danach die Teilmenge aller SNPs auszuwählen, die für die Entscheidungen des Klassifizierers am relevantesten sind und letztendlich diese mit multiplen statistischen Hypothesentests auf signifikante Assoziationen zu untersuchen. Der erste im Rahmen dieser Dissertation entwickelte, zweistufige Algorithmus COMBI trainiert zunächst eine Support Vector Machine, um die Teilmenge der bedeutendsten Kandidaten-SNPs zu bestimmen und führt dann Hypothesentests mit einer entsprechenden Anpassung des Signifikanzlevels für diese SNPs durch. Mit der Anwendung von COMBI auf generierten Datensätzen sowie auf Daten aus einer WTCCC-Studie (2007) wird gezeigt, dass die neue Methode bessere Ergebnisse liefert als gewöhnliches multiples Testen sowie andere Konkurrenzmethoden. COMBI ermöglicht höhere statistische Power und Präzision als die untersuchten Alternativen und liefert weniger falsche (d.h. nicht replizierte) und mehr wahre (d.h. replizierte) Entdeckungen, wenn die jeweiligen Ergebnisse mit unabhängigen GWAS validiert werden. In den letzten Jahren wurde tiefes Lernen zu einer der führenden Methoden der Datenwissenschaften, die die Vorhersageleistungen im Vergleich zu herkömmlichen Ansätzen häufig erheblich verbessert. In jüngster Zeit hat sich zudem erklärbare künstliche Intelligenz (Explainable AI) zu einem neuartigen Forschungsgebiet entwickelt, das über die reine Vorhersageverbesserung hinausgeht und Wissen aus Deep-Learning-Methoden extrahiert, indem ihre Ergebnisse interpretiert und erklärt werden. Im Rahmen dieser Fortschritte entwickeln wir eine Erweiterung von COMBI, die auf tiefem Lernen und erklärbarer künstlicher Intelligenz basiert. Dieser zweite im Rahmen der Dissertation entwickelte, dreistufige Algorithmus DeepCOMBI trainiert zunächst ein neuronales Netzwerk für die Klassifizierung von Probanden in ihre jeweiligen Phänotypen. Anschließend werden die Entscheidungen der Klassifizierung mit Layerwise Relevance Propagation erklärt und die Ergebnisse verwendet, um die relevantesten SNPs zu identifizieren. Wie bei der ursprünglichen COMBI-Methode werden diese SNPs im dritten Schritt auf statistische Assoziation getestet. Auf generierten Datensätze und der bereits genannten WTCCC Studie von 2007 wird gezeigt, dass DeepCOMBI bessere Vorhersageleistungen erbringt als COMBI, gewöhnliches multiples Testen und andere Konkurrenzmethoden. Über die Verbesserung der Identifizierung von Assoziationen zwischen Phänotypen und Genotypen hinausgehend, tragen wir in dieser Dissertation dazu bei, besser zu verstehen, wie genetische Informationen in phänotypische Strukturen und biologische Funktionen übersetzt werden. Bei der Untersuchung der Umwandlung genetischer Informationen von DNA über mRNA zu Proteinen wird das Genom häufig im Kontext von Zelltypen interpretiert, indem untersucht wird, welche Gene in bestimmten Zellen aktiv sind. In diesem Kontext ist das Ziel von scRNA-Seq-Experimenten die Definition und Katalogisierung von Zelltypen basierend auf dem Transkriptom einzelner Zellen, was auf ein unüberwachtes Clustering-Problem hinausläuft. Beim Clustern von kleinen krankheits- oder gewebespezifischen Datensätzen ist die Identifizierung seltener Zelltypen häufig problematisch. Deshalb schlagen wir vor, herkömmliche Clustering-Algorithmen mit dem Konzept des Transfer Learnings zu kombinieren, um große und gut untersuchte Referenzdatensätze verwenden zu können. Der dritte im Rahmen der Dissertation vorgeschlagene, kombinatorische Ansatz modifiziert daher den Zieldatensatz, indem Informationen aus dem Referenzdatensatz über eine nichtnegative Matrixfaktorisierung einbezogen werden, bevor der modifizierte Datensatz mit einem Clustering-Algorithmus analysiert wird. Die Leistung der vorgeschlagenen Methode wird auf simulierten scRNA-Seq-Daten sowie auf öffentlich verfügbaren Datensätzen empirisch evaluiert. Schließlich präsentieren wir die Ergebnisse der Analyse eines kürzlich veröffentlichten kleinen Datensatzes und finden ein verbessertes Clustering beim Transfer von Informationen aus einem großen Referenzdatensatz. Zusammenfassend trägt diese Dissertation zu einem besseren Verständnis des Genoms und der Prozesse rund um seine Übersetzung in biologische Strukturen und Funktionen bei. Mit der Entwicklung dreier kombinatorischer Ansätze für die Analyse biologischer Datensätze aus traditionellen Methoden einerseits und modernen Algorithmen des maschinellen Lernens andererseits, wird gezeigt, dass auch hier “das Ganze mehr ist als die Summe seiner Teile” (sinngemäß Aristoteles, 4. Jh. v. Chr.).

Since the dawn of computer vision, semantic and geometric scene understanding has been an essential problem. It impacted early works and led to numerous real-world applications. A scene is a place where an agent can act with or navigate. Scene understanding is the process of analyzing the semantic information inside the static 2D image and the relationships between the scene contents. This dissertation presents the use of deep learning models and how they can be applied to recognize the surrounding environment given a single still image. The scene captured in an image contains different objects from various classes and they are looking in different directions. These objects appear in the image either small because they are far from the camera or large because they are very close to the camera. When the scene is complex, we find that some objects are occluded and it is hard sometimes to predict contextual information about the complete 3D object. Also, using a single view always leads to ill-posed problems as there is no enough information to reveal the ambiguity. So, to build a useful and complete understanding of a given scene, we have to answer the following questions: (1) what are the object classes that appear in the image? (2) from which direction do they look at the camera? (3) are the objects far or close to the camera? (4) if some object parts are hidden, how can the machine generate the 3D information of the object? More specifically, this dissertation approaches scene understanding by answering the above-mentioned questions. First, we present a multi-task CNN model that performs object classification and viewpoint estimation simultaneously. These two problems seem to have opposite representative features. For object classification, the features should be powerful so that they are orientation-invariant features. For viewpoint estimation, the features should preserve the orientation characteristic and the ability to describe the same object with different viewpoints. To this end, the proposed CNN has a shared network for both tasks and task-specific sub-networks. With this design, the mentioned problems can be solved using the same model without proposing parallel models and separating the tasks. Second, we address the problem of depth estimation from a single image. We formulate this problem as a regression task and propose two different CNN models to solve this task. The first model uses a series of stacked convolutional layers that generate the depth map from a single image. This model is a fully convolutional network that regresses the depth information for each pixel. However, the generated depth images are smaller than the input images and they are blurry. To overcome this drawback, we propose a second model that has encoder-decoder architecture. This model has an encoder part to extract useful features and a decoder part to reconstruct the image and generate the final depth image. The useful information extracted in the encoder part is transferred to the decoder part using the skip-connections. This information helps in generating more accurate depth images with sharper objects’ parts. For this task, we select a non-convex loss function to train the models and optimize the network weights. The no-convex loss function is robust against to the outliers and converges faster. In the last part of the dissertation, we propose a CNN model that reconstructs 3D point clouds of objects form a single image. Single-view reconstruction is a hard task as the 3D structure can be inferred accurately for specific object classes given restricted assumptions. The proposed model is a simple, yet powerful, that utilizes an initial point cloud of a sphere shape to generate the final point cloud. For this problem, we use a large-scale 3D dataset to train the model. Many images are rendered from each 3D model and used for training. To generate the ground-truth point clouds, we sample the points from the object’s surface. The proposed model takes a single image of an object and generates a point cloud that presents the desired object accurately. An initial sphere is used to spread the points evenly on the reconstructed object surface and prevents the points to be grouped in some parts of the objects.This dissertation demonstrates the leverage of using deep learning technology to give a comprehensive understanding of a scene using a single image only. We conclude this dissertation with a general discussion and propose several potential future research directions for better deep learning understanding and interpretation in solving computer vision tasks., Seit dem Beginn von Computer Vision war das semantische und geometrische Verständnis von Szenen ein essentielles Problem. Es beeinflusste erste Arbeiten und führte zu zahlreichen Anwendungen. Eine Szene beschreibt einen Ort in welchem ein Agent agiert oder navigiert. Daher ist das Verständnis einer Szene der Prozess semantische Informationen in einem statischen 2D Bild zu analysieren und die Beziehungen zwischen den einzelnen Inhalten in diesem Bild zu verstehen. Diese Dissertation präsentiert wie verschiedene Deep Learning Modelle genutzt und für ein Verständnis von Szenerien aus einem einzigen Bild eingesetzt werden können. Ein aufgenommenes Bild enthält verschiedene Objekte aus verschiedenen Klassen, die unterschiedlich ausgerichtet sind. Diese Objekte können entweder durch eine große Distanz zur Kamera sehr klein erscheinen oder groß, wenn sie sich direkt vor der Kamera befinden. Enthält eine Szene viele Objekte, verdecken einige Objekte andere und schränken somit die verfügbaren Informationen über das komplette 3D Objekt ein. Somit führt ein einzelnes Bild immer zu Problemen mit unzureichenden Informationen um Unklarheiten aufzulösen. Für das kreieren eines nützliches und komplettes Verständnis einer gegebenen Szene müssen folgende Fragen beantwortet werden: (1) Welche Objektklassen kommen in dem Bild vor? (2) Aus welcher Richtung betrachtet die Kamera die Szene? (3) Sind die Objekte nah an der Kamera oder weit weg? (4) Wenn Teile von Objekten verdeckt sind, wie kann eine Maschine diese 3D Informationen ergänzen? Genauer, diese Dissertation nähert sich dem Problem des Szenenverständnisses indem sie die oben genannten Fragen beantwortet. Als erstes wird ein multi-task CNN Modell vorgestellt, welches sowohl Objektklassifizierung als auch den Betrachtungsstandpunkt schätzt. Diese beiden Probleme scheinen gegensätzliche repräsentative Features zu benutzen. Für Objektklassifizierungen sollten die Features invariant zur Orientierung des Objektes sein. Für die Schätzung des Betrachtungsstandpunktes sollte jedoch die Orientierung erhalten bleiben. Zusätzlich sollte die Fähigkeit bestehen bleiben Objekte von verschiedenen Blickwinkeln aus zu beschreiben. Dennoch hat das vorgeschlagene Modell ein neuronales Netz, das für beide Probleme genutzt wird, und problemspezifische Subnetze. Mit diesem Design können beide Aufgaben mit dem gleichen Modell gelöst werden statt jedes Problem parallel und separat zu lösen. Als zweites wird die Problematik der Tiefenbestimmung aus einem Bild behandelt. Hierfür werden zwei verschiedene CNNs vorgeschlagen um das Problem als Regression zu lösen. Das erste benutzt eine Reihe von aufeinanderfolgenden Faltungen, die eine Tiefenkarte aus einem einzelnen Bild generiert. Dieses ist ein reines Faltungsnetz, welches die Tiefe für jeden Pixel per Regression bestimmt. Allerdings sind diese generierten Bilder kleiner als das Ursprüngliche und verwaschen. Daher wird ein weiteres Modell vorgeschlagen, welches einer encoder-decoder Architektur folgt. Der Encoder extrahiert nützliche Features aus denen der Decoder dann das ürsprüngliche Bild rekonstruiert und das fertige Tiefenbild generiert. Die nützlichen Informationen werden im Encoder extrahiert und durch sogenannte Skip-Connections an den Decoder weiter gegeben. Diese Informationen verbessern die Genauigkeit der Tiefenkarte und schärferen Objektkanten. Für das Trainieren und Optimieren der Netzwerkgewichte wurde eine nicht konvexe Verlustfunktion gewählt. Die nicht konvexe Verlustfunktion führt zu weniger Einfluss von Ausreißern und konvergiert schneller. Im letzten Teil der Dissertation wird ein CNN Modell eingeführt, das 3D Punktwolken aus einem einzigen Bild rekonstruiert. Rekonstruktionen durch einen einzigen Betrachtungswinkel ist ein schweres Problem, da die 3D Struktur für spezifische Objekte nur durch Annahmen genau geschlussfolgert werden kann. Das vorgeschlagene Modell is einfach und trotzdem wirkungsvoll. Es benutzt eine Punktwolke einer Kugel um daraus die Punktwolke des Objekts zu generieren. Der Trainingsprozess basiert auf einem großzügig angelegten 3D Datenset. Aus 3D Modellen wurden viele Bilder erzeugt, die als Trainingsgrundlage dienen. Als optimale Lösung wurden Punkte auf der Oberfläche der 3D Geometrien extrahiert. Das vorgeschlagene Modell nutzt daher ein einzelnes Bild um daraus eine Punktwolke zu generieren, welche das gewünschte Objekt akkurat visualisiert und beschreibt. Die ursprüngliche Kugel wird genutzt um die Punkte gleichmäßig auf dem rekonstruierten Objekt zu verteilen. Sie verhindert, dass sich Punkte an einigen Stellen des Objekts gruppieren. Es wird demonstriert welchen Wirkungsgrad Deep Learning Technologien haben können um ein umfassendes Verständnis von Szenen aus nur einem einzelnen Bild zu erlangen. Die Arbeit wird mit einer Diskussion beendet und schlägt verschiedene potentielle Forschungsrichtungen vor, die zu einem besseren Verständnis und Interpretation von Deep Learning in Computer Vision führen können.

A proactive context-aware system automatically adapts its user interface to the user's situational needs. This is achieved by continuously capturing the environmental properties, reasoning upon the context, and detecting situations where unsolicited adjustments are helpful or notifications informative. If the characteristics of those situations are well known in advance, their occurrence can be detected at runtime by the rule-based processing of raw sensor data. However, rule-based context reasoning methods determine the user's situation mostly based on present sensor signals instead of considering the situation to be likewise the product of the past context. This article introduces a graph-based situation modeling formalism for the specification of system-relevant environmental circumstances as context flow graphs. A directed cyclic graph represents thereby the distinct contextual characteristics a user's situation is made of and the temporal order in which these appear and disappear during the evolution of the situation. Complex situations for rule-based proactive context-aware systems can then be expressed at a high level of abstraction and without the need to understand the underlying sensor-related signal processing mechanisms. The technical feasibility is demonstrated by a prototypical distributed proactive context-aware middleware that, in addition, comes up with a web-based user interface for the interactive graphical and logical modeling of situations as context flow graphs.

Recommender systems recommend new movies, music, restaurants, etc. Typically, service providers organize such systems in a centralized way, holding all the data. Biases in the recommender systems are not transparent to the user and lock-in effects might make it inconvenient for the user to switch providers. In this paper, we present the concept, design, and implementation of MobRec, a mobile platform that decentralizes the data collection, data storage, and recommendation process. MobRec's architecture does not need any backend and solely consists of the users' smartphones, which already contain the users' preferences and ratings. Being in proximity in public places or public transportation, data is exchanged in a device-to-device manner, building local databases that can recommend new items. One of biggest challenges of such a system is the implementation of unobtrusive device-to-device data exchange on off-the-shelf Android devices and iPhones. MobRec facilitates such data exchange, building on Google Nearby Messages with Bluetooth Low Energy. We achieve the successful exchange of data within 3 to 4 minutes, making it suitable for the described scenario. We demonstrate the feasibility of decentralized recommender systems and provide blueprints for the development of seamless multi-platform device-to-device communication.

Traditionally, GPUs only had programmer-managed caches. The advent of hardware-managed caches accelerated the use of GPUs for general-purpose computing. However, as GPU caches are shared by thousands of threads, they are usually a victim of contention and can suffer from thrashing and high miss rate, in particular, for memory-divergent workloads. As data locality is crucial for performance, there have been several efforts focusing on exploiting data locality in GPUs. However, there is a lack of quantitative analysis of data locality and data reuse in GPUs. In this paper, we quantitatively study the data locality and its limits in GPUs. We observe that data locality is much higher than exploited by current GPUs. We show that, on the one hand, the low spatial utilization of cache lines justifies the use of demand-fetched caches. On the other hand, the much higher actual spatial utilization of cache lines shows the lost spatial locality and presents opportunities for further optimizing the cache design.

Cardiovascular diseases are the main cause of death worldwide, with sleep disordered breathing being a further aggravating factor. Respiratory illnesses are the third leading cause of death amongst the noncommunicable diseases. The current COVID-19 pandemic, however, also highlights the impact of communicable respiratory syndromes. In the clinical routine, prolonged postanesthetic respiratory instability worsens the patient outcome. Even though early and continuous, long-term cardiorespiratory monitoring has been proposed or even proven to be beneficial in several situations, implementations thereof are sparse. We employed our recently presented, multimodal patch stethoscope to estimate Einthoven electrocardiogram (ECG) Lead I and II from a single 55 mm ECG lead. Using the stethoscope and ECG subsystems, the pre-ejection period (PEP) and left ventricular ejection time (LVET) were estimated. ECG-derived respiration techniques were used in conjunction with a novel, phonocardiogram-derived respiration approach to extract respiratory parameters. Medical-grade references were the SOMNOmedics SOMNO HDTM and Osypka ICON-CoreTM. In a study including 10 healthy subjects, we analyzed the performances in the supine, lateral, and prone position. Einthoven I and II estimations yielded correlations exceeding 0.97. LVET and PEP estimation errors were 10% and 21%, respectively. Respiratory rates were estimated with mean absolute errors below 1.2 bpm, and the respiratory signal yielded a correlation of 0.66. We conclude that the estimation of ECG, PEP, LVET, and respiratory parameters is feasible using a wearable, multimodal acquisition device and encourage further research in multimodal signal fusion for respiratory signal estimation.

Blockchain technology has the potential to bring transparency and trust to a multitude of use cases. Our research demonstrates that the technology can reduce asymmetric information in markets by bridging trust gaps. The combination of blockchain and Internet of Things technology that automatically collects sensor data, provides a feasible, decentralized technological solution for such an inefficient “Market of Lemons” coined by nobel laureate Georg Akerlof. In this paper, we develop a system prototype to reduce mileage fraud on the used car markets. Our work demonstrates the feasibility of a trusted system of records for (vehicle) data such as mileage data using a distributed database based on the public Ethereum network and smart contracts. We have identified eight requirements that are fulfilled by the prototype and the functional logic and design of thesolution can be reproduced to any other application area characterized by a lack of trust between actors or by the absence of a trusted central authority. However, the developed prototype suffers from similar limitations and challenges as the technology itself. Low throughput causes limitations in scalability and transaction costs are unpredictable. Further development of the blockchain technology and considering more cost‐efficient consensus mechanisms will address these issues.

Today, we rely heavily upon Internet-connected devices, applications, and services. Such reliance makes it crucial for the underlying networks to be reliable and secure. However, network outages, bugs in network devices such as switches and routers, and security compromises of the critical network infrastructure happen and sometimes, incur losses in revenue. This makes network management and control critically important. Networking devices such as IP-based routers and ethernet-based switches are fixed-function devices that are vertically integrated, i.e., the control and data plane are bundled together. These devices can only be configured by network operators and, thus, notably lag behind in terms of providing useful and custom abstractions for network management and orchestration. This necessitated the need for new network management and control paradigms. Software-defined Networking (SDN) emerged as a paradigm that introduced programmability. SDN decouples the previously distributed control plane from the data plane and outsources the control to a logically centralized software SDN controller running on commodity hardware. SDN controller manages and controls several data plane devices (e.g., SDN switches) through a well-known interface known as OpenFlow while offering a multitude of opportunities regarding management and control through programmability of the control plane. However, the SDN switches remain as fixed-function devices that can only be configured via OpenFlow but not programmed. To enhance SDNs, Programming Protocol-independent Packet Processors (P4) language was introduced. P4 is a domain-specific language that allows data plane programmability by writing custom programs known as P4 programs that run on data plane switches (e.g., P4 switches). These programs dictate P4 switches how to process packets even after those switches are already deployed. At the network level, a P4 network, generally, comprises of an SDN controller that manages and controls underlying P4 switches. Together, SDN and P4 are complementary and can operate in conjugation with each other. Hereby, programmable networks emerged as a generic term for networks such as Software-defined Networks (SDNs) or P4 networks. However, as the switch (e.g., a P4 switch) and the networks (e.g., SDNs and P4 networks) get increasingly programmable, complex bugs and faults surface especially, during runtime under diverse workloads to pose unprecedented threats. To give an example of a single P4 switch, a programmer writes a P4 program defining packet processing and then deploys it on a P4 switch. However, programming errors or P4 switch-specific errors manifesting as bugs result in an abnormal switch behavior under active traffic. This necessitates the detection and elimination of bugs. Zooming out from a P4 switch to the network-level (e.g., SDNs and P4 networks), data plane faults such as software or hardware bugs, switch failures, misconfigurations of switches, and attacks are ubiquitous. Even worse, the network control plane or SDN controller remains unaware of the existence of such data plane faults which results in control-data plane inconsistency. This necessitates sound mechanisms that verify the actual network data plane behavior against the expected network control plane behavior during runtime. To address the aforementioned challenges, the goal of this dissertation is to develop runtime verification mechanisms for the following scenarios ranging from a single switch to the network-level, namely, (i) a P4 switch, (ii) SDNs, and (iii) P4 networks. We make the following contributions: (i) We present the design, implementation, and evaluation of P6, a system that detects, localizes, and patches bugs at runtime in a P4 program deployed on a P4 switch to perform end-to-end runtime verification. P6 leverages techniques such as machine learning and static analysis-guided fuzzing to detect, dynamic fault localization-based techniques to localize, and software libraries to patch the bugs in P4 programs. Furthermore, P6 detects P4 switch target platform-specific bugs. Our evaluation of the P6 prototype on a single P4 switch across different switch targets shows that it successfully detects, localizes, and patches software bugs existing in the publicly-available P4 application programs while outperforming even the advanced baseline approaches. (ii) We present the design, implementation, and evaluation of PAZZ, a system that leverages network coverage-guided fuzzing via Binary Decision Diagrams (BDDs) for detection and bloom-filters used by custom per-switch tagging for localization of control-data plane inconsistency in SDNs. Our evaluation of the PAZZ prototype shows that it can quickly detect and localize the control-data plane inconsistency between one or many source-destination pairs in various topologies and configurations of different scale while outperforming baseline approaches. (iii) We present the design, implementation, and evaluation of P4CONSIST, a system that leverages In-band Network Telemetry (INT)-based per-switch tagging in P4 switches, depth-frst search, and symbolic execution for the detection of control-data plane inconsistency in P4 networks. Our evaluation of the P4CONSIST prototype shows that it can rapidly detect the control-data plane inconsistency between one or many source-destination pairs in diverse topologies and configurations of different scale., Heutzutage verlassen wir uns vermehrt auf Geräte, Anwendungen und Services, die mit dem Internet verbunden sind. Diese Abhängigkeit erfordert es, dass das zugrundeliegende Netzwerk zuverlässig und sicher ist. Netzwerkausfälle, Fehler in Netzwerkgeräten wie Switches und Router, sowie Beeinträchtigungen der Sicherheit von kritischen Netzwerkinfrastrukturen passieren und bringen Umsatzverluste mit sich. Aus diesem Grund sind Netzwerkmanage- ment und -kontrolle unerlässlich. Netzwerkgeräte wie IP-basierte Router und Ethernet-basierte Switches sind traditionell als vertikal integrierte Geräte mit fest verbauter Funktionalität, d.h. gebündelter Kontroll- und Datenebene, bekannt. Solche Geräte können durch Netzbetreiber lediglich konfiguriert werden, weshalb sie deutliche Nachteile im Bereich der Abstraktion von Netzwerkmanagement und -orchestrierung haben. Hieraus entstand die Notwendigkeit neuer Paradigmen für Netzwerkkontrolle und -management. Software-Defined Networking (SDN) entstand als Paradigma, das Programmierbarkeit von Netzwerken ermöglicht. SDN trennt die zuvor verteilte Kontrollebene von der Datenebene, die nun in einem logisch-zentralisierten SDN Controller konsolidiert wird und als Software auf Standardhardware ausgeführt werden kann. Der SDN Controller managt und kontrolliert mehrere Geräte auf Datenebene (z.B. SDN Switches), über eine als OpenFlow bekannte Schnittstelle und bietet gleichzeitig, durch die Programmierbarkeit der Kontrollebene, eine Reihe von Möglichkeiten. Nichtsdestotrotz verbleiben SDN Switches als Geräte mit fest verbauter Funktionalität, die lediglich konfiguriert, nicht aber programmiert werden können. Um die Programmierbarkeit zu ermöglichen, wurde die Program- miersprache Protocol-independent Packet Processors (P4) entwickelt. P4 ist eine domänen- spezifische Sprache, welche die Programmierbarkeit der Datenebene, durch das Entwickeln von benutzerdefinierten Programmen (sogenannten P4 Programmen), die auf Switches der Datenebene (z.B. P4 Switches) ausgeführt werden, ermöglicht. Diese Programme geben vor wie Pakete verarbeitet werden sollen, selbst wenn die P4 Switches bereits im Einsatz sind. Auf Netzwerkebene besteht ein P4 Netzwerk aus einem SDN Controller, der die untergeordneten P4 Switches managt und kontrolliert. Insgesamt sind SDN und P4 komplementär und können in Verbindung miteinander eingesetzt werden. Als Resultat entwickelte sich der Begriff programmierbare Netzwerke als Sammelbegriff, sowohl für Software-defined Networks (SDNs), als auch P4 Netzwerke. Mit der erhöhten Programmierbarkeit von Switches (z.B. P4 Switch), sowie Netzwerken (z.B. SDNs und P4 Netzwerke), treten insbesondere zur Ausführung unterschiedlicher Arbeitslasten komplexe Bugs und Fehler zu Tage, die bis dato nie dagewesene Bedrohungen darstellen. Um ein Beispiel für einen einzelnen P4 Switch zu nennen: Ein Programmierer schreibt ein P4 Programm, das die Paketverarbeitung definiert und stellt dieses dann auf einem P4 Switch bereit. Programmierfehler oder P4 Switch-spezifische Fehler manifestieren sich jedoch als Bugs, die in einem ungewöhnlichen Switch-Verhalten unter unterschiedlichem Datenverkehr resultieren. Sowohl die Erkennung als auch die Beseitigung von Bugs erlangen daher größte Bedeutung. Wenn der Fokus von einem P4 Switch auf die Netzwerkebene (z.B. SDNs und P4 Netzwerke) verlagert wird, zeigt sich, dass Fehler auf der Datenebene wie Software- oder Hardwarebugs, Hardwarefehler, Fehlkonfigurationen und Angriffe allgegenwärtig sind. Schlimmer noch: die Netzwerk-Kontrollebene oder der SDN Controller sind im Unklaren über die Existenz solcher Fehler auf Datenebene, was zu Inkonsistenzen zwischen Kontroll- und Datenebene führt während der Datenverkehr über das Netzwerk fließt. Dies erfordert solide Mechanismen, die das tatsächliche Verhalten der Datenebene mit dem erwarteten Verhalten der Kontrollebene während der Laufzeit vergleichen, um erforderliche Korrekturmaßnahmen einleiten zu können. Um die zuvor beschriebenen Herausforderungen zu adressieren, ist das Ziel dieser Dissertation die Entwicklung von Mechanismen zur Verifikation während der Laufzeit für die folgen den Szenarien, die von einem einzelnen Switch bis zur Netzwerkebene reichen, (i) einem P4 Switch, (ii) SDNs und (iii) P4 Netzwerke. Wir leisten folgende Beiträge: (i) Wir präsentieren das Design, die Implementierung und Evaluation von P6, einem System, welches Fehler in einem P4 Programm, ausgeführt auf einem P4 Switch, automatisch zur Laufzeit erkennen, lokalisieren und beheben kann, um Ende-zu-Ende Laufzeit Verifikation zur ermöglichen. P6 nutzt hierfür Techniken wie durch maschinelles Lernen und statische Analyse geleitetes Fuzzing zur Erkennung, dynamische Lokalisierungsmechanismen zur Lokalisierung und Softwarebibliotheken zur Behebung von Fehlern in P4 Programmen. Außerdem kann P6 plat- tformspezifische Fehler von P4 Switches erkennen. Unsere Evaluation des P6 Prototypen auf einem einzelnen P4 Switch mit einer Reihe verschiedener Zielplattformen zeigt, dass P6 verschiedenste existierende Fehler in öffentlich verfügbaren P4 Programmen, erfolgreich erkennen, lokalisieren und beheben kann und dabei sogar fortschrittliche Basisansätze übertrifft. (ii) Wir präsentieren das Design, die Implementierung und Evaluation von PAZZ, einem System zur Erkennung und Lokalisierung von Inkonsistenzen zwischen der Kontroll- und Datenebenen in SDNs, welches auf dem Netzwerkabdeckung basiertem Fuzzing mit Binary Decision Diagrams (BDDs) und Bloom Filtern zur Lokalisierung von Fehlern mittels benutzerdefinierter Markierungen von Paketen beruht. Unsere Evaluation des PAZZ Prototypen zeigt, dass er in der Lage ist, Inkonsistenzen der Kontroll- und Datenebene zwischen einem oder mehreren Quelle-Ziel Paaren in verschiedenen Topologien und Konfigurationen unter- schiedlicher Größenordnungen, schnell zu erkennen und zu lokalisieren, sowie die Basisansätze zu übertreffen. (iii) Wir präsentieren das Design, die Implementierung und Evaluation von P4CONSIST, einem System zur Erkennung von Inkonsistenzen zwischen der Kontroll- und Datenebene mithilfe von per-Switch Tagging basierend auf In-band Network Telemetry (INT) für P4 Switches, Tiefensuche und symbolischer Ausführung. Unsere Evaluation des P4CONSIST Prototypen zeigt, dass er in kürzester Zeit in der Lage ist, Inkonsistenzen zwischen der Kontroll- und Datenebene und einem oder mehrerer Quelle-Ziel Paaren in diversen Topologien und Konfigurationen unterschiedlicher Größenordnungen zu erkennen.