TY - THES A1 - Dreseler, Markus T1 - Automatic tiering for in-memory database systems N2 - A decade ago, it became feasible to store multi-terabyte databases in main memory. These in-memory databases (IMDBs) profit from DRAM's low latency and high throughput as well as from the removal of costly abstractions used in disk-based systems, such as the buffer cache. However, as the DRAM technology approaches physical limits, scaling these databases becomes difficult. Non-volatile memory (NVM) addresses this challenge. This new type of memory is persistent, has more capacity than DRAM (4x), and does not suffer from its density-inhibiting limitations. Yet, as NVM has a higher latency (5-15x) and a lower throughput (0.35x), it cannot fully replace DRAM. IMDBs thus need to navigate the trade-off between the two memory tiers. We present a solution to this optimization problem. Leveraging information about access frequencies and patterns, our solution utilizes NVM's additional capacity while minimizing the associated access costs. Unlike buffer cache-based implementations, our tiering abstraction does not add any costs when reading data from DRAM. As such, it can act as a drop-in replacement for existing IMDBs. Our contributions are as follows: (1) As the foundation for our research, we present Hyrise, an open-source, columnar IMDB that we re-engineered and re-wrote from scratch. Hyrise enables realistic end-to-end benchmarks of SQL workloads and offers query performance which is competitive with other research and commercial systems. At the same time, Hyrise is easy to understand and modify as repeatedly demonstrated by its uses in research and teaching. (2) We present a novel memory management framework for different memory and storage tiers. By encapsulating the allocation and access methods of these tiers, we enable existing data structures to be stored on different tiers with no modifications to their implementation. Besides DRAM and NVM, we also support and evaluate SSDs and have made provisions for upcoming technologies such as disaggregated memory. (3) To identify the parts of the data that can be moved to (s)lower tiers with little performance impact, we present a tracking method that identifies access skew both in the row and column dimensions and that detects patterns within consecutive accesses. Unlike existing methods that have substantial associated costs, our access counters exhibit no identifiable overhead in standard benchmarks despite their increased accuracy. (4) Finally, we introduce a tiering algorithm that optimizes the data placement for a given memory budget. In the TPC-H benchmark, this allows us to move 90% of the data to NVM while the throughput is reduced by only 10.8% and the query latency is increased by 11.6%. With this, we outperform approaches that ignore the workload's access skew and access patterns and increase the query latency by 20% or more. Individually, our contributions provide novel approaches to current challenges in systems engineering and database research. Combining them allows IMDBs to scale past the limits of DRAM while continuing to profit from the benefits of in-memory computing. N2 - Seit etwa einem Jahrzehnt können Datenbanken mit einer Größe von mehreren Terabytes im Hauptspeicher abgelegt werden. Diese Hauptspeicherdatenbanken (In-Memory Databases) profitieren einerseits von der niedrigen Latenz und dem hohen Durchsatz von DRAM und andererseits vom Fehlen teurer Abstraktionsschichten, wie dem Buffer Cache, welcher in Festplatten-basierten Datenbanksystemen von Nöten war. Dadurch, dass die Entwicklung der DRAM-Technologie mehr und mehr auf physikalische Grenzen stößt, wird es jedoch zunehmend schwierig, Hauptspeicherdatenbanken zu skalieren. Non-volatile Memory (NVM) adressiert diese Herausforderung. Dieser neue Speichertyp ist persistent, hat eine um einen Faktor 4 höhere Kapazität als DRAM und leidet nicht unter den Einschränkungen, welche die Erhöhung der Speicherdichte von DRAM limitieren. Da NVM jedoch eine höhere Latenz (5-15x) und einen niedrigeren Durchsatz (0.35x) aufweist als DRAM, kann es DRAM noch nicht vollständig ersetzen. Bei der Entwicklung von Hauptspeicherdatenbanken muss daher der Zielkonflikt zwischen den beiden Speichertypen ausbalanciert werden. Die vorliegende Arbeit präsentiert eine Lösung für dieses Optimierungsproblem. Indem wir Informationen zu Zugriffshäufigkeiten und -mustern auswerten, können wir die zusätzliche Kapazität von NVM ausnutzen und gleichzeitig die mit NVM verbundene Erhöhung von Zugriffskosten minimieren. Anders als bei bestehenden Ansätzen, welche auf einen Buffer Cache aufsetzen, bleiben bei unserer Ansatz die Kosten von Zugriffen auf DRAM unverändert. Dadurch kann unsere Lösung als unmittelbarer Ersatz für existierende Hauptspeicherdatenbanken genutzt werden. Unsere Arbeit leistet hierfür die folgenden Beiträge: (1) Als Grundlage für unsere Forschung präsentieren wir Hyrise, eine quelloffene, spaltenorientierte Hauptspeicherdatenbank, welche wir von Grund auf neu entwickelt haben. Hyrise ermöglicht realistische End-to-End Benchmarks von SQL Workloads und weist dabei eine Performance auf, welche mit anderen Datenbanksystemen aus Industrie und Forschung vergleichbar ist. Hierbei ist Hyrise leicht zu verstehen und modifizieren. Dies wurde durch den wiederholten Einsatz in Forschung und Lehre demonstriert. (2) Wir präsentieren ein neuartiges Speicherverwaltungs-Framework, welches verschiedene Speicherebenen (Tiers) unterstützt. Indem wir die Allokations- und Zugriffsmethoden dieser Speicherebenen kapseln, ermöglichen wir es, bestehende Datenstrukturen auf diese Ebenen aufzuteilen ohne ihre Implementierung anpassen zu müssen. Neben DRAM und NVM unterstützt unser Ansatz SSDs und ist auf zukünftige Technologien wie Disaggregated Memory vorbereitet. (3) Um jene Teile der Daten zu identifizieren, welche auf langsamere Ebenen verschoben werden können, ohne dass die Performance des Systems als Ganzes negativ beeinträchtigt wird, stellen wir mit unseren Access Countern eine Tracking-Methode vor, welche ungleich verteilte Zugriffshäufigkeiten sowohl in der Zeilen- als auch in der Spaltendimension erkennt. Ebenfalls erkennt die Tracking-Methode Zugriffsmuster in aufeinanderfolgenden Zugriffsoperationen. Trotz ihrer hohen Genauigkeit weisen unsere Access Counter keine messbaren Mehrkosten auf. Dies unterscheidet sie von bestehenden Ansätzen, welche ungleichverteilte Zugriffsmuster weniger gut erkennen, gleichzeitig aber Mehrkosten von 20% verursachen. (4) Abschließend stellen wir einen Tiering-Algorithmus vor, welcher die Verteilung von Daten auf die verschiedenen Speicherebenen optimiert. Am Beispiel des TPC-H-Benchmarks zeigen wir, wie 90% der Daten auf NVM verschoben werden können, wobei der Durchsatz nur um 10.8% reduziert und die durchschnittliche Antwortzeit um 11.6% erhöht wird. Damit übertreffen wir Ansätze, welche Ungleichverteilungen in den Zugriffshäufigkeiten und -mustern ignorieren. Einzeln betrachtet stellen unsere Beiträge neue Herangehensweisen für aktuelle Herausforderungen in der systemnahen Entwicklung und der Datenbankforschung dar. In ihrem Zusammenspiel ermöglichen sie es, Hauptspeicherdatenbanken über die Grenzen von DRAM hinaus zu skalieren und dabei weiterhin von den Vorteilen des In-Memory Computings zu profitieren. T2 - Automatisches Tiering für Hauptspeicherdatenbanken KW - dbms KW - imdb KW - tiering KW - nvm KW - hyrise KW - scm KW - dbms KW - imdb KW - mmdb KW - Datenbanken KW - tiering KW - nvm KW - hyrise KW - scm Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-558253 ER - TY - THES A1 - Plauth, Max Frederik T1 - Improving the Accessibility of Heterogeneous System Resources for Application Developers using Programming Abstractions T1 - Verbesserung der Zugänglichkeit heterogener Systemressourcen für Anwendungsentwickler durch Programmierabstraktionen N2 - The heterogeneity of today's state-of-the-art computer architectures is confronting application developers with an immense degree of complexity which results from two major challenges. First, developers need to acquire profound knowledge about the programming models or the interaction models associated with each type of heterogeneous system resource to make efficient use thereof. Second, developers must take into account that heterogeneous system resources always need to exchange data with each other in order to work on a problem together. However, this data exchange is always associated with a certain amount of overhead, which is why the amounts of data exchanged should be kept as low as possible. This thesis proposes three programming abstractions to lessen the burdens imposed by these major challenges with the goal of making heterogeneous system resources accessible to a wider range of application developers. The lib842 compression library provides the first method for accessing the compression and decompression facilities of the NX-842 on-chip compression accelerator available in IBM Power CPUs from user space applications running on Linux. Addressing application development of scale-out GPU workloads, the CloudCL framework makes the resources of GPU clusters more accessible by hiding many aspects of distributed computing while enabling application developers to focus on the aspects of the data parallel programming model associated with GPUs. Furthermore, CloudCL is augmented with transparent data compression facilities based on the lib842 library in order to improve the efficiency of data transfers among cluster nodes. The improved data transfer efficiency provided by the integration of transparent data compression yields performance improvements ranging between 1.11x and 2.07x across four data-intensive scale-out GPU workloads. To investigate the impact of programming abstractions for data placement in NUMA systems, a comprehensive evaluation of the PGASUS framework for NUMA-aware C++ application development is conducted. On a wide range of test systems, the evaluation demonstrates that PGASUS does not only improve the developer experience across all workloads, but that it is also capable of outperforming NUMA-agnostic implementations with average performance improvements of 1.56x. Based on these programming abstractions, this thesis demonstrates that by providing a sufficient degree of abstraction, the accessibility of heterogeneous system resources can be improved for application developers without occluding performance-critical properties of the underlying hardware. N2 - Die Heterogenität heutiger Rechnerarchitekturen konfrontiert Anwendungsentwickler mit einem immensen Maß an Komplexität, welches sich aus zwei großen Herausforderungen ergibt. Erstens müssen Entwickler fundierte Kenntnisse über die Programmiermodelle oder Interaktionsmodelle verfügen, welche eine Voraussetzung sind um die jeweiligen heterogenen Systemressourcen effizient nutzen zu können. Zweitens müssen Entwickler berücksichtigen, dass heterogene Systemressourcen immer auch Daten untereinander austauschen müssen, um ein Problem gemeinsam zu bearbeiten. Dieser Datenaustausch ist aber auch immer mit einem gewissen Mehraufwand verbunden, weshalb die ausgetauschten Datenmengen so gering wie möglich gehalten werden sollten. Diese Dissertation schlägt drei Programmierabstraktionen vor und ermöglicht es so, Anwendungsentwickler bei der Bewältigung dieser Herausforderungen zu entlasten, so dass heterogene Systemressourcen für eine größere Anzahl von Anwendungsentwicklern zugänglich werden. Die lib842-Kompressionsbibliothek bietet Anwendungen erstmals die Möglichkeit, die Kompressions- und Dekompressionsfunktionen des in IBM Power Prozessoren integrierten NX-842 Kompressionsbeschleunigers unter Linux zu verwenden. Das CloudCL-Framework richtet sich an die Entwicklung von GPU-beschleunigten, verteilten Anwendungen und macht die Ressourcen von GPU-Clustern vereinfacht nutzbar, indem es viele Aspekte des verteilten Rechnens ausblendet und es so Anwendungsentwicklern ermöglicht, sich auf die Aspekte des auf GPUs üblichen, datenparallelen Programmiermodells zu konzentrieren. CloudCL wurde weitergehend über transparente Datenkompressionsfunktionalität auf Basis der lib842 Programmbibliothek erweitert, um die Datenübertragungseffizienz zwischen Clusterknoten zu verbessern. Die verbesserte Datentransfereffizienz führt zu Leistungsverbesserungen zwischen 1, 11-fach und 2, 07- fach bei der Verwendung von vier datenintesiven, verteilten, und GPU-beschleunigten Arbeitslasten. Um die Auswirkungen von Programmierabstraktionen auf die Datenplatzierung in NUMA-Systemen zu untersuchen, wird eine umfassende Evaluierung des PGASUSFrameworks für NUMA-gewahre C++-Anwendungsentwicklung durchgeführt. Unter Verwendung einer breiten Palette von Testsystemen zeigt die Evaluierung, dass PGASUS nicht nur die Entwicklung von NUMA-gewahren Anwendungen erleichtert, sondern auch in der Lage ist, die Leistung von NUMA-agnostischen Implementierungen im Mittel um 1, 56× zu übertreffen. Auf der Grundlage dieser Programmierabstraktionen zeigt diese Dissertation, dass heterogene Systemressourcen durch die Bereitstellung angemessener Abstraktionsmechanismen einfacher von Anwendungsentwicklern erschlossen werden können, ohne dass leistungsrelevante Eigenschaften der zugrunde liegenden Hardware verdeckt werden. KW - heterogeneous computing KW - programming abstraction KW - heterogenes Rechnen KW - Programmierabstraktionen Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-558118 ER - TY - THES A1 - Discher, Sören T1 - Real-Time Rendering Techniques for Massive 3D Point Clouds T1 - Echtzeit-Rendering-Techniken für massive 3D-Punktwolken N2 - Today, point clouds are among the most important categories of spatial data, as they constitute digital 3D models of the as-is reality that can be created at unprecedented speed and precision. However, their unique properties, i.e., lack of structure, order, or connectivity information, necessitate specialized data structures and algorithms to leverage their full precision. In particular, this holds true for the interactive visualization of point clouds, which requires to balance hardware limitations regarding GPU memory and bandwidth against a naturally high susceptibility to visual artifacts. This thesis focuses on concepts, techniques, and implementations of robust, scalable, and portable 3D visualization systems for massive point clouds. To that end, a number of rendering, visualization, and interaction techniques are introduced, that extend several basic strategies to decouple rendering efforts and data management: First, a novel visualization technique that facilitates context-aware filtering, highlighting, and interaction within point cloud depictions. Second, hardware-specific optimization techniques that improve rendering performance and image quality in an increasingly diversified hardware landscape. Third, natural and artificial locomotion techniques for nausea-free exploration in the context of state-of-the-art virtual reality devices. Fourth, a framework for web-based rendering that enables collaborative exploration of point clouds across device ecosystems and facilitates the integration into established workflows and software systems. In cooperation with partners from industry and academia, the practicability and robustness of the presented techniques are showcased via several case studies using representative application scenarios and point cloud data sets. In summary, the work shows that the interactive visualization of point clouds can be implemented by a multi-tier software architecture with a number of domain-independent, generic system components that rely on optimization strategies specific to large point clouds. It demonstrates the feasibility of interactive, scalable point cloud visualization as a key component for distributed IT solutions that operate with spatial digital twins, providing arguments in favor of using point clouds as a universal type of spatial base data usable directly for visualization purposes. N2 - Punktwolken gehören heute zu den wichtigsten Kategorien räumlicher Daten, da sie digitale 3D-Modelle der Ist-Realität darstellen, die mit beispielloser Geschwindigkeit und Präzision erstellt werden können. Ihre einzigartigen Eigenschaften, d.h. das Fehlen von Struktur-, Ordnungs- oder Konnektivitätsinformationen, erfordern jedoch spezielle Datenstrukturen und Algorithmen, um ihre volle Präzision zu nutzen. Insbesondere gilt dies für die interaktive Visualisierung von Punktwolken, die es erfordert, Hardwarebeschränkungen in Bezug auf GPU-Speicher und -Bandbreite mit einer naturgemäß hohen Anfälligkeit für visuelle Artefakte in Einklang zu bringen. Diese Arbeit konzentriert sich auf Konzepte, Techniken und Implementierungen von robusten, skalierbaren und portablen 3D-Visualisierungssystemen für massive Punktwolken. Zu diesem Zweck wird eine Reihe von Rendering-, Visualisierungs- und Interaktionstechniken vorgestellt, die mehrere grundlegende Strategien zur Entkopplung von Rendering-Aufwand und Datenmanagement erweitern: Erstens eine neuartige Visualisierungstechnik, die kontextabhängiges Filtern, Hervorheben und Interaktion innerhalb von Punktwolkendarstellungen erleichtert. Zweitens hardwarespezifische Optimierungstechniken, welche die Rendering-Leistung und die Bildqualität in einer immer vielfältigeren Hardware-Landschaft verbessern. Drittens natürliche und künstliche Fortbewegungstechniken für eine übelkeitsfreie Erkundung im Kontext moderner Virtual-Reality-Geräte. Viertens ein Framework für webbasiertes Rendering, das die kollaborative Erkundung von Punktwolken über Geräteökosysteme hinweg ermöglicht und die Integration in etablierte Workflows und Softwaresysteme erleichtert. In Zusammenarbeit mit Partnern aus Industrie und Wissenschaft wird die Praxistauglichkeit und Robustheit der vorgestellten Techniken anhand mehrerer Fallstudien aufgezeigt, die repräsentative Anwendungsszenarien und Punktwolkendatensätze verwenden. Zusammenfassend zeigt die Arbeit, dass die interaktive Visualisierung von Punktwolken durch eine mehrstufige Softwarearchitektur mit einer Reihe von domänenunabhängigen, generischen Systemkomponenten realisiert werden kann, die auf Optimierungsstrategien beruhen, die speziell für große Punktwolken geeignet sind. Sie demonstriert die Machbarkeit einer interaktiven, skalierbaren Punktwolkenvisualisierung als Schlüsselkomponente für verteilte IT-Lösungen, die mit räumlichen digitalen Zwillingen arbeiten, und liefert Argumente für die Verwendung von Punktwolken als universelle Art von räumlichen Basisdaten, die direkt für Visualisierungszwecke verwendet werden können. KW - 3D Point Clouds KW - Real-Time Rendering KW - Visualization KW - Virtual Reality KW - Web-Based Rendering KW - 3D-Punktwolken KW - Echtzeit-Rendering KW - Visualisierung KW - Virtuelle Realität KW - Webbasiertes Rendering Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-601641 ER - TY - THES A1 - Melnichenko, Anna T1 - Selfish Creation of Realistic Networks N2 - Complex networks like the Internet or social networks are fundamental parts of our everyday lives. It is essential to understand their structural properties and how these networks are formed. A game-theoretic approach to network design problems has become of high interest in the last decades. The reason is that many real-world networks are the outcomes of decentralized strategic behavior of independent agents without central coordination. Fabrikant, Luthra, Maneva, Papadimitriou, and Schenker proposed a game-theoretic model aiming to explain the formation of the Internet-like networks. In this model, called the Network Creation Game, agents are associated with nodes of a network. Each agent seeks to maximize her centrality by establishing costly connections to other agents. The model is relatively simple but shows a high potential in modeling complex real-world networks. In this thesis, we contribute to the line of research on variants of the Network Creation Games. Inspired by real-world networks, we propose and analyze several novel network creation models. We aim to understand the impact of certain realistic modeling assumptions on the structure of the created networks and the involved agents’ behavior. The first natural additional objective that we consider is the network’s robustness. We consider a game where the agents seek to maximize their centrality and, at the same time, the stability of the created network against random edge failure. Our second point of interest is a model that incorporates an underlying geometry. We consider a network creation model where the agents correspond to points in some underlying space and where edge lengths are equal to the distances between the endpoints in that space. The geometric setting captures many physical real-world networks like transport networks and fiber-optic communication networks. We focus on the formation of social networks and consider two models that incorporate particular realistic behavior observed in real-world networks. In the first model, we embed the anti-preferential attachment link formation. Namely, we assume that the cost of the connection is proportional to the popularity of the targeted agent. Our second model is based on the observation that the probability of two persons to connect is inversely proportional to the length of their shortest chain of mutual acquaintances. For each of the four models above, we provide a complete game-theoretical analysis. In particular, we focus on distinctive structural properties of the equilibria, the hardness of computing a best response, the quality of equilibria in comparison to the centrally designed socially optimal networks. We also analyze the game dynamics, i.e., the process of sequential strategic improvements by the agents, and analyze the convergence to an equilibrium state and its properties. N2 - Komplexe Netzwerke, wie das Internet oder soziale Netzwerke, sind fundamentale Bestandteile unseres Alltags. Deshalb ist es wichtig, ihre strukturellen Eigenschaften zu verstehen und zu wissen, wie sie gebildet werden. Um dies zu erreichen, wurden in den letzten Jahrzehnten spieltheoretische Ansätze für Netzwerkdesignprobleme populär. Der Grund dafür ist, dass viele reale Netzwerke das Ergebnis von dezentralem strategischem Verhalten unabhängiger Agenten ohne zentrale Koordination sind. Fabrikant, Luthra, Maneva, Papadimitriou und Schenker haben ein solches spieltheoretisches Modell vorgeschlagen, um die Entstehung von internetähnlichen Netzwerken zu erklären. In diesem Modell, dem sogenannten Network Creation Game, repräsentieren die Agenten die Knoten eines Netzwerks. Jeder Agent versucht, durch den Kauf von Verbindungen zu anderen Agenten seine Zentralität im erzeugten Netzwerk zu maximieren. Dieses Modell ist relativ einfach, aber es hat ein großes Potenzial, reale Netzwerke modellieren zu können. In der vorliegenden Arbeit tragen wir zur aktuellen Forschungsrichtung, die sich der Untersuchung von Varianten der Network Creation Games widmet, bei. Inspiriert von realen Netzwerken, schlagen wir verschiedene neuartige Netzwerkbildungsmodelle vor und analysieren diese. Wir wollen hierbei die Auswirkungen bestimmter realistischer Modellierungsannahmen auf die Struktur der erstellten Netzwerke und das Verhalten der beteiligten Agenten verstehen. Die erste natürliche zusätzliche Modellierungsannahme, die wir betrachten, ist ein Fokus auf die Robustheit des erzeugten Netzwerks. In diesem Modell haben die Agenten das Ziel, ihre Zentralität zu maximieren und gleichzeitig das erstellte Netzwerk robust gegenüber zufällige Verbindungsausfälle zu machen. Das zweite neue Modell, das wir hier betrachten, bezieht eine zu Grunde liegende Geometrie mit ein. Hierbei entspricht jeder Agent einem Punkt in einem gegebenen Raum und die Länge einer Netzwerkverbindung entspricht der Distanz zwischen den jeweiligen Endpunkten in diesem Raum. Diese geometrische Variante erlaubt die Modellierung vieler realer physischer Netzwerke, wie z.B. Transportnetzwerke und Glasfaserkommunikationsnetzwerke. Des Weiteren fokussieren wir uns auf die Bildung von sozialen Netzwerken und betrachten zwei Modelle, die ein bestimmtes realistisches Verhalten einbeziehen, das in realen sozialen Netzwerken beobachtet werden kann. Das erste Modell basiert auf einer anti-präferentiellen Kantenerzeugung. Dabei nehmen wir an, dass die Kosten einer Verbindung proportional zur Popularität des Agenten am anderen Endpunkt sind. Das zweite betrachtete Modell basiert auf der Beobachtung, dass die Wahrscheinlichkeit, dass zwei Personen verbunden sind, proportional zur Länge ihrer kürzesten Kette von gegenseitigen Bekanntschaften ist. Für jedes der vier oben genannten Modelle liefern wir eine komplette spieltheoretische Analyse. Insbesondere fokussieren wir uns auf charakteristische strukturelle Eigenschaften der spieltheoretischen Gleichgewichte, die Komplexität der Berechnung einer optimalen Strategie und die Qualität der Gleichgewichte im Vergleich zu den zentral entworfenen sozial optimalen Netzwerken. Außerdem analysieren wir die Spieldynamik, d.h. den Prozess von sequentiellen verbessernden Strategieänderungen der Agenten. Dabei untersuchen wir die Konvergenz zu einem Gleichgewichtszustand und die Eigenschaften solcher Konvergenzprozesse. T2 - Spieltheoretische Erzeugung von realistischen Netzwerken KW - Algorithmic Game Theory KW - Network Creation Game KW - Price of Anarchy KW - Nash Equilibrium KW - Game Dynamics KW - Computational Hardness KW - Algorithmische Spieltheorie KW - Network Creation Game KW - Preis der Anarchie KW - Spieldynamik KW - Komplexität der Berechnung Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-548141 ER - TY - THES A1 - Molitor, Louise T1 - Strategic Residential Segregation N2 - Residential segregation is a widespread phenomenon that can be observed in almost every major city. In these urban areas, residents with different ethnical or socioeconomic backgrounds tend to form homogeneous clusters. In Schelling’s classical segregation model two types of agents are placed on a grid. An agent is content with its location if the fraction of its neighbors, which have the same type as the agent, is at least 𝜏, for some 0 < 𝜏 ≤ 1. Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty location. The model gives a coherent explanation of how clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Although the model is well studied, previous research focused on a random process point of view. However, it is more realistic to assume instead that the agents strategically choose where to live. We close this gap by introducing and analyzing game-theoretic models of Schelling segregation, where rational agents strategically choose their locations. As the first step, we introduce and analyze a generalized game-theoretic model that allows more than two agent types and more general underlying graphs modeling the residential area. We introduce different versions of Swap and Jump Schelling Games. Swap Schelling Games assume that every vertex of the underlying graph serving as a residential area is occupied by an agent and pairs of discontent agents can swap their locations, i.e., their occupied vertices, to increase their utility. In contrast, for the Jump Schelling Game, we assume that there exist empty vertices in the graph and agents can jump to these vacant vertices if this increases their utility. We show that the number of agent types as well as the structure of underlying graph heavily influence the dynamic properties and the tractability of finding an optimal strategy profile. As a second step, we significantly deepen these investigations for the swap version with 𝜏 = 1 by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy, and the dynamic properties. Moreover, we restrict the movement of agents locally. As a main takeaway, we find that both aspects influence the existence and the quality of stable states. Furthermore, also for the swap model, we follow sociological surveys and study, asking the same core game-theoretic questions, non-monotone singlepeaked utility functions instead of monotone ones, i.e., utility functions that are not monotone in the fraction of same-type neighbors. Our results clearly show that moving from monotone to non-monotone utilities yields novel structural properties and different results in terms of existence and quality of stable states. In the last part, we introduce an agent-based saturated open-city variant, the Flip Schelling Process, in which agents, based on the predominant type in their neighborhood, decide whether to change their types. We provide a general framework for analyzing the influence of the underlying topology on residential segregation and investigate the probability that an edge is monochrome, i.e., that both incident vertices have the same type, on random geometric and Erdős–Rényi graphs. For random geometric graphs, we prove the existence of a constant c > 0 such that the expected fraction of monochrome edges after the Flip Schelling Process is at least 1/2 + c. For Erdős–Rényi graphs, we show the expected fraction of monochrome edges after the Flip Schelling Process is at most 1/2 + o(1). N2 - Die Segregation von Wohngebieten ist ein weit verbreitetes Phänomen, das in fast jeder größeren Stadt zu beobachten ist. In diesen städtischen Gebieten neigen Bewohner mit unterschiedlichem ethnischen oder sozioökonomischen Hintergrund dazu, homogene Nachbarschaften zu bilden. In Schellings klassischem Segregationsmodell werden zwei Arten von Agenten auf einem Gitter platziert. Ein Agent ist mit seinem Standort zufrieden, wenn der Anteil seiner Nachbarn, die denselben Typ wie er haben, mindestens 𝜏 beträgt, für 0 < 𝜏 ≤ 1. Unzufriedene Agenten tauschen einfach ihren Standort mit einem zufällig ausgewählten anderen unzufriedenen Agenten oder springen auf einen zufälligen leeren Platz. Das Modell liefert eine kohärente Erklärung dafür, wie sich Cluster bilden können, selbst wenn alle Agenten tolerant sind, d.h. wenn sie damit einverstanden sind, in gemischten Nachbarschaften zu leben. Damit es zu Segregation kommt, genügt eine leichte Tendenz, dass die Agenten ähnliche Nachbarn bevorzugen. Obwohl das Modell gut untersucht ist, lag der Schwerpunkt der bisherigen Forschung eher auf dem Zufallsprozess. Es ist jedoch realistischer, davon auszugehen, dass Agenten strategisch ihren Wohnort aussuchen. Wir schließen diese Lücke, indem wir spieltheoretische Modelle der Schelling-Segregation einführen und analysieren, in welchen rationale Akteure ihre Standorte strategisch wählen. In einem ersten Schritt führen wir ein verallgemeinertes spieltheoretisches Modell ein, das mehr als zwei Agententypen und allgemeinere zugrundeliegende Graphen zur Modellierung des Wohngebiets zulässt und analysieren es. Zu diesem Zweck untersuchen wir verschiedene Versionen von Tausch- und Sprung-Schelling-Spielen. Bei den Tausch-Schelling-Spielen gehen wir davon aus, dass jeder Knoten des zugrunde liegenden Graphen, der als Wohngebiet dient, von einem Agenten besetzt ist und dass Paare von unzufriedenen Agenten ihre Standorte, d.h. ihre besetzten Knoten, tauschen können, um ihren Nutzen zu erhöhen. Im Gegensatz dazu gehen wir beim Sprung-Schelling-Spiel davon aus, dass es leere Knoten im Graphen gibt und die Agenten zu diesen unbesetzten Knoten springen können, wenn dies ihren Nutzen erhöht. Wir zeigen, dass die Anzahl der Agententypen sowie die zugrundeliegende Struktur des Graphen, die dynamischen Eigenschaften und die Komplexität der Berechenbarkeit eines optimalen Strategieprofils stark beeinflussen. In einem zweiten Schritt vertiefen wir diese Untersuchungen für die Tauschvariante mit 𝜏 = 1 erheblich, indem wir den Einfluss der zugrunde liegenden Topologie, die dasWohngebiet modelliert, auf die Existenz von Gleichgewichten, den Preis der Anarchie und die dynamischen Eigenschaften hin untersuchen. Darüber hinaus schränken wir die Bewegung der Agenten lokal ein. Die wichtigste Erkenntnis ist, dass beide Aspekte die Existenz als auch die Qualität stabiler Zustände beeinflussen. Desweiteren folgen wir, auch für das Tauschmodell, soziologischen Untersuchungen und untersuchen für dieselben zentralen spieltheoretischen Fragen nicht-monotone einspitzige Nutzenfunktionen anstelle von monotonen, d.h. Nutzenfunktionen, die nicht monoton bezüglich des Anteils der gleichartigen Nachbarn sind. Unsere Ergebnisse zeigen deutlich, dass der Übergang von monotonen zu nicht-monotonen Nutzenfunktionen zu neuen strukturellen Eigenschaften und anderen Ergebnissen in Bezug auf die Existenz und Qualität stabiler Zustände führt. Im letzten Teil führen wir eine agentenbasierte gesättigte Offene-Stadt-Variante ein, den Flip-Schelling-Prozess, bei dem Agenten auf der Grundlage des vorherrschenden Typs in ihrer Nachbarschaft entscheiden, ob sie ihren Typ wechseln. Wir stellen einen allgemeinen Rahmen für die Analyse des Einflusses der zugrundeliegenden Topologie auf dieWohnsegregation zur Verfügung und untersuchen die Wahrscheinlichkeit, dass eine Kante einfarbig auf zufälligen geometrischen und Erdős–Rényi-Graphen ist, d.h. dass beide inzidenten Knoten denselben Typ haben. Für zufällige geometrische Graphen beweisen wir die Existenz einer Konstante c > 0, so dass der erwartete Anteil einfarbiger Kanten nach dem Flip-Schelling-Prozess mindestens 1/2 + c beträgt. Für Erdős–Rényi-Graphen zeigen wir, dass der erwartete Anteil einfarbiger Kanten nach dem Flip-Schelling-Prozess höchstens 1/2 + o(1) ist. T2 - Strategische Wohnsegregation KW - Schelling Segregation KW - Algorithmic Game Theory KW - Schelling Process KW - Price of Anarchy KW - Game Dynamics KW - Algorithmische Spieltheorie KW - Spieldynamiken KW - Preis der Anarchie KW - Schelling Prozess KW - Schelling Segregation Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-601359 ER - TY - GEN A1 - Konigorski, Stefan A1 - Wernicke, Sarah A1 - Slosarek, Tamara A1 - Zenner, Alexander Maximilian A1 - Strelow, Nils A1 - Ruether, Darius Ferenc A1 - Henschel, Florian A1 - Manaswini, Manisha A1 - Pottbäcker, Fabian A1 - Edelman, Jonathan Antonio A1 - Owoyele, Babajide A1 - Danieletto, Matteo A1 - Golden, Eddye A1 - Zweig, Micol A1 - Nadkarni, Girish N. A1 - Bottinger, Erwin T1 - StudyU: A Platform for Designing and Conducting Innovative Digital N-of-1 Trials T2 - Zweitveröffentlichungen der Universität Potsdam : Reihe der Digital Engineering Fakultät N2 - N-of-1 trials are the gold standard study design to evaluate individual treatment effects and derive personalized treatment strategies. Digital tools have the potential to initiate a new era of N-of-1 trials in terms of scale and scope, but fully functional platforms are not yet available. Here, we present the open source StudyU platform, which includes the StudyU Designer and StudyU app. With the StudyU Designer, scientists are given a collaborative web application to digitally specify, publish, and conduct N-of-1 trials. The StudyU app is a smartphone app with innovative user-centric elements for participants to partake in trials published through the StudyU Designer to assess the effects of different interventions on their health. Thereby, the StudyU platform allows clinicians and researchers worldwide to easily design and conduct digital N-of-1 trials in a safe manner. We envision that StudyU can change the landscape of personalized treatments both for patients and healthy individuals, democratize and personalize evidence generation for self-optimization and medicine, and can be integrated in clinical practice. T3 - Zweitveröffentlichungen der Universität Potsdam : Reihe der Digital Engineering Fakultät - 12 KW - digital interventions KW - N-of-1 trial KW - SCED KW - single-case experimental design KW - web application KW - mobile application KW - app KW - digital health Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-580370 IS - 12 ER - TY - JOUR A1 - Konigorski, Stefan A1 - Wernicke, Sarah A1 - Slosarek, Tamara A1 - Zenner, Alexander Maximilian A1 - Strelow, Nils A1 - Ruether, Darius Ferenc Ruether A1 - Henschel, Florian A1 - Manaswini, Manisha A1 - Pottbäcker, Fabian A1 - Edelman, Jonathan Antonio A1 - Owoyele, Babajide A1 - Danieletto, Matteo A1 - Golden, Eddye A1 - Zweig, Micol A1 - Nadkarni, Girish N. A1 - Bottinger, Erwin T1 - StudyU: A Platform for Designing and Conducting Innovative Digital N-of-1 Trials JF - Journal of Medical Internet Research N2 - N-of-1 trials are the gold standard study design to evaluate individual treatment effects and derive personalized treatment strategies. Digital tools have the potential to initiate a new era of N-of-1 trials in terms of scale and scope, but fully functional platforms are not yet available. Here, we present the open source StudyU platform, which includes the StudyU Designer and StudyU app. With the StudyU Designer, scientists are given a collaborative web application to digitally specify, publish, and conduct N-of-1 trials. The StudyU app is a smartphone app with innovative user-centric elements for participants to partake in trials published through the StudyU Designer to assess the effects of different interventions on their health. Thereby, the StudyU platform allows clinicians and researchers worldwide to easily design and conduct digital N-of-1 trials in a safe manner. We envision that StudyU can change the landscape of personalized treatments both for patients and healthy individuals, democratize and personalize evidence generation for self-optimization and medicine, and can be integrated in clinical practice. KW - digital interventions KW - N-of-1 trial KW - SCED KW - single-case experimental design KW - web application KW - mobile application KW - app KW - digital health Y1 - 2021 U6 - https://doi.org/10.2196/35884 SN - 1438-8871 VL - 24 PB - JMIR Publications CY - Richmond, Virginia, USA ET - 7 ER - TY - THES A1 - Haarmann, Stephan T1 - WICKR: A Joint Semantics for Flexible Processes and Data N2 - Knowledge-intensive business processes are flexible and data-driven. Therefore, traditional process modeling languages do not meet their requirements: These languages focus on highly structured processes in which data plays a minor role. As a result, process-oriented information systems fail to assist knowledge workers on executing their processes. We propose a novel case management approach that combines flexible activity-centric processes with data models, and we provide a joint semantics using colored Petri nets. The approach is suited to model, verify, and enact knowledge-intensive processes and can aid the development of information systems that support knowledge work. Knowledge-intensive processes are human-centered, multi-variant, and data-driven. Typical domains include healthcare, insurances, and law. The processes cannot be fully modeled, since the underlying knowledge is too vast and changes too quickly. Thus, models for knowledge-intensive processes are necessarily underspecified. In fact, a case emerges gradually as knowledge workers make informed decisions. Knowledge work imposes special requirements on modeling and managing respective processes. They include flexibility during design and execution, ad-hoc adaption to unforeseen situations, and the integration of behavior and data. However, the predominantly used process modeling languages (e.g., BPMN) are unsuited for this task. Therefore, novel modeling languages have been proposed. Many of them focus on activities' data requirements and declarative constraints rather than imperative control flow. Fragment-Based Case Management, for example, combines activity-centric imperative process fragments with declarative data requirements. At runtime, fragments can be combined dynamically, and new ones can be added. Yet, no integrated semantics for flexible activity-centric process models and data models exists. In this thesis, Wickr, a novel case modeling approach extending fragment-based Case Management, is presented. It supports batch processing of data, sharing data among cases, and a full-fledged data model with associations and multiplicity constraints. We develop a translational semantics for Wickr targeting (colored) Petri nets. The semantics assert that a case adheres to the constraints in both the process fragments and the data models. Among other things, multiplicity constraints must not be violated. Furthermore, the semantics are extended to multiple cases that operate on shared data. Wickr shows that the data structure may reflect process behavior and vice versa. Based on its semantics, prototypes for executing and verifying case models showcase the feasibility of Wickr. Its applicability to knowledge-intensive and to data-centric processes is evaluated using well-known requirements from related work. N2 - Traditionelle Prozessmodellierungssprachen sind auf hoch strukturierte Prozesse ausgelegt, in denen Daten nur eine Nebenrolle spielen. Sie eignen sich daher nicht für wissensintensive Prozesse, die flexibel und datengetrieben sind. Deshalb können prozessorientierte Informationssysteme Fachexperten nicht gänzlich unterstützen. Diese Arbeit beinhaltet eine neue Modellierungssprache, die flexible Prozessmodelle mit Datenmodellen kombiniert. Die Semantik dieser Sprache ist mittels gefärbten Petri-Netzen formal definiert. Wissensintensive Prozesse können so modelliert, verifiziert und ausgeführt werden. Wissensintensive Prozesse sind variantenreich und involvieren Fachexperten, die mit ihren Entscheidungen die Prozessausführung prägen. Typische Anwendungsbereiche sind das Gesundheitswesen, Rechtswesen und Versicherungen. Diese Prozesse können i.d.R. nicht vollständig spezifiziert werden, da das zugrundeliegende Wissen zu umfangreich ist und sich außerdem zu schnell verändert. Die genaue Reihenfolge der Aktivitäten wird erst durch die Fachexperten zur Laufzeit festgelegt. Deshalb erfordern dieser Prozesse Flexibilität sowohl zur Entwurfszeit wie zur Laufzeit, Daten und Verhalten müssen in enger Beziehung betrachtet werden. Zudem muss es möglich sein, den Prozess anzupassen, falls eine unvorhergesehene Situation eintreten. Etablierte Prozessmodellierungssprachen, wie z.B. BPMN, sind daher ungeeignet. Deshalb werden neue Sprachen entwickelt, in denen sich generell zwei Tendenzen beobachten lassen: ein Wechseln von imperativer zu deklarativer Modellierung und eine zunehmende Integration von Daten. Im Fragment-Basierten-Case-Management können imperative Prozessfragmente zur Laufzeit flexibel kombiniert werden, solange spezifizierten Datenanforderungen erfüllt sind. In dieser Arbeit wird Wickr vorgestellt. Dabei handelt es sich um eine Modellierungssprache, die das Fragment-Basierte-Case-Management erweitert. Wickr kombiniert Prozessfragmente mit einem Datenmodell inklusive Assoziationen und zwei Arten an Multiplizitätseinschränkungen: Die erste Art muss immer gelten, wohingegen die zweite nur am Ende eines Falls gelten muss. Zusätzlich unterstützt Wickr Stapelverarbeitung und Datenaustausch zwischen Fällen. Des Weiteren entwickeln wir eine translationale Semantik, die Wickr in gefärbte Petri-Netze übersetzt. Die Semantik berücksichtigt sowohl die Vorgaben des Prozessmodells wie auch die des Datenmodells. Die Semantik eignet sich nicht nur für die Beschreibung eines einzelnen Falls, sondern kann auch mehrere untereinander in Beziehung stehende Fälle abdecken. Durch Prototypen wird die Umsetzbarkeit von Wickr demonstriert und mittels bekannten Anforderungslisten die Einsatzmöglichkeit für wissensintensive und datengetriebene Prozesse evaluiert. T2 - Wickr: Eine gemeinsame Semantik für flexible Prozesse und Daten KW - Case Management KW - Business Process Management KW - Process Modeling KW - Data Modeling KW - Execution Semantics KW - Geschäftsprozessmanagement KW - Fallmanagement KW - Datenmodellierung KW - Ausführungssemantiken KW - Prozessmodellierung Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-546137 ER -