Detailansicht
Engineering efficient algorithms for the analysis of dynamic data
Lara Chiara Ost
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doktoratsstudium der technischen Wissenschaften Informatik
Betreuer*innen
Monika Henzinger ,
Kathrin Hanauer
DOI
10.25365/thesis.77684
URN
urn:nbn:at:at-ubw:1-30980.71917.753554-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Die Analyse von großen Datensätzen ist auf vielen Gebieten von zentraler Bedeutung, wobei sich die Anforderungen an die Art der Analyse stark unterscheiden können. Ein gemeinsamer Aspekt über Anwendungen hinweg ist die Dynamik der Datensätze: neue Daten kommen hinzu und obsolete Daten werden entfernt. Beispiele finden sich in Graphen, die soziale Netzwerke repräsentieren, wo Änderungen in den Interaktionen der Teilnehmer Kanten erscheinen und verschwinden lassen, oder auch in Kommunikationsnetzwerken, deren gewichtete Kanten den fluktuierenden Kommunikationsbedarf modellieren. Allgemein kann jeder Datenstrom als dynamisch angesehen werden, zum Beispiel finanzielle Daten, physiologische Daten und seismische Daten. Diese Dissertation behandelt Algorithmen zur Analyse von dynamischen Daten in unterschiedlichen Anwendungsgebieten: in topologischer Datenanalyse, privater Datenanalyse und rekonfigurierbaren Netzwerken. Persistente Homologie ist ein Schlüsselkonzept in topologischer Datenanalyse, das topologische Eigenschaften auf vielen Skalen beschreibt. Wir führen eine Datenstruktur zur Berechnung der persistenten Homologie von Zeitreihen ein, die auf einer neuartigen Baum-ähnlichen Struktur, dem Bananenbaum, basiert. Diese Datenstruktur unterstützt lokale Operationen, wie Änderung eines Wertes und Einfügen eines Punktes, und topologische Operationen, die Zeitreihen trennen oder zusammenfügen. Die Laufzeit für diese Operationen skaliert linear mit den Änderungen in der Ausgabe. Eine experimentelle Studie auf synthetischen und realen Zeitreihen zeigt, dass Bananenbäume auf symmetrischen Irrfahrten und quasi-periodischen Reihen Änderungen an der Eingabe schneller verarbeiten als der bisher schnellste Algorithmus. Die Ergebnisse zeigen auch Zusammenhänge zwischen der Performanz und der Struktur der Bananenbäume auf. Bananenbäume auf realen Zeitreihen ähneln denen auf symmetrischen Irrfahrten in ihren strukturellen Eigenschaften, was eine gute Anwendbarkeit nahelegt. Private Datenanalyse zielt darauf ab, Analysen von Datensätzen zu erzeugen und gleichzeitig sensible Daten zu schützen. Differential Privacy ist ein Ansatz, der solche Analysen ermöglicht. Wir betrachten Differential Privacy für Graphprobleme im Kontext der Continual Observation; das heißt, für dynamische Graphen. Wir beschreiben ε-differentiell private Algorithmen auf Event-Level für die Probleme Zählen von Subgraphen, minimaler Spannbaum, kleinster Schnitt, maximales Matching und dichtester Subgraph auf partiell dynamischen Eingaben. Dies sind die ersten differentiell privaten Algorithmen für solche Probleme mit additivem Fehler der poly-logarithmisch mit T, der Länge der Eingabe, skaliert. Schließlich zeigen wir, dass der additive Fehler von Algorithmen auf User-Level für viele Graphprobleme linear im maximalen Funktionswert ist. Rekonfigurierbare Netzwerke in Datencentern ermöglichen direkte Verbindungen zwischen Racks, angepasst an den Kommunikationsbedarf. Diese Verbindungen formen eine Menge an k disjunkten Matchings. Wir präsentieren dynamische Algorithmen, die diese disjunkten Matchings berechnen und dabei die kommunizierte Datenmenge maximieren. Wir vergleichen sieben (batch-)dynamische Algorithmen mit statischen in ausführlichen Experimenten auf 176 synthetischen und 39 realen Netzwerk-Traces. Unsere Algorithmen verbessern die Laufzeit deutlich und reduzieren die nötigen Änderungen an der Netzwerkkonfiguration, ohne dabei an Lösungsqualität zu verlieren.
Abstract
(Englisch)
The analysis of large data sets is central to numerous fields, each posing different requirements on the kinds of analyses that are performed. One aspect many areas share is the dynamic nature of data: data sets change as new data arrives and outdated data is removed. Consider, for example, graphs representing social networks, where edges appear and disappear as people's interactions evolve, or communication graphs, where weighted edges represent changing communication demand. Any kind of continuous data stream can also be considered dynamic data. Examples are financial data, physiological data such as in electrocardiography, and seismic data. We study algorithms for the analysis of dynamic data in different application areas, namely in topological data analysis, private data analysis and reconfigurable networks. Persistent homology is a key concept in topological data analysis, describing topological features across multiple scales. We introduce a data structure for maintaining the persistent homology of time series data, based on a novel tree-like representation called the banana tree. It supports local operations such as changing the value of an item or inserting a new item, and topological operations, i.e., cutting and concatenating, which each can be performed in time linear in the number of changes to the output. We assess its performance and properties in an experimental study on a variety of synthetic and real-world time series. The results indicate that banana trees outperform the state-of-the-art static algorithms on unbiased random and quasi-periodic data. They also reveal connections between the performance and structure of the banana trees. Our results suggest practical utility of banana trees on real-world data sets, as they share structural properties with random walks. Private data analysis aims to publish analyses of a data set while protecting the sensitive data of users who contribute their information. Differential privacy is a framework that offers such protections. We study differential privacy for graph problems under continual observation, i.e., for dynamic graphs. We present event-level ε-differentially private algorithms for subgraph counting problems, minimum spanning tree, minimum cut, maximum matching and densest subgraph on partially dynamic inputs. These are the first differentially private algorithms for such problems with additive error poly-logarithmic in the input length T. Finally, we show that on user-level with fully dynamic inputs the additive error must be linear in the value of the output's solution range for a wide variety of graph problems. Reconfigurable networks in datacenters provide direct connections between racks, adapted to the communication demand, which form a set of k edge-disjoint matchings. We propose dynamic algorithms to efficiently maintain these disjoint matchings while maximizing the demand served. We present seven (batch-)dynamic algorithms and compare them to static ones in extensive experiments on 176 synthetic and 39 real-world network traces. Our dynamic algorithms significantly improve the running time and reduce the number of changes to the network's configuration, while retaining solution quality.
Schlagwörter
Schlagwörter
(Deutsch)
dynamische Algorithmen Datenanalyse Persistente Homologie Differential Privacy Graphalgorithmen
Schlagwörter
(Englisch)
dynamic algorithms data analysis persistent homology differential privacy graph algorithms
Autor*innen
Lara Chiara Ost 
Haupttitel (Englisch)
Engineering efficient algorithms for the analysis of dynamic data
Publikationsjahr
2024
Umfangsangabe
ix, 179 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Gramoz Goranci ,
Henning Meyerhenke
Klassifikation
54 Informatik > 54.10 Theoretische Informatik
AC Nummer
AC17430798
Utheses ID
73744
Studienkennzahl
UA | 786 | 880 | |