TY - THES A1 - Afifi, Haitham T1 - Wireless In-Network Processing for Multimedia Applications T1 - Drahtlose In-Network-Verarbeitung für Multimedia-Anwendungen N2 - With the recent growth of sensors, cloud computing handles the data processing of many applications. Processing some of this data on the cloud raises, however, many concerns regarding, e.g., privacy, latency, or single points of failure. Alternatively, thanks to the development of embedded systems, smart wireless devices can share their computation capacity, creating a local wireless cloud for in-network processing. In this context, the processing of an application is divided into smaller jobs so that a device can run one or more jobs. The contribution of this thesis to this scenario is divided into three parts. In part one, I focus on wireless aspects, such as power control and interference management, for deciding which jobs to run on which node and how to route data between nodes. Hence, I formulate optimization problems and develop heuristic and meta-heuristic algorithms to allocate wireless and computation resources. Additionally, to deal with multiple applications competing for these resources, I develop a reinforcement learning (RL) admission controller to decide which application should be admitted. Next, I look into acoustic applications to improve wireless throughput by using microphone clock synchronization to synchronize wireless transmissions. In the second part, I jointly work with colleagues from the acoustic processing field to optimize both network and application (i.e., acoustic) qualities. My contribution focuses on the network part, where I study the relation between acoustic and network qualities when selecting a subset of microphones for collecting audio data or selecting a subset of optional jobs for processing these data; too many microphones or too many jobs can lessen quality by unnecessary delays. Hence, I develop RL solutions to select the subset of microphones under network constraints when the speaker is moving while still providing good acoustic quality. Furthermore, I show that autonomous vehicles carrying microphones improve the acoustic qualities of different applications. Accordingly, I develop RL solutions (single and multi-agent ones) for controlling these vehicles. In the third part, I close the gap between theory and practice. I describe the features of my open-source framework used as a proof of concept for wireless in-network processing. Next, I demonstrate how to run some algorithms developed by colleagues from acoustic processing using my framework. I also use the framework for studying in-network delays (wireless and processing) using different distributions of jobs and network topologies. N2 - Mit der steigenden Anzahl von Sensoren übernimmt Cloud Computing die Datenverarbeitung vieler Anwendungen. Dies wirft jedoch viele Bedenken auf, z. B. in Bezug auf Datenschutz, Latenzen oder Fehlerquellen. Alternativ und dank der Entwicklung eingebetteter Systeme können drahtlose intelligente Geräte für die lokale Verarbeitung verwendet werden, indem sie ihre Rechenkapazität gemeinsam nutzen und so eine lokale drahtlose Cloud für die netzinterne Verarbeitung schaffen. In diesem Zusammenhang wird eine Anwendung in kleinere Aufgaben unterteilt, so dass ein Gerät eine oder mehrere Aufgaben ausführen kann. Der Beitrag dieser Arbeit zu diesem Szenario gliedert sich in drei Teile. Im ersten Teil konzentriere ich mich auf drahtlose Aspekte wie Leistungssteuerung und Interferenzmanagement um zu entscheiden, welche Aufgaben auf welchem Knoten ausgeführt werden sollen und wie die Daten zwischen den Knoten weitergeleitet werden sollen. Daher formuliere ich Optimierungsprobleme und entwickle heuristische und metaheuristische Algorithmen zur Zuweisung von Ressourcen eines drahtlosen Netzwerks. Um mit mehreren Anwendungen, die um diese Ressourcen konkurrieren, umgehen zu können, entwickle ich außerdem einen Reinforcement Learning (RL) Admission Controller, um zu entscheiden, welche Anwendung zugelassen werden soll. Als Nächstes untersuche ich akustische Anwendungen zur Verbesserung des drahtlosen Durchsatzes, indem ich Mikrofon-Taktsynchronisation zur Synchronisierung drahtloser Übertragungen verwende. Im zweiten Teil arbeite ich mit Kollegen aus dem Bereich der Akustikverarbeitung zusammen, um sowohl die Netzwerk- als auch die Anwendungsqualitäten (d.h. die akustischen) zu optimieren. Mein Beitrag konzentriert sich auf den Netzwerkteil, wo ich die Beziehung zwischen akustischen und Netzwerkqualitäten bei der Auswahl einer Teilmenge von Mikrofonen für die Erfassung von Audiodaten oder der Auswahl einer Teilmenge von optionalen Aufgaben für die Verarbeitung dieser Daten untersuche; zu viele Mikrofone oder zu viele Aufgaben können die Qualität durch unnötige Verzögerungen verringern. Daher habe ich RL-Lösungen entwickelt, um die Teilmenge der Mikrofone unter Netzwerkbeschränkungen auszuwählen, wenn sich der Sprecher bewegt, und dennoch eine gute akustische Qualität gewährleistet. Außerdem zeige ich, dass autonome Fahrzeuge, die Mikrofone mit sich führen, die akustische Qualität verschiedener Anwendungen verbessern. Dementsprechend entwickle ich RL-Lösungen (Einzel- und Multi-Agenten-Lösungen) für die Steuerung dieser Fahrzeuge. Im dritten Teil schließe ich die Lücke zwischen Theorie und Praxis. Ich beschreibe die Eigenschaften meines Open-Source-Frameworks, das als Prototyp für die drahtlose netzinterne Verarbeitung verwendet wird. Anschließend zeige ich, wie einige Algorithmen, die von Kollegen aus der Akustikverarbeitung entwickelt wurden, mit meinem Framework ausgeführt werden können. Außerdem verwende ich das Framework für die Untersuchung von netzinternen Verzögerungen unter Verwendung verschiedener Aufgabenverteilungen und Netzwerktopologien. KW - wireless networks KW - reinforcement learning KW - network optimization KW - Netzoptimierung KW - bestärkendes Lernen KW - drahtloses Netzwerk Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-604371 ER - TY - THES A1 - Alhosseini Almodarresi Yasin, Seyed Ali T1 - Classification, prediction and evaluation of graph neural networks on online social media platforms T1 - Klassifizierung, Vorhersage und Bewertung graphischer neuronaler Netze auf Online-Social-Media-Plattformen N2 - The vast amount of data generated on social media platforms have made them a valuable source of information for businesses, governments and researchers. Social media data can provide insights into user behavior, preferences, and opinions. In this work, we address two important challenges in social media analytics. Predicting user engagement with online content has become a critical task for content creators to increase user engagement and reach larger audiences. Traditional user engagement prediction approaches rely solely on features derived from the user and content. However, a new class of deep learning methods based on graphs captures not only the content features but also the graph structure of social media networks. This thesis proposes a novel Graph Neural Network (GNN) approach to predict user interaction with tweets. The proposed approach combines the features of users, tweets and their engagement graphs. The tweet text features are extracted using pre-trained embeddings from language models, and a GNN layer is used to embed the user in a vector space. The GNN model then combines the features and graph structure to predict user engagement. The proposed approach achieves an accuracy value of 94.22% in classifying user interactions, including likes, retweets, replies, and quotes. Another major challenge in social media analysis is detecting and classifying social bot accounts. Social bots are automated accounts used to manipulate public opinion by spreading misinformation or generating fake interactions. Detecting social bots is critical to prevent their negative impact on public opinion and trust in social media. In this thesis, we classify social bots on Twitter by applying Graph Neural Networks. The proposed approach uses a combination of both the features of a node and an aggregation of the features of a node’s neighborhood to classify social bot accounts. Our final results indicate a 6% improvement in the area under the curve score in the final predictions through the utilization of GNN. Overall, our work highlights the importance of social media data and the potential of new methods such as GNNs to predict user engagement and detect social bots. These methods have important implications for improving the quality and reliability of information on social media platforms and mitigating the negative impact of social bots on public opinion and discourse. N2 - Die riesige Menge an Daten, die auf Social-Media-Plattformen generiert wird, hat sie zu einer wertvollen Informationsquelle für Unternehmen, Regierungen und Forscher gemacht. Daten aus sozialen Medien können Einblicke in das Verhalten, die Vorlieben und die Meinungen der Nutzer geben. In dieser Arbeit befassen wir uns mit zwei wichtigen Herausforderungen im Bereich der Social-Media-Analytik. Die Vorhersage des Nutzerinteresses an Online-Inhalten ist zu einer wichtigen Aufgabe für die Ersteller von Inhalten geworden, um das Nutzerengagement zu steigern und ein größeres Publikum zu erreichen. Herkömmliche Ansätze zur Vorhersage des Nutzerengagements stützen sich ausschließlich auf Merkmale, die aus dem Nutzer und dem Inhalt abgeleitet werden. Eine neue Klasse von Deep-Learning-Methoden, die auf Graphen basieren, erfasst jedoch nicht nur die Inhaltsmerkmale, sondern auch die Graphenstruktur von Social-Media-Netzwerken. In dieser Arbeit wird ein neuartiger Graph Neural Network (GNN)-Ansatz zur Vorhersage der Nutzerinteraktion mit Tweets vorgeschlagen. Der vorgeschlagene Ansatz kombiniert die Merkmale von Nutzern, Tweets und deren Engagement-Graphen. Die Textmerkmale der Tweets werden mit Hilfe von vortrainierten Einbettungen aus Sprachmodellen extrahiert, und eine GNN-Schicht wird zur Einbettung des Nutzers in einen Vektorraum verwendet. Das GNN-Modell kombiniert dann die Merkmale und die Graphenstruktur, um das Nutzerengagement vorherzusagen. Der vorgeschlagene Ansatz erreicht eine Genauigkeit von 94,22% bei der Klassifizierung von Benutzerinteraktionen, einschließlich Likes, Retweets, Antworten und Zitaten. Eine weitere große Herausforderung bei der Analyse sozialer Medien ist die Erkennung und Klassifizierung von Social-Bot-Konten. Social Bots sind automatisierte Konten, die dazu dienen, die öffentliche Meinung zu manipulieren, indem sie Fehlinformationen verbreiten oder gefälschte Interaktionen erzeugen. Die Erkennung von Social Bots ist entscheidend, um ihre negativen Auswirkungen auf die öffentliche Meinung und das Vertrauen in soziale Medien zu verhindern. In dieser Arbeit klassifizieren wir Social Bots auf Twitter mit Hilfe von Graph Neural Networks. Der vorgeschlagene Ansatz verwendet eine Kombination aus den Merkmalen eines Knotens und einer Aggregation der Merkmale der Nachbarschaft eines Knotens, um Social-Bot-Konten zu klassifizieren. Unsere Endergebnisse zeigen eine 6%ige Verbesserung der Fläche unter der Kurve bei den endgültigen Vorhersagen durch die Verwendung von GNN. Insgesamt unterstreicht unsere Arbeit die Bedeutung von Social-Media-Daten und das Potenzial neuer Methoden wie GNNs zur Vorhersage des Nutzer-Engagements und zur Erkennung von Social Bots. Diese Methoden haben wichtige Auswirkungen auf die Verbesserung der Qualität und Zuverlässigkeit von Informationen auf Social-Media-Plattformen und die Abschwächung der negativen Auswirkungen von Social Bots auf die öffentliche Meinung und den Diskurs. KW - graph neural networks KW - social bot detection KW - user engagement KW - graphische neuronale Netze KW - Social Bots erkennen KW - Nutzer-Engagement Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-626421 ER - TY - THES A1 - Amirkhanyan, Aragats T1 - Methods and frameworks for GeoSpatioTemporal data analytics T1 - Methoden und Frameworks für geo-raumzeitliche Datenanalysen N2 - In the era of social networks, internet of things and location-based services, many online services produce a huge amount of data that have valuable objective information, such as geographic coordinates and date time. These characteristics (parameters) in the combination with a textual parameter bring the challenge for the discovery of geospatiotemporal knowledge. This challenge requires efficient methods for clustering and pattern mining in spatial, temporal and textual spaces. In this thesis, we address the challenge of providing methods and frameworks for geospatiotemporal data analytics. As an initial step, we address the challenges of geospatial data processing: data gathering, normalization, geolocation, and storage. That initial step is the basement to tackle the next challenge -- geospatial clustering challenge. The first step of this challenge is to design the method for online clustering of georeferenced data. This algorithm can be used as a server-side clustering algorithm for online maps that visualize massive georeferenced data. As the second step, we develop the extension of this method that considers, additionally, the temporal aspect of data. For that, we propose the density and intensity-based geospatiotemporal clustering algorithm with fixed distance and time radius. Each version of the clustering algorithm has its own use case that we show in the thesis. In the next chapter of the thesis, we look at the spatiotemporal analytics from the perspective of the sequential rule mining challenge. We design and implement the framework that transfers data into textual geospatiotemporal data - data that contain geographic coordinates, time and textual parameters. By this way, we address the challenge of applying pattern/rule mining algorithms in geospatiotemporal space. As the applicable use case study, we propose spatiotemporal crime analytics -- discovery spatiotemporal patterns of crimes in publicly available crime data. The second part of the thesis, we dedicate to the application part and use case studies. We design and implement the application that uses the proposed clustering algorithms to discover knowledge in data. Jointly with the application, we propose the use case studies for analysis of georeferenced data in terms of situational and public safety awareness. N2 - Heute ist die Zeit der sozialen Netzwerke, des Internets der Dinge und der Standortbezogenen Diensten (Location-Based services). Viele Online-Dienste erzeugen eine riesige Datenmenge, die wertvolle Informationen enthält, wie z. B. geographische Koordinaten und Datum sowie Zeit. Diese Informationen (Parameter) in Kombination mit einem Textparameter stellen die Herausforderung für die Entdeckung von geo-raumzeitlichem (geospatiotemporal) Wissen dar. Diese Herausforderung erfordert effiziente Methoden zum Clustering und Pattern-Mining in räumlichen, zeitlichen und textlichen Aspekten. In dieser Dissertation stellen wir uns der Herausforderung, Methoden und Frameworks für geo-raumzeitliche Datenanalysen bereitzustellen. Im ersten Schritt gehen wir auf die Herausforderungen der Geodatenverarbeitung ein: Datenerfassung, -Normalisierung, -Ortung und -Speicherung. Dieser Schritt ist der Grundstein für die nächste Herausforderung – das geographische Clustering. Es erfordert das Entwerfen einer Methode für das Online-Clustering georeferenzierter Daten. Dieser Algorithmus kann als Serverseitiger Clustering-Algorithmus für Online-Karten verwendet werden, die massive georeferenzierte Daten visualisieren. Im zweiten Schritt entwickeln wir die Erweiterung dieser Methode, die zusätzlich den zeitlichen Aspekt der Daten berücksichtigt. Dazu schlagen wir den Dichte und Intensitätsbasierten geo-raumzeitlichen Clustering-Algorithmus mit festem Abstand und Zeitradius vor. Jede Version des Clustering-Algorithmus hat einen eigenen Anwendungsfall, den wir in dieser Doktorarbeit zeigen. Im nächsten Kapitel dieser Arbeit betrachten wir die raumzeitlich Analyse aus der Perspektive der sequentiellen Regel-Mining-Herausforderung. Wir entwerfen und implementieren ein Framework, das Daten in textliche raumzeitliche Daten umwandelt. Solche Daten enthalten geographische Koordinaten, Zeit und Textparameter. Auf diese Weise stellen wir uns der Herausforderung, Muster- / Regel-Mining-Algorithmen auf geo-raumzeitliche Daten anzuwenden. Als Anwendungsfallstudie schlagen wir raumzeitliche Verbrechensanalysen vor – Entdeckung raumzeitlicher Muster von Verbrechen in öffentlich zugänglichen Datenbanken. Im zweiten Teil der Arbeit diskutieren wir über die Anwendung und die Fallstudien. Wir entwerfen und implementieren eine Anwendungssoftware, die die vorgeschlagene Clustering-Algorithmen verwendet, um das Wissen in Daten zu entdecken. Gemeinsam mit der Anwendungssoftware betrachten wir Anwendungsbeispiele für die Analyse georeferenzierter Daten im Hinblick auf das Situationsbewusstsein. KW - geospatial data KW - data analytics KW - clustering KW - situational awareness KW - Geodaten KW - Datenanalyse KW - Clustering KW - Situationsbewusstsein Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-441685 ER - TY - THES A1 - Bano, Dorina T1 - Discovering data models from event logs T1 - Entdecken von Datenmodellen aus Ereignisprotokollen N2 - In the last two decades, process mining has developed from a niche discipline to a significant research area with considerable impact on academia and industry. Process mining enables organisations to identify the running business processes from historical execution data. The first requirement of any process mining technique is an event log, an artifact that represents concrete business process executions in the form of sequence of events. These logs can be extracted from the organization's information systems and are used by process experts to retrieve deep insights from the organization's running processes. Considering the events pertaining to such logs, the process models can be automatically discovered and enhanced or annotated with performance-related information. Besides behavioral information, event logs contain domain specific data, albeit implicitly. However, such data are usually overlooked and, thus, not utilized to their full potential. Within the process mining area, we address in this thesis the research gap of discovering, from event logs, the contextual information that cannot be captured by applying existing process mining techniques. Within this research gap, we identify four key problems and tackle them by looking at an event log from different angles. First, we address the problem of deriving an event log in the absence of a proper database access and domain knowledge. The second problem is related to the under-utilization of the implicit domain knowledge present in an event log that can increase the understandability of the discovered process model. Next, there is a lack of a holistic representation of the historical data manipulation at the process model level of abstraction. Last but not least, each process model presumes to be independent of other process models when discovered from an event log, thus, ignoring possible data dependencies between processes within an organization. For each of the problems mentioned above, this thesis proposes a dedicated method. The first method provides a solution to extract an event log only from the transactions performed on the database that are stored in the form of redo logs. The second method deals with discovering the underlying data model that is implicitly embedded in the event log, thus, complementing the discovered process model with important domain knowledge information. The third method captures, on the process model level, how the data affects the running process instances. Lastly, the fourth method is about the discovery of the relations between business processes (i.e., how they exchange data) from a set of event logs and explicitly representing such complex interdependencies in a business process architecture. All the methods introduced in this thesis are implemented as a prototype and their feasibility is proven by being applied on real-life event logs. N2 - In den letzten zwei Jahrzehnten hat sich Process Mining von einer Nischendisziplin zu einem bedeutenden Forschungsgebiet mit erheblichen Auswirkungen auf Wissenschaft und Industrie entwickelt. Process Mining ermöglicht es Unternehmen, die laufenden Geschäftsprozesse anhand historischer Ausführungsdaten zu identifizieren. Die erste Voraussetzung für jede Process-Mining-Technik ist ein Ereignisprotokoll (Event Log), ein Artefakt, das konkrete Geschäftsprozessausführungen in Form einer Abfolge von Ereignissen darstellt. Diese Protokolle (Logs) können aus den Informationssystemen der Unternehmen extrahiert werden und ermöglichen es Prozessexperten, tiefe Einblicke in die laufenden Unternehmensprozesse zu gewinnen. Unter Berücksichtigung der Abfolge der Ereignisse in diesen Protokollen (Logs) können Prozessmodelle automatisch entdeckt und mit leistungsbezogenen Informationen erweitert werden. Neben verhaltensbezogenen Informationen enthalten Ereignisprotokolle (Event Logs) auch domänenspezifische Daten, wenn auch nur implizit. Solche Daten werden jedoch in der Regel nicht in vollem Umfang genutzt. Diese Arbeit befasst sich im Bereich Process Mining mit der Forschungslücke der Extraktion von Kontextinformationen aus Ereignisprotokollen (Event Logs), die von bestehenden Process Mining-Techniken nicht erfasst werden. Innerhalb dieser Forschungslücke identifizieren wir vier Schlüsselprobleme, bei denen wir die Ereignisprotokolle (Event Logs) aus verschiedenen Perspektiven betrachten. Zunächst befassen wir uns mit dem Problem der Erfassung eines Ereignisprotokolls (Event Logs) ohne hinreichenden Datenbankzugang. Das zweite Problem ist die unzureichende Nutzung des in Ereignisprotokollen (Event Logs) enthaltenen Domänenwissens, das zum besseren Verständnis der generierten Prozessmodelle beitragen kann. Außerdem mangelt es an einer ganzheitlichen Darstellung der historischen Datenmanipulation auf Prozessmodellebene. Nicht zuletzt werden Prozessmodelle häufig unabhängig von anderen Prozessmodellen betrachtet, wenn sie aus Ereignisprotokollen (Event Logs) ermittelt wurden. Dadurch können mögliche Datenabhängigkeiten zwischen Prozessen innerhalb einer Organisation übersehen werden. Für jedes der oben genannten Probleme schlägt diese Arbeit eine eigene Methode vor. Die erste Methode ermöglicht es, ein Ereignisprotokoll (Event Log) ausschließlich anhand der Historie der auf einer Datenbank durchgeführten Transaktionen zu extrahieren, die in Form von Redo-Logs gespeichert ist. Die zweite Methode befasst sich mit der Entdeckung des zugrundeliegenden Datenmodells, das implizit in dem jeweiligen Ereignisprotokoll (Event Log) eingebettet ist, und ergänzt so mit das entdeckte Prozessmodell mit wichtigen, domänenspezifischen Informationen. Bei der dritten Methode wird auf der Ebene des Prozess- modells erfasst, wie sich die Daten auf die laufenden Prozessinstanzen auswirken. Die vierte Methode befasst sich schließlich mit der Entdeckung der Beziehungen zwischen Geschäftsprozessen (d.h. deren Datenaustausch) auf Basis der jeweiligen Ereignisprotokolle (Event Logs), sowie mit der expliziten Darstellung solcher komplexen Abhängigkeiten in einer Geschäftsprozessarchitektur. Alle in dieser Arbeit vorgestellten Methoden sind als Prototyp implementiert und ihre Anwendbarkeit wird anhand ihrer Anwendung auf reale Ereignisprotokolle (Event Logs) nachgewiesen. KW - process mining KW - data models KW - business process architectures KW - Datenmodelle KW - Geschäftsprozessarchitekturen Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-585427 ER - TY - THES A1 - Bartz, Christian T1 - Reducing the annotation burden: deep learning for optical character recognition using less manual annotations N2 - Text is a ubiquitous entity in our world and daily life. We encounter it nearly everywhere in shops, on the street, or in our flats. Nowadays, more and more text is contained in digital images. These images are either taken using cameras, e.g., smartphone cameras, or taken using scanning devices such as document scanners. The sheer amount of available data, e.g., millions of images taken by Google Streetview, prohibits manual analysis and metadata extraction. Although much progress was made in the area of optical character recognition (OCR) for printed text in documents, broad areas of OCR are still not fully explored and hold many research challenges. With the mainstream usage of machine learning and especially deep learning, one of the most pressing problems is the availability and acquisition of annotated ground truth for the training of machine learning models because obtaining annotated training data using manual annotation mechanisms is time-consuming and costly. In this thesis, we address of how we can reduce the costs of acquiring ground truth annotations for the application of state-of-the-art machine learning methods to optical character recognition pipelines. To this end, we investigate how we can reduce the annotation cost by using only a fraction of the typically required ground truth annotations, e.g., for scene text recognition systems. We also investigate how we can use synthetic data to reduce the need of manual annotation work, e.g., in the area of document analysis for archival material. In the area of scene text recognition, we have developed a novel end-to-end scene text recognition system that can be trained using inexact supervision and shows competitive/state-of-the-art performance on standard benchmark datasets for scene text recognition. Our method consists of two independent neural networks, combined using spatial transformer networks. Both networks learn together to perform text localization and text recognition at the same time while only using annotations for the recognition task. We apply our model to end-to-end scene text recognition (meaning localization and recognition of words) and pure scene text recognition without any changes in the network architecture. In the second part of this thesis, we introduce novel approaches for using and generating synthetic data to analyze handwriting in archival data. First, we propose a novel preprocessing method to determine whether a given document page contains any handwriting. We propose a novel data synthesis strategy to train a classification model and show that our data synthesis strategy is viable by evaluating the trained model on real images from an archive. Second, we introduce the new analysis task of handwriting classification. Handwriting classification entails classifying a given handwritten word image into classes such as date, word, or number. Such an analysis step allows us to select the best fitting recognition model for subsequent text recognition; it also allows us to reason about the semantic content of a given document page without the need for fine-grained text recognition and further analysis steps, such as Named Entity Recognition. We show that our proposed approaches work well when trained on synthetic data. Further, we propose a flexible metric learning approach to allow zero-shot classification of classes unseen during the network’s training. Last, we propose a novel data synthesis algorithm to train off-the-shelf pixel-wise semantic segmentation networks for documents. Our data synthesis pipeline is based on the famous Style-GAN architecture and can synthesize realistic document images with their corresponding segmentation annotation without the need for any annotated data! N2 - Text umgibt uns überall. Wir finden Text in allen Lebenslagen, z.B. in einem Geschäft, an Gebäuden, oder in unserer Wohnung. Viele dieser Textentitäten können heutzutage auch in digitalen Bildern gefunden werden, welche auf verschiedene Art und Weise erstellt werden können, z.B. mittels einer Kamera in einem Smartphone oder durch einen Dokumentenscanner. Die Anzahl verfügbarer digitaler Bilder, z.B. Millionen – wenn nicht Milliarden von Bildern – in Google Streetview, macht eine manuelle Analyse der Bilddaten unmöglich. Obwohl es im Gebiet der Optical Character Recognition (OCR) in den letzten Jahren viel Fortschritt gab, gibt es doch noch viele Bereiche, die noch nicht vollständig erforscht worden sind. Der immer zunehmende Einsatz von Methoden des maschinellen Lernens, insbesondere der Einsatz von Deep Learning Technologien, im Bereich der OCR, führt zu dem großen Problem der Verfügbarkeit von annotierten Trainingsdaten. Die Beschaffung annotierter Daten mittels manueller Annotation ist zeitintensiv und sehr teuer. In dieser Arbeit zeigen wir neue Wege und Verfahren auf, wie das Problem der Beschaffung annotierter Daten für die Anwendung von modernsten Deep Learning Verfahren im Bereich der OCR gelöst werden könnte. Hierbei zeigen wir neue Verfahren in zwei Unterbereichen der OCR. Einerseits untersuchen wir, wie wir die Annotationskosten reduzieren könnten, indem wir inexakte Annotationen benutzen um z.B. die Kosten der Annotation von echten Daten im Bereich der Texterkennung aus natürlichen Bildern zu reduzieren. Dieses System wird mittels weak supervision trainiert und erreicht Ergebnisse, die auf dem Stand der Technik bzw. darüber liegen. Unsere Methode basiert auf zwei unabhängigen neuronalen Netzwerken, die mittels eines Spatial Transformers verbunden werden. Beide Netzwerke werden zusammen trainiert und lernen zusammen, wie Text gefunden und gelesen werden kann. Dabei nutzen wir aber nur Annotationen und Supervision für das Lesen (recognition) des Textes, nicht für die Textfindung. Wir zeigen weiterhin, dass unser System für eine Mehrzahl von Aufgaben im Bereich der Texterkennung aus natürlichen Bildern genutzt werden kann, ohne Veränderungen im Netzwerk vornehmen zu müssen. Andererseits untersuchen wir, wie wir Verfahren zur Erstellung von synthetischen Daten benutzen können, um die Kosten und den Aufwand der manuellen Annotation zu verringern und zeigen Ergebnisse aus dem Bereich der Analyse von Handschrift in historischen Archivdokumenten. Zuerst präsentieren wir ein System zur Erkennung, ob ein Bild überhaupt Handschrift enthält. Hier schlagen wir eine neue Datengenerierungsmethode vor. Die generierten Daten werden zum Training eines Klassifizierungsmodells genutzt. Unsere experimentellen Ergebnisse belegen, dass unsere Idee auch auf echten Daten aus einem Archiv eingesetzt werden kann. Als Zweites führen wir einen neuen Schritt in einer Dokumentenanalyseplattform ein: Handschriftklassifizierung. Hier ordnen wir Bilder einzelner handgeschriebener Wörter anhand ihrer visuellen Struktur in Klassen, wie Zahlen, Datumsangaben oder Wörter ein. Die Einführung dieses Analyseschrittes erlaubt es uns den besten Algorithmus für den nächsten Schritt, die eigentliche Handschrifterkennung, zu finden. Der Analyseschritt erlaubt es uns auch, bereits Aussagen über den semantischen Inhalt eines Dokumentes zu treffen, ohne weitere Analyseschritte, wie Named Entity Recognition, durchführen zu müssen. Wir zeigen, dass unser Ansatz sehr gut funktioniert, wenn er auf synthetischen Daten trainiert wird; wir zeigen weiterhin, dass unser Ansatz auch für zero-shot Klassifikation eingesetzt werden kann. Zum Schluss präsentieren wir ein neues Verfahren zur Generierung von Trainingsdaten für die pixelgenaue semantische Segmentierung in Bildern von Dokumenten. Unser Verfahren basiert auf der bekannten StyleGAN Architektur und ist in der Lage Bilder mit entsprechender Annotation automatisch zu generieren. Hierbei werden keine echten annotierten Daten benötigt und das Verfahren kann auf jeder Form von Dokumenten eingesetzt werden. KW - computer vision KW - optical character recognition KW - archive analysis KW - data synthesis KW - weak supervision KW - Archivanalyse KW - maschinelles Sehen KW - Datensynthese KW - Texterkennung KW - schwach überwachtes maschinelles Lernen Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-555407 ER - TY - THES A1 - Batoulis, Kimon T1 - Sound integration of process and decision models T1 - Korrekte Integration von Prozess- und Entscheidungsmodellen N2 - Business process management is an established technique for business organizations to manage and support their processes. Those processes are typically represented by graphical models designed with modeling languages, such as the Business Process Model and Notation (BPMN). Since process models do not only serve the purpose of documentation but are also a basis for implementation and automation of the processes, they have to satisfy certain correctness requirements. In this regard, the notion of soundness of workflow nets was developed, that can be applied to BPMN process models in order to verify their correctness. Because the original soundness criteria are very restrictive regarding the behavior of the model, different variants of the soundness notion have been developed for situations in which certain violations are not even harmful. All of those notions do only consider the control-flow structure of a process model, however. This poses a problem, taking into account the fact that with the recent release and the ongoing development of the Decision Model and Notation (DMN) standard, an increasing number of process models are complemented by respective decision models. DMN is a dedicated modeling language for decision logic and separates the concerns of process and decision logic into two different models, process and decision models respectively. Hence, this thesis is concerned with the development of decisionaware soundness notions, i.e., notions of soundness that build upon the original soundness ideas for process models, but additionally take into account complementary decision models. Similar to the various notions of workflow net soundness, this thesis investigates different notions of decision soundness that can be applied depending on the desired degree of restrictiveness. Since decision tables are a standardized means of DMN to represent decision logic, this thesis also puts special focus on decision tables, discussing how they can be translated into an unambiguous format and how their possible output values can be efficiently determined. Moreover, a prototypical implementation is described that supports checking a basic version of decision soundness. The decision soundness notions were also empirically evaluated on models from participants of an online course on process and decision modeling as well as from a process management project of a large insurance company. The evaluation demonstrates that violations of decision soundness indeed occur and can be detected with our approach. N2 - Das Prozessmanagement ist eine etablierte Methode für Unternehmen zur Verwaltung und Unterstützung ihrer Geschäftsprozesse. Solche Prozesse werden typischerweise durch graphische Modelle dargestellt, welche mit Modellierungssprachen wie etwa der Business Process Model and Notation (BPMN) erstellt werden. Da Prozessmodelle nicht nur der Dokumentation der Prozesse dienen, sondern auch die Grundlage für deren Implementierung und Automatisierung sind, müssen sie bestimmte Korrektheitsanforderungen erfüllen. In dieser Hinsicht wurde der Begriff der Soundness einesWorkflow-Netzes entwickelt, welcher auch auf BPMN-Prozessmodelle angewendet werden kann, um deren Korrektheit zu prüfen. Da die ursprünglichen Soundness-Kriterien sehr restriktiv bezüglich des Verhaltens des Modells sind, wurden zudem Varianten des Soundness-Begriffs entwickelt. Diese können in Situationen verwendet werden, in denen bestimmte Verletzungen der Kriterien tolerabel sind. Diese Soundness-Begriffe berücksichtigen allerdings ausschließlich den Kontrollfluss der Prozessmodelle. Dies stellt ein Problem dar, weil viele Prozessmodelle heutzutage durch Entscheidungsmodelle ergänzt werden. In diesem Kontext ist die Decision Model and Notation (DMN) eine dedizierte Sprache zur Modellierung von Entscheidungen und unterstüzt die Trennung von Kontrollfluss- und Entscheidungslogik. Die vorliegende Dissertation befasst sich daher mit der Entwicklung von erweiterten Soundness-Begriffen, die sowohl Prozess- als auch Entscheidungsmodelle berücksichtigen. Ähnlich zu den bestehenden Soundness-Varianten, werden in dieser Arbeit Varianten des erweiterten Soundness-Begriffs untersucht, die je nach gewünschtem Restriktionsgrad angewendet werden können. Da Entscheidungstabellen eine in der DMN standadisierte Form sind, um Entscheidungslogik auszudrücken, fokussiert sich diese Arbeit inbesondere auf Entscheidungstabellen. So wird diskutiert wie DMN-Tabellen in ein eindeutiges Format übersetzt werden können und wie sich deren möglichen Rückgabewerte effizient bestimmen lassen. Ferner beschreibt die Arbeit eine prototypische Implementierung, die das Prüfen einer elementaren Variante des erweiterten Soundness-Begriffs erlaubt. Die Begriffe wurden außerdem empirisch evaluiert. Dazu dienten zum einen Modelle von Teilnehmern eines Online-Kurses zur Prozess- und Entscheidungsmodellierung. Zum anderen wurden Modelle eines Versicherungsunternehmens analysiert. Die Evaluierung zeigt, das Verstöße gegen den erweiterten Soundness-Begriff in der Tat auftreten und durch den hier beschriebenen Ansatz erkannt werden können. KW - decision-aware process models KW - soundness KW - decision soundness KW - formal verification KW - entscheidungsbewusste Prozessmodelle KW - Korrektheit KW - Entscheidungskorrektheit KW - formale Verifikation Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-437386 ER - TY - THES A1 - Bazhenova, Ekaterina T1 - Discovery of Decision Models Complementary to Process Models T1 - Das Konstruieren von Entscheidungsmodellen als Ergänzung zu Prozessmodellen N2 - Business process management is an acknowledged asset for running an organization in a productive and sustainable way. One of the most important aspects of business process management, occurring on a daily basis at all levels, is decision making. In recent years, a number of decision management frameworks have appeared in addition to existing business process management systems. More recently, Decision Model and Notation (DMN) was developed by the OMG consortium with the aim of complementing the widely used Business Process Model and Notation (BPMN). One of the reasons for the emergence of DMN is the increasing interest in the evolving paradigm known as the separation of concerns. This paradigm states that modeling decisions complementary to processes reduces process complexity by externalizing decision logic from process models and importing it into a dedicated decision model. Such an approach increases the agility of model design and execution. This provides organizations with the flexibility to adapt to the ever increasing rapid and dynamic changes in the business ecosystem. The research gap, identified by us, is that the separation of concerns, recommended by DMN, prescribes the externalization of the decision logic of process models in one or more separate decision models, but it does not specify this can be achieved. The goal of this thesis is to overcome the presented gap by developing a framework for discovering decision models in a semi-automated way from information about existing process decision making. Thus, in this thesis we develop methodologies to extract decision models from: (1) control flow and data of process models that exist in enterprises; and (2) from event logs recorded by enterprise information systems, encapsulating day-to-day operations. Furthermore, we provide an extension of the methodologies to discover decision models from event logs enriched with fuzziness, a tool dealing with partial knowledge of the process execution information. All the proposed techniques are implemented and evaluated in case studies using real-life and synthetic process models and event logs. The evaluation of these case studies shows that the proposed methodologies provide valid and accurate output decision models that can serve as blueprints for executing decisions complementary to process models. Thus, these methodologies have applicability in the real world and they can be used, for example, for compliance checks, among other uses, which could improve the organization's decision making and hence it's overall performance. N2 - Geschäftsprozessmanagement ist eine anerkannte Strategie, um Unternehmen produktiv und nachhaltig zu führen. Einer der wichtigsten Faktoren des Geschäftsprozessmanagements ist die Entscheidungsfindung – tagtäglich und auf allen Ebenen. In den letzten Jahren wurden – zusätzlich zu existierenden Geschäftsprozessmanagementsystemen – eine Reihe von Frameworks zum Entscheidungsmanagement entwickelt. Um die weit verbreitete Business Process Model and Notation (BPMN) zu ergänzen, hat das OMG-Konsortium kürzlich die Decision Model and Notation (DMN) entwickelt. Einer der Treiber für die Entwicklung der DMN ist das wachsende Interesse an dem aufstrebenden Paradigma der “Separation of Concerns” (Trennung der Sichtweisen). Dieses Prinzip besagt, dass die Prozesskomplexität reduziert wird, wenn Entscheidungen komplementär zu den Prozessen modelliert werden, indem die Entscheidungslogik von Prozessmodellen entkoppelt und in ein dediziertes Entscheidungsmodel aufgenommen wird. Solch ein Ansatz erhöht die Agilität von Modelentwurf und –ausführung und bietet Unternehmen so die Flexibilität, auf die stetig zunehmenden, rasanten Veränderungen in der Unternehmenswelt zu reagieren. Während die DMN die Trennung der Belange empfiehlt und die Entkopplung der Entscheidungslogik von den Prozessmodellen vorschreibt, gibt es bisher keine Spezifikation, wie dies erreicht werden kann. Diese Forschungslücke ist der Ausgangspunkt der vorliegenden Arbeit. Das Ziel dieser Doktorarbeit ist es, die beschriebene Lücke zu füllen und ein Framework zur halbautomatischen Konstruktion von Entscheidungsmodellen zu entwickeln, basierend auf Informationen über existierende Prozessentscheidungsfindung. In dieser Arbeit werden die entwickelten Methoden zur Entkopplung von Entscheidungsmodellen dargestellt. Die Extraktion der Modelle basiert auf folgenden Eingaben: (1) Kontrollfluss und Daten aus Prozessmodellen, die in Unternehmen existieren; und (2) von Unternehmensinformationssystemen aufgezeichnete Ereignisprotokolle der Tagesgeschäfte. Außerdem stellen wir eine Erweiterung der Methode vor, die es ermöglicht, auch in von Unschärfe geprägten Ereignisprotokollen Entscheidungsmodelle zu entdecken. Hier wird mit Teilwissen über die Prozessausführung gearbeitet. Alle vorgestellten Techniken wurden implementiert und in Fallstudien evaluiert – basierend auf realen und künstlichen Prozessmodellen, sowie auf Ereignisprotokollen. Die Evaluierung der Fallstudien zeigt, dass die vorgeschlagenen Methoden valide und akkurate Entscheidungsmodelle produzieren, die als Blaupause für das Vollziehen von Entscheidungen dienen können und die Prozessmodelle ergänzen. Demnach sind die vorgestellten Methoden in der realenWelt anwendbar und können beispielsweise für Übereinstimmungskontrollen genutzt werden, was wiederum die Entscheidungsfindung in Unternehmen und somit deren Gesamtleistung verbessern kann. KW - business process management KW - decision management KW - process models KW - decision models KW - decision mining KW - Geschäftsprozessmanagement KW - Entscheidungsmanagement KW - Entscheidungsfindung KW - Entscheidungsmodelle KW - Prozessmodelle Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-410020 ER - TY - THES A1 - Benson, Lawrence T1 - Efficient state management with persistent memory N2 - Efficiently managing large state is a key challenge for data management systems. Traditionally, state is split into fast but volatile state in memory for processing and persistent but slow state on secondary storage for durability. Persistent memory (PMem), as a new technology in the storage hierarchy, blurs the lines between these states by offering both byte-addressability and low latency like DRAM as well persistence like secondary storage. These characteristics have the potential to cause a major performance shift in database systems. Driven by the potential impact that PMem has on data management systems, in this thesis we explore their use of PMem. We first evaluate the performance of real PMem hardware in the form of Intel Optane in a wide range of setups. To this end, we propose PerMA-Bench, a configurable benchmark framework that allows users to evaluate the performance of customizable database-related PMem access. Based on experimental results obtained with PerMA-Bench, we discuss findings and identify general and implementation-specific aspects that influence PMem performance and should be considered in future work to improve PMem-aware designs. We then propose Viper, a hybrid PMem-DRAM key-value store. Based on PMem-aware access patterns, we show how to leverage PMem and DRAM efficiently to design a key database component. Our evaluation shows that Viper outperforms existing key-value stores by 4–18x for inserts while offering full data persistence and achieving similar or better lookup performance. Next, we show which changes must be made to integrate PMem components into larger systems. By the example of stream processing engines, we highlight limitations of current designs and propose a prototype engine that overcomes these limitations. This allows our prototype to fully leverage PMem's performance for its internal state management. Finally, in light of Optane's discontinuation, we discuss how insights from PMem research can be transferred to future multi-tier memory setups by the example of Compute Express Link (CXL). Overall, we show that PMem offers high performance for state management, bridging the gap between fast but volatile DRAM and persistent but slow secondary storage. Although Optane was discontinued, new memory technologies are continuously emerging in various forms and we outline how novel designs for them can build on insights from existing PMem research. N2 - Die effiziente Verwaltung großer Zustände ist eine zentrale Herausforderung für Datenverwaltungssysteme. Traditionell wird der Zustand in einen schnellen, aber flüchtigen Zustand im Speicher für die Verarbeitung und einen persistenten, aber langsamen Zustand im Sekundärspeicher für die Speicherung unterteilt. Persistenter Speicher (PMem), eine neue Technologie in der Speicherhierarchie, lässt die Grenzen zwischen diesen Zuständen verschwimmen, indem er sowohl Byte-Adressierbarkeit und geringe Latenz wie DRAM als auch Persistenz wie Sekundärspeicher bietet. Diese Eigenschaften haben das Potenzial, die Leistung von Datenbanksystemen grundlegend zu verändern. Aufgrund der potenziellen Auswirkungen, die PMem auf Datenverwaltungssysteme hat, untersuchen wir in dieser Arbeit ihre Verwendung von PMem. Zunächst evaluieren wir die Leistung von echter PMem-Hardware in Form von Intel Optane in einer Vielzahl von Konfigurationen. Zu diesem Zweck stellen wir PerMA-Bench vor, ein konfigurierbares Benchmark-Framework, mit dem Benutzer die Leistung von anpassbaren datenbankbezogenen PMem-Zugriffen untersuchen können. Auf der Grundlage der mit PerMA-Bench erzielten experimentellen Ergebnisse diskutieren wir unsere Erkenntnisse und identifizieren allgemeine und implementierungsspezifische Aspekte, die die PMem-Leistung beeinflussen und in zukünftigen Arbeiten berücksichtigt werden sollten, um PMem-fähige Designs zu verbessern. Anschließend präsentieren wir Viper, einen hybriden PMem-DRAM Key-Value-Store. Basierend auf PMem-bewussten Zugriffsmustern zeigen wir, wie PMem und DRAM effizient genutzt werden können, um eine wichtige Datenbankkomponente zu entwickeln. Unsere Evaluierung zeigt, dass Viper bestehende Key-Value-Stores bei Einfügungen um 4- bis 18-mal übertrifft, während er gleichzeitig vollständige Datenpersistenz bietet und ähnliche oder bessere Lookup-Leistung erzielt. Als nächstes zeigen wir, welche Änderungen vorgenommen werden müssen, um PMem-Komponenten in größere Systeme zu integrieren. Am Beispiel von Datenstromverarbeitungssystemen zeigen wir die Einschränkungen aktueller Designs auf und stellen einen Prototyp eines Systems vor, das diese Einschränkungen überwindet. Dadurch kann unser Prototyp die Leistung von PMem für die interne Zustandsverwaltung voll ausnutzen. Schließlich erörtern wir angesichts der Abkündigung von Optane, wie Erkenntnisse aus der PMem-Forschung am Beispiel von Compute Express Link (CXL) auf künftige mehrstufige Speicher-Setups übertragen werden können. Insgesamt zeigen wir, dass PMem eine hohe Leistungsfähigkeit für die Zustandsverwaltung bietet und die Lücke zwischen schnellem, aber flüchtigem DRAM und beständigem, aber langsamem Sekundärspeicher schließt. Obwohl Optane eingestellt wurde, entstehen ständig neue Speichertechnologien in verschiedenen Formen, und wir skizzieren, wie neuartige Entwürfe für sie auf den Erkenntnissen aus der bestehenden PMem-Forschung aufbauen können. KW - persistent memory KW - pmem KW - database KW - data management KW - state management KW - Datenverwaltung KW - Datenbank KW - persistenter Speicher KW - pmem KW - Zustandsverwaltung Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-625637 ER - TY - THES A1 - Bin Tareaf, Raad T1 - Social media based personality prediction models T1 - Social Media-basierte Persönlichkeitsvorhersage Modelle N2 - Individuals have an intrinsic need to express themselves to other humans within a given community by sharing their experiences, thoughts, actions, and opinions. As a means, they mostly prefer to use modern online social media platforms such as Twitter, Facebook, personal blogs, and Reddit. Users of these social networks interact by drafting their own statuses updates, publishing photos, and giving likes leaving a considerable amount of data behind them to be analyzed. Researchers recently started exploring the shared social media data to understand online users better and predict their Big five personality traits: agreeableness, conscientiousness, extraversion, neuroticism, and openness to experience. This thesis intends to investigate the possible relationship between users’ Big five personality traits and the published information on their social media profiles. Facebook public data such as linguistic status updates, meta-data of likes objects, profile pictures, emotions, or reactions records were adopted to address the proposed research questions. Several machine learning predictions models were constructed with various experiments to utilize the engineered features correlated with the Big 5 Personality traits. The final predictive performances improved the prediction accuracy compared to state-of-the-art approaches, and the models were evaluated based on established benchmarks in the domain. The research experiments were implemented while ethical and privacy points were concerned. Furthermore, the research aims to raise awareness about privacy between social media users and show what third parties can reveal about users’ private traits from what they share and act on different social networking platforms. In the second part of the thesis, the variation in personality development is studied within a cross-platform environment such as Facebook and Twitter platforms. The constructed personality profiles in these social platforms are compared to evaluate the effect of the used platforms on one user’s personality development. Likewise, personality continuity and stability analysis are performed using two social media platforms samples. The implemented experiments are based on ten-year longitudinal samples aiming to understand users’ long-term personality development and further unlock the potential of cooperation between psychologists and data scientists. N2 - Menschen haben das Bedürfnis, sich anderen Menschen innerhalb einer bestimmten Gemeinschaft mitzuteilen, indem sie ihre Erfahrungen, Gedanken, Handlungen und Meinungen teilen. Zu diesem Zweck nutzen sie am liebsten moderne Online-Plattformen für soziale Medien wie Twitter, Facebook, persönliche Blogs und Reddit. Die Nutzer dieser sozialen Netzwerke interagieren, indem sie ihre eigenen Status-Updates verfassen, Fotos veröffentlichen und Likes vergeben und dabei eine beträchtliche Menge an Daten hinterlassen, die analysiert werden können. Forscher haben vor kurzem damit begonnen, die in den sozialen Medien geteilten Daten zu untersuchen, um die Online-Nutzer besser zu verstehen und ihre Big-Five-Persönlichkeitseigenschaften vorherzusagen: Verträglichkeit, Gewissenhaftigkeit, Extraversion, Neurotizismus und Offenheit für Erfahrungen. In dieser Arbeit soll der mögliche Zusammenhang zwischen den Big Five Persönlichkeitsmerkmalen der Nutzer und den in ihren Social-Media-Profilen veröffentlichten Informationen untersucht werden. Öffentliche Facebook-Daten wie sprachliche Status-Updates, Metadaten von Likes, Profilbilder, Emotionen oder Reaktionsaufzeichnungen wurden zur Beantwortung der vorgeschlagenen Forschungsfragen herangezogen. Es wurden mehrere Modelle des maschinellen Lernens mit verschiedenen Experimenten erstellt, um die entwickelten Merkmale zu nutzen, die mit den Big 5 Persönlichkeitsmerkmalen korrelieren. Die endgültigen Vorhersageleistungen verbesserten die Vorhersagegenauigkeit im Vergleich zu modernsten Ansätzen, und die Modelle wurden auf der Grundlage etablierter Benchmarks in diesem Bereich bewertet. Die Forschungsexperimente wurden unter Berücksichtigung ethischer Aspekte und des Datenschutzes durchgeführt. Darüber hinaus zielt die Forschung darauf ab, das Bewusstsein für die Privatsphäre von Nutzern sozialer Medien zu schärfen und zu zeigen, was Dritte über die privaten Eigenschaften von Nutzern aus dem, was sie auf verschiedenen sozialen Netzwerkplattformen teilen und tun, herausfinden können. Im zweiten Teil der Arbeit werden die Unterschiede in der Persönlichkeitsentwicklung in einer plattformübergreifenden Umgebung wie Facebook und Twitter untersucht. Die konstruierten Persönlichkeitsprofile in diesen sozialen Plattformen werden verglichen, um die Auswirkungen der verwendeten Plattformen auf die Persönlichkeitsentwicklung eines Nutzers zu bewerten. Ebenso werden Persönlichkeitskontinuität und -stabilität anhand von zwei Social Media Plattformen untersucht. Die durchgeführten Experimente basieren auf zehnjährigen Längsschnittstichproben mit dem Ziel, die langfristige Persönlichkeitsentwicklung der Nutzer zu verstehen und das Potenzial der Zusammenarbeit zwischen Psychologen und Datenwissenschaftlern weiter zu erschließen. KW - social media KW - online personality KW - social networking KW - Online-Persönlichkeit KW - sozialen Medien KW - soziales Netzwerk Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-549142 ER - TY - THES A1 - Buschmann, Stefan T1 - A software framework for GPU-based geo-temporal visualization techniques T1 - Ein Software-Framework für GPU-basierte räumlich-zeitliche Visualisierungstechniken N2 - Räumlich-zeitliche Daten sind Daten, welche sowohl einen Raum- als auch einen Zeitbezug aufweisen. So können beispielsweise Zeitreihen von Geodaten, thematische Karten die sich über die Zeit verändern, oder Bewegungsaufzeichnungen von sich bewegenden Objekten als räumlich-zeitliche Daten aufgefasst werden. In der heutigen automatisierten Welt gibt es eine wachsende Anzahl von Datenquellen, die beständig räumlich-zeitliche Daten generieren. Hierzu gehören beispielsweise Verkehrsüberwachungssysteme, die Bewegungsdaten von Menschen oder Fahrzeugen aufzeichnen, Fernerkundungssysteme, welche regelmäßig unsere Umgebung scannen und digitale Abbilder wie z.B. Stadt- und Landschaftsmodelle erzeugen, sowie Sensornetzwerke in unterschiedlichsten Anwendungsgebieten, wie z.B. der Logistik, der Verhaltensforschung von Tieren, oder der Klimaforschung. Zur Analyse räumlich-zeitlicher Daten werden neben der automatischen Analyse mittels statistischer Methoden und Data-Mining auch explorative Methoden angewendet, welche auf der interaktiven Visualisierung der Daten beruhen. Diese Methode der Analyse basiert darauf, dass Anwender in Form interaktiver Visualisierung die Daten explorieren können, wodurch die menschliche Wahrnehmung sowie das Wissen der User genutzt werden, um Muster zu erkennen und dadurch einen Einblick in die Daten zu erlangen. Diese Arbeit beschreibt ein Software-Framework für die Visualisierung räumlich-zeitlicher Daten, welches GPU-basierte Techniken beinhaltet, um eine interaktive Visualisierung und Exploration großer räumlich-zeitlicher Datensätze zu ermöglichen. Die entwickelten Techniken umfassen Datenhaltung, Prozessierung und Rendering und ermöglichen es, große Datenmengen in Echtzeit zu prozessieren und zu visualisieren. Die Hauptbeiträge der Arbeit umfassen: - Konzept und Implementierung einer GPU-zentrierten Visualisierungspipeline. Die beschriebenen Techniken basieren auf dem Konzept einer GPU-zentrierten Visualisierungspipeline, in welcher alle Stufen -- Prozessierung,Mapping, Rendering -- auf der GPU ausgeführt werden. Bei diesem Konzept werden die räumlich-zeitlichen Daten direkt im GPU-Speicher abgelegt. Während des Rendering-Prozesses werden dann mittels Shader-Programmen die Daten prozessiert, gefiltert, ein Mapping auf visuelle Attribute vorgenommen, und schließlich die Geometrien für die Visualisierung erzeugt. Datenprozessierung, Filtering und Mapping können daher in Echtzeit ausgeführt werden. Dies ermöglicht es Usern, die Mapping-Parameter sowie den gesamten Visualisierungsprozess interaktiv zu steuern und zu kontrollieren. - Interaktive Visualisierung attributierter 3D-Trajektorien. Es wurde eine Visualisierungsmethode für die interaktive Exploration einer großen Anzahl von 3D Bewegungstrajektorien entwickelt. Die Trajektorien werden dabei innerhalb einer virtuellen geographischen Umgebung in Form von einfachen Geometrien, wie Linien, Bändern, Kugeln oder Röhren dargestellt. Durch interaktives Mapping können Attributwerte der Trajektorien oder einzelner Messpunkte auf visuelle Eigenschaften abgebildet werden. Hierzu stehen Form, Höhe, Größe, Farbe, Textur, sowie Animation zur Verfügung. Mithilfe dieses dynamischen Mappings wurden außerdem verschiedene Visualisierungsmethoden implementiert, wie z.B. eine Focus+Context-Visualisierung von Trajektorien mithilfe von interaktiven Dichtekarten, sowie einer Space-Time-Cube-Visualisierung zur Darstellung des zeitlichen Ablaufs einzelner Bewegungen. - Interaktive Visualisierung geographischer Netzwerke. Es wurde eine Visualisierungsmethode zur interaktiven Exploration geo-referenzierter Netzwerke entwickelt, welche die Visualisierung von Netzwerken mit einer großen Anzahl von Knoten und Kanten ermöglicht. Um die Analyse von Netzwerken verschiedener Größen und in unterschiedlichen Kontexten zu ermöglichen, stehen mehrere virtuelle geographische Umgebungen zur Verfügung, wie bspw. ein virtueller 3D-Globus, als auch 2D-Karten mit unterschiedlichen geographischen Projektionen. Zur interaktiven Analyse dieser Netzwerke stehen interaktive Tools wie Filterung, Mapping und Selektion zur Verfügung. Des weiteren wurden Visualisierungsmethoden für verschiedene Arten von Netzwerken, wie z.B. 3D-Netzwerke und zeitlich veränderliche Netzwerke, implementiert. Zur Demonstration des Konzeptes wurden interaktive Tools für zwei unterschiedliche Anwendungsfälle entwickelt. Das erste beinhaltet die Visualisierung attributierter 3D-Trajektorien, welche die Bewegungen von Flugzeugen um einen Flughafen beschreiben. Es ermöglicht Nutzern, die Trajektorien von ankommenden und startenden Flugzeugen über den Zeitraum eines Monats interaktiv zu explorieren und zu analysieren. Durch Verwendung der interaktiven Visualisierungsmethoden für 3D-Trajektorien und interaktiven Dichtekarten können Einblicke in die Daten gewonnen werden, wie beispielsweise häufig genutzte Flugkorridore, typische sowie untypische Bewegungsmuster, oder ungewöhnliche Vorkommnisse wie Fehlanflüge. Der zweite Anwendungsfall beinhaltet die Visualisierung von Klimanetzwerken, welche geographischen Netzwerken in der Klimaforschung darstellen. Klimanetzwerke repräsentieren die Dynamiken im Klimasystem durch eine Netzwerkstruktur, die die statistische Beziehungen zwischen Orten beschreiben. Das entwickelte Tool ermöglicht es Analysten, diese großen Netzwerke interaktiv zu explorieren und dadurch die Struktur des Netzwerks zu analysieren und mit den geographischen Daten in Beziehung zu setzen. Interaktive Filterung und Selektion ermöglichen es, Muster in den Daten zu identifizieren, und so bspw. Cluster in der Netzwerkstruktur oder Strömungsmuster zu erkennen. N2 - Spatio-temporal data denotes a category of data that contains spatial as well as temporal components. For example, time-series of geo-data, thematic maps that change over time, or tracking data of moving entities can be interpreted as spatio-temporal data. In today's automated world, an increasing number of data sources exist, which constantly generate spatio-temporal data. This includes for example traffic surveillance systems, which gather movement data about human or vehicle movements, remote-sensing systems, which frequently scan our surroundings and produce digital representations of cities and landscapes, as well as sensor networks in different domains, such as logistics, animal behavior study, or climate research. For the analysis of spatio-temporal data, in addition to automatic statistical and data mining methods, exploratory analysis methods are employed, which are based on interactive visualization. These analysis methods let users explore a data set by interactively manipulating a visualization, thereby employing the human cognitive system and knowledge of the users to find patterns and gain insight into the data. This thesis describes a software framework for the visualization of spatio-temporal data, which consists of GPU-based techniques to enable the interactive visualization and exploration of large spatio-temporal data sets. The developed techniques include data management, processing, and rendering, facilitating real-time processing and visualization of large geo-temporal data sets. It includes three main contributions: - Concept and Implementation of a GPU-Based Visualization Pipeline. The developed visualization methods are based on the concept of a GPU-based visualization pipeline, in which all steps -- processing, mapping, and rendering -- are implemented on the GPU. With this concept, spatio-temporal data is represented directly in GPU memory, using shader programs to process and filter the data, apply mappings to visual properties, and finally generate the geometric representations for a visualization during the rendering process. Data processing, filtering, and mapping are thereby executed in real-time, enabling dynamic control over the mapping and a visualization process which can be controlled interactively by a user. - Attributed 3D Trajectory Visualization. A visualization method has been developed for the interactive exploration of large numbers of 3D movement trajectories. The trajectories are visualized in a virtual geographic environment, supporting basic geometries such as lines, ribbons, spheres, or tubes. Interactive mapping can be applied to visualize the values of per-node or per-trajectory attributes, supporting shape, height, size, color, texturing, and animation as visual properties. Using the dynamic mapping system, several kind of visualization methods have been implemented, such as focus+context visualization of trajectories using interactive density maps, and space-time cube visualization to focus on the temporal aspects of individual movements. - Geographic Network Visualization. A method for the interactive exploration of geo-referenced networks has been developed, which enables the visualization of large numbers of nodes and edges in a geographic context. Several geographic environments are supported, such as a 3D globe, as well as 2D maps using different map projections, to enable the analysis of networks in different contexts and scales. Interactive filtering, mapping, and selection can be applied to analyze these geographic networks, and visualization methods for specific types of networks, such as coupled 3D networks or temporal networks have been implemented. As a demonstration of the developed visualization concepts, interactive visualization tools for two distinct use cases have been developed. The first contains the visualization of attributed 3D movement trajectories of airplanes around an airport. It allows users to explore and analyze the trajectories of approaching and departing aircrafts, which have been recorded over the period of a month. By applying the interactive visualization methods for trajectory visualization and interactive density maps, analysts can derive insight from the data, such as common flight paths, regular and irregular patterns, or uncommon incidents such as missed approaches on the airport. The second use case involves the visualization of climate networks, which are geographic networks in the climate research domain. They represent the dynamics of the climate system using a network structure that expresses statistical interrelationships between different regions. The interactive tool allows climate analysts to explore these large networks, analyzing the network's structure and relating it to the geographic background. Interactive filtering and selection enables them to find patterns in the climate data and identify e.g. clusters in the networks or flow patterns. KW - computer graphics KW - visualization KW - visual analytics KW - Computergrafik KW - Visualisierung KW - Visual Analytics Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-443406 ER - TY - THES A1 - Che, Xiaoyin T1 - E-lecture material enhancement based on automatic multimedia analysis T1 - Online-Vorlesung Materialverbesserung basierend auf automatischer Multimedia-Analyse N2 - In this era of high-speed informatization and globalization, online education is no longer an exquisite concept in the ivory tower, but a rapidly developing industry closely relevant to people's daily lives. Numerous lectures are recorded in form of multimedia data, uploaded to the Internet and made publicly accessible from anywhere in this world. These lectures are generally addressed as e-lectures. In recent year, a new popular form of e-lectures, the Massive Open Online Courses (MOOCs), boosts the growth of online education industry and somehow turns "learning online" into a fashion. As an e-learning provider, besides to keep improving the quality of e-lecture content, to provide better learning environment for online learners is also a highly important task. This task can be preceded in various ways, and one of them is to enhance and upgrade the learning materials provided: e-lectures could be more than videos. Moreover, this process of enhancement or upgrading should be done automatically, without giving extra burdens to the lecturers or teaching teams, and this is the aim of this thesis. The first part of this thesis is an integrated framework of multi-lingual subtitles production, which can help online learners penetrate the language barrier. The framework consists of Automatic Speech Recognition (ASR), Sentence Boundary Detection (SBD) and Machine Translation (MT), among which the proposed SBD solution is major technical contribution, building on Deep Neural Network (DNN) and Word Vector (WV) and achieving state-of-the-art performance. Besides, a quantitative evaluation with dozens of volunteers is also introduced to measure how these auto-generated subtitles could actually help in context of e-lectures. Secondly, a technical solution "TOG" (Tree-Structure Outline Generation) is proposed to extract textual content from the displaying slides recorded in video and re-organize them into a hierarchical lecture outline, which may serve in multiple functions, such like preview, navigation and retrieval. TOG runs adaptively and can be roughly divided into intra-slide and inter-slides phases. Table detection and lecture video segmentation can be implemented as sub- or post-application in these two phases respectively. Evaluation on diverse e-lectures shows that all the outlines, tables and segments achieved are trustworthily accurate. Based on the subtitles and outlines previously created, lecture videos can be further split into sentence units and slide-based segment units. A lecture highlighting process is further applied on these units, in order to capture and mark the most important parts within the corresponding lecture, just as what people do with a pen when reading paper books. Sentence-level highlighting depends on the acoustic analysis on the audio track, while segment-level highlighting focuses on exploring clues from the statistical information of related transcripts and slide content. Both objective and subjective evaluations prove that the proposed lecture highlighting solution is with decent precision and welcomed by users. All above enhanced e-lecture materials have been already implemented in actual use or made available for implementation by convenient interfaces. N2 - In der Ära der mit Hochgeschwindigkeit digitalisierten und globalisierten Welt ist die Online-Bildung nicht mehr ein kunstvoller Begriff im Elfenbeinturm, sondern eine sich schnell entwickelnde Industrie, die für den Alltag der Menschen eine wichtige Rolle spielt. Zahlreiche Vorlesungen werden digital aufgezeichnet und im Internet Online zur Verfügung gestellt, so dass sie vom überall auf der Welt erreichbar und zugänglich sind. Sie werden als e-Vorlesungen bezeichnet. Eine neue Form der Online-Bildung namens „Massive Open Online Courses“ (MOOCs), welche zum Trend seit dem letzten Jahr geworden ist, verstärket und beschleunigt die Entwicklung des Online-Lernens. Ein Online-Lernen Anbieter hat nicht nur die Qualität des Lerninhaltes sondern auch die Lernumgebung und die Lerntools ständig zu verbessern. Eine diese Verbesserungen ist die Form, in der das Lernmaterial aktualisiert und angeboten wird. Das Ziel dieser Dissertation ist die Untersuchung und die Entwicklung von Tools, die der Prozess der Verbesserung und Aktualisierung des Lernmaterials automatisch durchführen. Die entwickelten Tools sollen das Lehrerteam entlasten und seine Arbeit beschleunigen. Der erste Teil der Dissertation besteht aus einem integrierten Framework für die Generierung von mehrsprachigen Untertiteln. Dies kann den Online-Lernern ermöglichen, die Sprachbarriere beim Lernen zu überwinden. Das Framework besteht aus „Automatic Speech Recognition“ (ASR), „Sentence Boundary Detection“ (SBD), und „Machine Translation“ (MT). SBD ist realisiert durch die Anwendung von „Deep Neural Network“ (DNN) und „Word Vector“ (WV), wodurch die Genauigkeit der Stand der Technik erreicht ist. Außerdem quantitative Bewertung durch Dutzende von Freiwilligen ist also eingesetzt, um zu evaluieren, wie diese automaisch generierten Untertiteln in den E-Vorlesungen helfen können. Im zweiten Teil ist eine technische Lösung namens „Tree-Structure Outline Generation“ (TOG) für die Extraktion des textuellen Inhalts aus den Folien präsentiert. Der extrahierten Informationen werden dann in strukturierter Form dargestellt, welche die Outline der Vorlesung wiederspiegelt. Diese Darstellung kann verschiedenen Funktionen dienen, wie dem Vorschau, der Navigation, und dem Abfragen des Inhaltes. TOG ist adaptiv und kann grob in Intra-Folie und Inter-Folien Phasen unterteilt werden. Für diese Phasen, Tabellenerkennung und die Segmentierung von Vorlesungsvideo können als Sub- oder Post-Applikation jeweils implementiert werden. Die höhere Genauigkeit der extrahierten Outline, der Tabellen, und der Segmenten wird experimentell durch die Anwendung auf verschieden e-Vorlesungen gezeigt. Basierend auf den Untertiteln und dem Outline, die in vorher generiert wurden, Vorlesungsvideos können weiter in Satzeinheiten und Folien-basierten Segmenteinheiten gesplittet werden. Ein Hervorhebungsprozess wird weiter auf diese Einheiten angewendet, um die wichtigsten Teile innerhalb der entsprechenden Vorlesung zu erfassen und zu markieren. Dies entspricht genau, was die Lerner mit einem Stift beim Lesen von Büchern machen. Die Satz-Level-Hervorhebung hängt von der akustischen Analyse auf der Audiospur ab, während die Segment-Level-Hervorhebung auf die Erforschung von Hinweisen aus den statistischen Informationen der verwandten Transkripte und des Folieninhalts fokussiert. Die objektiven und subjektiven Auswertungen zeigen, dass die vorgeschlagene Vorlesungsvorhebungslösung mit anständiger Präzision und von den Benutzern akzeptiert wird. All diese Methoden für die Verbesserung der Online-Materialien wurden bereits für den Einsatz implementiert und durch komfortable Schnittstellen zur Verfügung gestellt. KW - E-Learning KW - deep learning KW - NLP KW - document analysis KW - E-Learning KW - Deep Learning KW - natürliche Sprachverarbeitung KW - Dokument Analyse Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-408224 ER - TY - THES A1 - Cheng, Lung-Pan T1 - Human actuation T1 - Menschlicher Aktuator N2 - Ever since the conception of the virtual reality headset in 1968, many researchers have argued that the next step in virtual reality is to allow users to not only see and hear, but also feel virtual worlds. One approach is to use mechanical equipment to provide haptic feedback, e.g., robotic arms, exoskeletons and motion platforms. However, the size and the weight of such mechanical equipment tends to be proportional to its target’s size and weight, i.e., providing human-scale haptic feedback requires human-scale equipment, often restricting them to arcades and lab environments. The key idea behind this dissertation is to bypass mechanical equipment by instead leveraging human muscle power. We thus create software systems that orchestrate humans in doing such mechanical labor—this is what we call human actuation. A potential benefit of such systems is that humans are more generic, flexible, and versatile than machines. This brings a wide range of haptic feedback to modern virtual reality systems. We start with a proof-of-concept system—Haptic Turk, focusing on delivering motion experiences just like a motion platform. All Haptic Turk setups consist of a user who is supported by one or more human actuators. The user enjoys an interactive motion simulation such as a hang glider experience, but the motion is generated by those human actuators who manually lift, tilt, and push the user’s limbs or torso. To get the timing and force right, timed motion instructions in a format familiar from rhythm games are generated by the system. Next, we extend the concept of human actuation from 3-DoF to 6-DoF virtual reality where users have the freedom to walk around. TurkDeck tackles this problem by orchestrating a group of human actuators to reconfigure a set of passive props on the fly while the user is progressing in the virtual environment. TurkDeck schedules human actuators by their distances from the user, and instructs them to reconfigure the props to the right place on the right time using laser projection and voice output. Our studies in Haptic Turk and TurkDeck showed that human actuators enjoyed the experience but not as much as users. To eliminate the need of dedicated human actuators, Mutual Turk makes everyone a user by exchanging mechanical actuation between two or more users. Mutual Turk’s main functionality is that it orchestrates the users so as to actuate props at just the right moment and with just the right force to produce the correct feedback in each other's experience. Finally, we further eliminate the need of another user, making human actuation applicable to single-user experiences. iTurk makes the user constantly reconfigure and animate otherwise passive props. This allows iTurk to provide virtual worlds with constantly varying or even animated haptic effects, even though the only animate entity present in the system is the user. Our demo experience features one example each of iTurk’s two main types of props, i.e., reconfigurable props (the foldable board from TurkDeck) and animated props (the pendulum). We conclude this dissertation by summarizing the findings of our explorations and pointing out future directions. We discuss the development of human actuation compare to traditional machine actuation, the possibility of combining human and machine actuators and interaction models that involve more human actuators. N2 - Seit der Konzeption des Virtual-Reality-Headsets im Jahr 1968 argumentieren Forscher, der nächste Schritt in der virtuellen Realität ist nicht nur zu sehen und zu hören, sondern in virtuelle Welten auch fühlen zu können. Ein Ansatz solch haptisches Feedback zu geben ist die Verwendung mechanischer Ausrüstung, etwa Roboterarme, Exoskelette und Bewegungsplattformen. Jedoch sind die Größe und das Gewicht solcher Ausrüstung proportional zur Größe und Gewicht der Person, d. h. haptisches Feedback für einen Menschen erfordert Ausrüstung mit Größe und Gewicht eines Menschen. Dieses Ausmaß an Gerätschaften ist oft limitiert auf Arkaden oder Laborumgebungen. Der Schlüsselgedanke dieser Dissertation besteht darin, mechanische Geräte zu umgehen und stattdessen menschliche Muskelkraft zu nutzen. Wir erstellen Softwaresystem, die Menschen bei mechanischen Arbeiten orchestrieren, um anderen Menschen haptisches Feedback zu geben. Dies nennen wir „Human Actuation“ – menschliche Aktuierung. Ein möglicher Vorteil solcher Systeme ist es, dass Menschen generischer, flexibler und vielseitiger sind als gängige mechanische Ausrüstung. Dies bringt eine neue Bandbreite von haptischen Feedbackmöglichkeiten in moderne Virtual-Reality-Systeme. Wir beginnen mit einem Proof-of-Concept-System– Haptic Turk, mit Schwerpunkt auf die Bewegungserlebnisse, die eine solche menschliche Bewegungsplattform liefert. Alle Haptic Turk Konfigurationen bestehen aus einem Nutzer, sowie einem oder mehreren Menschen, die den Nutzer unterstützen, den Aktuatoren. Der Nutzer genießt eine interaktive Bewegungssimulation wie zum Beispiel die Simulation eines Hängegleiters, jedoch wird die Bewegung von Menschen erzeugt, die die Gliedmaßen des Benutzers manuell heben, kippen und drücken. Um das Timing einzuhalten, folgen Sie den Anweisungen des Systems. Ein aus Rhythmusspielen bekanntes Format wird dabei dynamisch von dem System erzeugt. Als nächstes erweitern wir das Konzept von „Human Actuation“ um 3-DoF auf 6-DoF Virtual Reality. Das heißt, Nutzer haben nun die Freiheit in der virtuellen Welt umherzugehen. TurkDeck löst dieses Problem, indem es eine Gruppe menschlicher Aktuatoren orchestriert, die eine Reihe von Requisiten rekonfigurieren, die der Nutzer fühlen kann, während er sich in der virtuellen Umgebung fortbewegt. TurkDeck plant die Positionierung der Menschen und weist sie zur richtigen Zeit an, die Requisiten an den richtigen Ort zu stellen. TurkDeck erreicht dies mit Hilfe von Laserprojektion und einer Anweisung gebender synthetischen Stimme. Unsere Studien zu Haptic Turk und TurkDeck zeigen, dass menschliche Aktuatoren ihre Erfahrung zwar genießen, jedoch in dem Ausmaß wie der Nutzer selbst. Um menschliche Aktuatoren mehr einzubeziehen macht Mutual Turk aus jedem Aktuator einen Nutzer, d.h. mehrere Nutzer geben sich gegenseitig haptisches Feedback. Die Hauptfunktion von Mutual Turk besteht darin, dass es seine Nutzer so orchestriert, dass sie die richtigen Requisiten im richtigen Moment und im richtigen Ausmaß betätigen, um so das richtige Feedback in der Erfahrung des Anderen zu erzeugen. Schlussendlich eliminieren wir die Notwendigkeit anderer Nutzer gänzlich und ermöglichen Erfahrungen für Einzelnutzer. iTurk lässt seinen Nutzer passive Requisiten neu konfigurieren und animieren. Dadurch kann iTurk virtuelle Welten mit stetig wechselnden Möglichkeiten bereitstellen oder sogar haptische Effekte generieren, obwohl jede Bewegung im System vom Nutzer selbst ausgelöst wird. Unsere Demo-Applikation verfügt über je ein Beispiel der von iTurk ermöglichten zwei Haupttypen von Requisiten - rekonfigurierbare Requisiten (eine faltbare Tafel aus TurkDeck) und animierter Requisiten (ein Pendel). Wir schließen die Dissertation mit Verweisen auf mögliche Forschungsrichtungen ab, die sich durch die präsentierten Systeme ergeben. Wir diskutieren „Human Actuation“ sowohl im Vergleich zu herkömmlichen mechanischen Geräten, aber auch in der Kombination, da sich mechanische Geräte und Menschen gegenseitig ergänzen können. Zudem erkunden wir mögliche Interaktionsmodelle, die sich durch das Einbeziehen von menschlichen Aktuatoren ergeben. KW - haptic feedback KW - Virtual Reality KW - motion and force KW - props KW - haptisches Feedback KW - virtuelle Realität KW - Bewegung KW - Requisit Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-418371 ER - TY - THES A1 - Chujfi-La-Roche, Salim T1 - Human Cognition and natural Language Processing in the Digitally Mediated Environment N2 - Organizations continue to assemble and rely upon teams of remote workers as an essential element of their business strategy; however, knowledge processing is particular difficult in such isolated, largely digitally mediated settings. The great challenge for a knowledge-based organization lies not in how individuals should interact using technology but in how to achieve effective cooperation and knowledge exchange. Currently more attention has been paid to technology and the difficulties machines have processing natural language and less to studies of the human aspect—the influence of our own individual cognitive abilities and preferences on the processing of information when interacting online. This thesis draws on four scientific domains involved in the process of interpreting and processing massive, unstructured data—knowledge management, linguistics, cognitive science, and artificial intelligence—to build a model that offers a reliable way to address the ambiguous nature of language and improve workers’ digitally mediated interactions. Human communication can be discouragingly imprecise and is characterized by a strong linguistic ambiguity; this represents an enormous challenge for the computer analysis of natural language. In this thesis, I propose and develop a new data interpretation layer for the processing of natural language based on the human cognitive preferences of the conversants themselves. Such a semantic analysis merges information derived both from the content and from the associated social and individual contexts, as well as the social dynamics that emerge online. At the same time, assessment taxonomies are used to analyze online comportment at the individual and community level in order to successfully identify characteristics leading to greater effectiveness of communication. Measurement patterns for identifying effective methods of individual interaction with regard to individual cognitive and learning preferences are also evaluated; a novel Cyber-Cognitive Identity (CCI)—a perceptual profile of an individual’s cognitive and learning styles—is proposed. Accommodation of such cognitive preferences can greatly facilitate knowledge management in the geographically dispersed and collaborative digital environment. Use of the CCI is proposed for cognitively labeled Latent Dirichlet Allocation (CLLDA), a novel method for automatically labeling and clustering knowledge that does not rely solely on probabilistic methods, but rather on a fusion of machine learning algorithms and the cognitive identities of the associated individuals interacting in a digitally mediated environment. Advantages include: a greater perspicuity of dynamic and meaningful cognitive rules leading to greater tagging accuracy and a higher content portability at the sentence, document, and corpus level with respect to digital communication. N2 - Zunehmend bauen Organisationen Telearbeit als zentrales Element ihrer Geschäftsstrategie auf. Allerdings führt die Wissensverarbeitung in solchen digital vermittelnden -weitegehend aber nicht interaktiv strukturierten- Kontexten zu Schwierigkeiten. Dabei liegt die wesentliche Herausforderung für wissensbasierte Organisationen nicht in der Frage, wie Individuen mithilfe von Technologien zusammenarbeiten sollten, sondern darin, wie effektiv die Zusammenarbeit und ein effektiver Wissensaustausch zu erreichen sind. Gegenwärtige Untersuchungen fokussieren weit mehr auf Technologien selbst als auf den menschlichen Voraussetzungen von kognitiven Fähigkeiten und Präferenzen bei der online basierten Zusammenarbeit. Genauso ist der Umstand noch nicht hinreichend berücksichtigt worden, dass Natural Language Processing (NLP) den generellen Begleiterscheinungen von Sprache wie Missverständnissen und Mehrdeutigkeiten unterworfen ist. Diese Arbeit setzt auf vier wissenschaftlichen Feldern auf, die in der Verarbeitung und Interpretation von großen, teils unstrukturierten Datenmengen wesentlich sind: Wissensmanagement, Kognitionswissenschaft, Linguistik und Künstliche Intelligenz. Auf dieser breiten Grundlage wird ein Modell angeboten, das auf verlässliche Art, den nicht-deterministischen Charakter von Sprache betont und vor diesem Hintergrund Verbesserungspotentiale digital gestützter Zusammenarbeit aufzeigt. Menschliche Kommunikation kann entmutigend unpräzise sein und ist von linguistischer Mehrdeutigkeit geprägt. Dies bildet eine wesentliche Herausforderung für die computertechnische Analyse natürlicher Sprache. In dieser Arbeit entwickle ich unter Berücksichtigung kognitiver Präferenzen von Gesprächspartnern den Vorschlag für einen neuen Interpretationsansatz von Daten. Im Rahmen dieser semantischen Analyse werden Informationen zusammengeführt, die sowohl den zu vermittelnden Inhalt als auch die damit verbundenen sozialen und individuellen Kontexte, sowie die Gruppendynamik im Online-Umfeld einbeziehen. Gleichzeitig werden Bewertungstaxonomien verwendet, um das Online-Verhalten sowohl auf individueller wie gruppendynamischer Ebene zu analysieren, um darin Merkmale für eine größere Effektivität der Kommunikation zu identifizieren. Es werden Muster zur Identifizierung und Messung wirksamer Methoden der Interaktion in Hinblick auf individuelle kognitive und lernpsychologische Präferenzen bewertet. Hierzu wird der Begriff einer Cyber-Cognitive Identity (CCI) vorgeschlagen, der unterschiedliche Wahrnehmungsprofile kognitiver und lernpsychologischer Stile verschiedener Individuen beschreibt. Die Bezugnahme auf solche kognitiven Präferenzen kann das Wissensmanagement in geografisch verteilten, kollaborativen digitalen Umgebungen erheblich erleichtern und damit das Wissensaustausch verbessern. Cognitive Labeled Latent Dirichlet Allocation (CLLDA) wird als generatives Wahrscheinlichkeitsmodell für die automatische Kennzeichnung und Clusterbildung von CCI-gewonnenen Profilen verwendet. Dabei dominieren methodologisch die Kognitionstypen gegenüber den Wahrscheinlichkeitsaspekten. Mit der Einführung und Weiterverarbeitung des CCI-Begriffs wird der bisherige Forschungsstand um ein fundiertes Verfahrensmodell erweitert, das eine Grundlage für sich potentiell anschließende Forschungsarbeiten und praktische Anwendungen bietet. KW - cognitive science KW - natural language processing KW - knowledge management KW - thinking styles KW - artificial intelligence KW - Kognitionswissenschaft KW - Verarbeitung natürlicher Sprache KW - Wissensmanagement KW - Denkstile KW - künstliche Intelligenz Y1 - 2020 ER - TY - THES A1 - Doskoč, Vanja T1 - Mapping restrictions in behaviourally correct learning N2 - In this thesis, we investigate language learning in the formalisation of Gold [Gol67]. Here, a learner, being successively presented all information of a target language, conjectures which language it believes to be shown. Once these hypotheses converge syntactically to a correct explanation of the target language, the learning is considered successful. Fittingly, this is termed explanatory learning. To model learning strategies, we impose restrictions on the hypotheses made, for example requiring the conjectures to follow a monotonic behaviour. This way, we can study the impact a certain restriction has on learning. Recently, the literature shifted towards map charting. Here, various seemingly unrelated restrictions are contrasted, unveiling interesting relations between them. The results are then depicted in maps. For explanatory learning, the literature already provides maps of common restrictions for various forms of data presentation. In the case of behaviourally correct learning, where the learners are required to converge semantically instead of syntactically, the same restrictions as in explanatory learning have been investigated. However, a similarly complete picture regarding their interaction has not been presented yet. In this thesis, we transfer the map charting approach to behaviourally correct learning. In particular, we complete the partial results from the literature for many well-studied restrictions and provide full maps for behaviourally correct learning with different types of data presentation. We also study properties of learners assessed important in the literature. We are interested whether learners are consistent, that is, whether their conjectures include the data they are built on. While learners cannot be assumed consistent in explanatory learning, the opposite is the case in behaviourally correct learning. Even further, it is known that learners following different restrictions may be assumed consistent. We contribute to the literature by showing that this is the case for all studied restrictions. We also investigate mathematically interesting properties of learners. In particular, we are interested in whether learning under a given restriction may be done with strongly Bc-locking learners. Such learners are of particular value as they allow to apply simulation arguments when, for example, comparing two learning paradigms to each other. The literature gives a rich ground on when learners may be assumed strongly Bc-locking, which we complete for all studied restrictions. N2 - In dieser Arbeit untersuchen wir das Sprachenlernen in der Formalisierung von Gold [Gol67]. Dabei stellt ein Lerner, dem nacheinander die volle Information einer Zielsprache präsentiert wird, Vermutungen darüber auf, welche Sprache er glaubt, präsentiert zu bekommen. Sobald diese Hypothesen syntaktisch zu einer korrekten Erklärung der Zielsprache konvergieren, wird das Lernen als erfolgreich angesehen. Dies wird passenderweise als erklärendes Lernen bezeichnet. Um Lernstrategien zu modellieren, werden den aufgestellten Hypothesen Einschränkungen auferlegt, zum Beispiel, dass die Vermutungen einem monotonen Verhalten folgen müssen. Auf diese Weise können wir untersuchen, welche Auswirkungen eine bestimmte Einschränkung auf das Lernen hat. In letzter Zeit hat sich die Literatur in Richtung Kartographie verlagert. Hier werden verschiedene, scheinbar nicht zusammenhängende Restriktionen einander gegenübergestellt, wodurch interessante Beziehungen zwischen ihnen aufgedeckt werden. Die Ergebnisse werden dann in so genannten Karten dargestellt. Für das erklärende Lernen gibt es in der Literatur bereits Karten geläufiger Einschränkungen für verschiedene Formen der Datenpräsentation. Im Falle des verhaltenskorrekten Lernens, bei dem die Lerner nicht syntaktisch, sondern semantisch konvergieren sollen, wurden die gleichen Einschränkungen wie beim erklärenden Lernen untersucht. Ein ähnlich vollständiges Bild hinsichtlich ihrer Interaktion wurde jedoch noch nicht präsentiert. In dieser Arbeit übertragen wir den Kartographie-Ansatz auf das verhaltenskorrekte Lernen. Insbesondere vervollständigen wir die Teilergebnisse aus der Literatur für viele gut untersuchte Restriktionen und liefern Karten für verhaltenskorrektes Lernen mit verschiedenen Arten der Datenpräsentation. Wir untersuchen auch Eigenschaften von Lernern, die in der Literatur als wichtig eingestuft werden. Uns interessiert, ob die Lerner konsistent sind, das heißt ob ihre Vermutungen die Daten einschließen, auf denen sie aufgebaut sind. Während man beim erklärenden Lernen nicht davon ausgehen kann, dass die Lerner konsistent sind, ist beim verhaltenskorrekten Lernen das Gegenteil der Fall. Es ist sogar bekannt, dass Lerner, die verschiedenen Einschränkungen folgen, als konsistent angenommen werden können. Wir tragen zur Literatur bei, indem wir zeigen, dass dies für alle untersuchten Restriktionen der Fall ist. Wir untersuchen auch mathematisch interessante Eigenschaften von Lernern. Insbesondere interessiert uns, ob das Lernen unter einer gegebenen Restriktion mit stark Bc-sperrenden Lernern durchgeführt werden kann. Solche Lerner sind von besonderem Wert, da sie es erlauben, Simulationsargumente anzuwenden, wenn man zum Beispiel zwei Lernparadigmen miteinander vergleicht. Die Literatur bietet eine reichhaltige Grundlage dafür, wann Lerner als stark Bc-sperrend angenommen werden können, die wir auf alle untersuchten Einschränkungen erweitern. KW - language learning in the limit KW - behaviourally correct learning KW - maps KW - consistent learning KW - strongly behaviourally correct locking KW - verhaltenskorrektes Lernen KW - konsistentes Lernen KW - Sprachlernen im Limes KW - Karten KW - stark verhaltenskorrekt sperrend Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-593110 ER - TY - THES A1 - Draisbach, Uwe T1 - Efficient duplicate detection and the impact of transitivity T1 - Effiziente Dublettenerkennung und der Einfluss von Transitivität N2 - Duplicate detection describes the process of finding multiple representations of the same real-world entity in the absence of a unique identifier, and has many application areas, such as customer relationship management, genealogy and social sciences, or online shopping. Due to the increasing amount of data in recent years, the problem has become even more challenging on the one hand, but has led to a renaissance in duplicate detection research on the other hand. This thesis examines the effects and opportunities of transitive relationships on the duplicate detection process. Transitivity implies that if record pairs ⟨ri,rj⟩ and ⟨rj,rk⟩ are classified as duplicates, then also record pair ⟨ri,rk⟩ has to be a duplicate. However, this reasoning might contradict with the pairwise classification, which is usually based on the similarity of objects. An essential property of similarity, in contrast to equivalence, is that similarity is not necessarily transitive. First, we experimentally evaluate the effect of an increasing data volume on the threshold selection to classify whether a record pair is a duplicate or non-duplicate. Our experiments show that independently of the pair selection algorithm and the used similarity measure, selecting a suitable threshold becomes more difficult with an increasing number of records due to an increased probability of adding a false duplicate to an existing cluster. Thus, the best threshold changes with the dataset size, and a good threshold for a small (possibly sampled) dataset is not necessarily a good threshold for a larger (possibly complete) dataset. As data grows over time, earlier selected thresholds are no longer a suitable choice, and the problem becomes worse for datasets with larger clusters. Second, we present with the Duplicate Count Strategy (DCS) and its enhancement DCS++ two alternatives to the standard Sorted Neighborhood Method (SNM) for the selection of candidate record pairs. DCS adapts SNMs window size based on the number of detected duplicates and DCS++ uses transitive dependencies to save complex comparisons for finding duplicates in larger clusters. We prove that with a proper (domain- and data-independent!) threshold, DCS++ is more efficient than SNM without loss of effectiveness. Third, we tackle the problem of contradicting pairwise classifications. Usually, the transitive closure is used for pairwise classifications to obtain a transitively closed result set. However, the transitive closure disregards negative classifications. We present three new and several existing clustering algorithms and experimentally evaluate them on various datasets and under various algorithm configurations. The results show that the commonly used transitive closure is inferior to most other clustering algorithms, especially for the precision of results. In scenarios with larger clusters, our proposed EMCC algorithm is, together with Markov Clustering, the best performing clustering approach for duplicate detection, although its runtime is longer than Markov Clustering due to the subexponential time complexity. EMCC especially outperforms Markov Clustering regarding the precision of the results and additionally has the advantage that it can also be used in scenarios where edge weights are not available. N2 - Dubletten sind mehrere Repräsentationen derselben Entität in einem Datenbestand. Diese zu identifizieren ist das Ziel der Dublettenerkennung, wobei in der Regel Paare von Datensätzen anhand von Ähnlichkeitsmaßen miteinander verglichen und unter Verwendung eines Schwellwerts als Dublette oder Nicht-Dublette klassifiziert werden. Für Dublettenerkennung existieren verschiedene Anwendungsbereiche, beispielsweise im Kundenbeziehungsmanagement, beim Onlineshopping, der Genealogie und in den Sozialwissenschaften. Der in den letzten Jahren zu beobachtende Anstieg des gespeicherten Datenvolumens erschwert die Dublettenerkennung, da die Anzahl der benötigten Vergleiche quadratisch mit der Anzahl der Datensätze wächst. Durch Verwendung eines geeigneten Paarauswahl-Algorithmus kann die Anzahl der zu vergleichenden Paare jedoch reduziert und somit die Effizienz gesteigert werden. Die Dissertation untersucht die Auswirkungen und Möglichkeiten transitiver Beziehungen auf den Dublettenerkennungsprozess. Durch Transitivität lässt sich beispielsweise ableiten, dass aufgrund einer Klassifikation der Datensatzpaare ⟨ri,rj⟩ und ⟨rj,rk⟩ als Dublette auch die Datensätze ⟨ri,rk⟩ eine Dublette sind. Dies kann jedoch im Widerspruch zu einer paarweisen Klassifizierung stehen, denn im Unterschied zur Äquivalenz ist die Ähnlichkeit von Objekten nicht notwendigerweise transitiv. Im ersten Teil der Dissertation wird die Auswirkung einer steigenden Datenmenge auf die Wahl des Schwellwerts zur Klassifikation von Datensatzpaaren als Dublette oder Nicht-Dublette untersucht. Die Experimente zeigen, dass unabhängig von dem gewählten Paarauswahl-Algorithmus und des gewählten Ähnlichkeitsmaßes die Wahl eines geeigneten Schwellwerts mit steigender Datensatzanzahl schwieriger wird, da die Gefahr fehlerhafter Cluster-Zuordnungen steigt. Der optimale Schwellwert eines Datensatzes variiert mit dessen Größe. So ist ein guter Schwellwert für einen kleinen Datensatz (oder eine Stichprobe) nicht notwendigerweise ein guter Schwellwert für einen größeren (ggf. vollständigen) Datensatz. Steigt die Datensatzgröße im Lauf der Zeit an, so muss ein einmal gewählter Schwellwert ggf. nachjustiert werden. Aufgrund der Transitivität ist dies insbesondere bei Datensätzen mit größeren Clustern relevant. Der zweite Teil der Dissertation beschäftigt sich mit Algorithmen zur Auswahl geeigneter Datensatz-Paare für die Klassifikation. Basierend auf der Sorted Neighborhood Method (SNM) werden mit der Duplicate Count Strategy (DCS) und ihrer Erweiterung DCS++ zwei neue Algorithmen vorgestellt. DCS adaptiert die Fenstergröße in Abhängigkeit der Anzahl gefundener Dubletten und DCS++ verwendet zudem die transitive Abhängigkeit, um kostspielige Vergleiche einzusparen und trotzdem größere Cluster von Dubletten zu identifizieren. Weiterhin wird bewiesen, dass mit einem geeigneten Schwellwert DCS++ ohne Einbußen bei der Effektivität effizienter als die Sorted Neighborhood Method ist. Der dritte und letzte Teil der Arbeit beschäftigt sich mit dem Problem widersprüchlicher paarweiser Klassifikationen. In vielen Anwendungsfällen wird die Transitive Hülle zur Erzeugung konsistenter Cluster verwendet, wobei hierbei paarweise Klassifikationen als Nicht-Dublette missachtet werden. Es werden drei neue und mehrere existierende Cluster-Algorithmen vorgestellt und experimentell mit verschiedenen Datensätzen und Konfigurationen evaluiert. Die Ergebnisse zeigen, dass die Transitive Hülle den meisten anderen Clustering-Algorithmen insbesondere bei der Precision, definiert als Anteil echter Dubletten an der Gesamtzahl klassifizierter Dubletten, unterlegen ist. In Anwendungsfällen mit größeren Clustern ist der vorgeschlagene EMCC-Algorithmus trotz seiner subexponentiellen Laufzeit zusammen mit dem Markov-Clustering der beste Clustering-Ansatz für die Dublettenerkennung. EMCC übertrifft Markov Clustering insbesondere hinsichtlich der Precision der Ergebnisse und hat zusätzlich den Vorteil, dass dieser auch ohne Ähnlichkeitswerte eingesetzt werden kann. KW - Datenqualität KW - Datenintegration KW - Dubletten KW - Duplikaterkennung KW - data quality KW - data integration KW - duplicate detection KW - deduplication KW - entity resolution Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-572140 ER - TY - THES A1 - Dyck, Johannes T1 - Verification of graph transformation systems with k-inductive invariants T1 - Verifikation von Graphtransformationssystemen mit k-induktiven Invarianten N2 - With rising complexity of today's software and hardware systems and the hypothesized increase in autonomous, intelligent, and self-* systems, developing correct systems remains an important challenge. Testing, although an important part of the development and maintainance process, cannot usually establish the definite correctness of a software or hardware system - especially when systems have arbitrarily large or infinite state spaces or an infinite number of initial states. This is where formal verification comes in: given a representation of the system in question in a formal framework, verification approaches and tools can be used to establish the system's adherence to its similarly formalized specification, and to complement testing. One such formal framework is the field of graphs and graph transformation systems. Both are powerful formalisms with well-established foundations and ongoing research that can be used to describe complex hardware or software systems with varying degrees of abstraction. Since their inception in the 1970s, graph transformation systems have continuously evolved; related research spans extensions of expressive power, graph algorithms, and their implementation, application scenarios, or verification approaches, to name just a few topics. This thesis focuses on a verification approach for graph transformation systems called k-inductive invariant checking, which is an extension of previous work on 1-inductive invariant checking. Instead of exhaustively computing a system's state space, which is a common approach in model checking, 1-inductive invariant checking symbolically analyzes graph transformation rules - i.e. system behavior - in order to draw conclusions with respect to the validity of graph constraints in the system's state space. The approach is based on an inductive argument: if a system's initial state satisfies a graph constraint and if all rules preserve that constraint's validity, we can conclude the constraint's validity in the system's entire state space - without having to compute it. However, inductive invariant checking also comes with a specific drawback: the locality of graph transformation rules leads to a lack of context information during the symbolic analysis of potential rule applications. This thesis argues that this lack of context can be partly addressed by using k-induction instead of 1-induction. A k-inductive invariant is a graph constraint whose validity in a path of k-1 rule applications implies its validity after any subsequent rule application - as opposed to a 1-inductive invariant where only one rule application is taken into account. Considering a path of transformations then accumulates more context of the graph rules' applications. As such, this thesis extends existing research and implementation on 1-inductive invariant checking for graph transformation systems to k-induction. In addition, it proposes a technique to perform the base case of the inductive argument in a symbolic fashion, which allows verification of systems with an infinite set of initial states. Both k-inductive invariant checking and its base case are described in formal terms. Based on that, this thesis formulates theorems and constructions to apply this general verification approach for typed graph transformation systems and nested graph constraints - and to formally prove the approach's correctness. Since unrestricted graph constraints may lead to non-termination or impracticably high execution times given a hypothetical implementation, this thesis also presents a restricted verification approach, which limits the form of graph transformation systems and graph constraints. It is formalized, proven correct, and its procedures terminate by construction. This restricted approach has been implemented in an automated tool and has been evaluated with respect to its applicability to test cases, its performance, and its degree of completeness. N2 - Durch die Komplexität heutiger Software- und Hardwaresysteme und den vermuteten Anstieg der Zahl autonomer und intelligenter Systeme bleibt die Entwicklung korrekter Systeme eine wichtige Herausforderung. Obwohl Testen ein wichtiger Teil des Entwicklungszyklusses ist und bleibt, reichen Tests üblicherweise nicht aus, um die Korrektkeit eines Systems sicherzustellen - insbsondere wenn Systeme beliebig große oder unendliche Zustandsräume oder unendlich viele mögliche initiale Zustände aufweisen. Formale Verifikation nimmt sich dieses Problems an: Nach Darstellung des Systems in einem formalen Modell können Verifikationsansätze und Werkzeuge angewendet werden, um zu analysieren, ob das System seine Spezifikation erfüllt. Ein verbreiteter Formalismus für derartige Modelle sind Graphen und Graphtransformationssysteme. Diese Konzepte basieren auf etablierten mathematischen Grundlagen und sind ausdrucksstark genug, um komplexe Software- oder Hardwaresysteme auf verschiedenen Abstraktionsstufen zu beschreiben. Seit ihrer Einführung in den 70er-Jahren wurden Graphtransformationssysteme stetig weiterentwickelt; entsprechende Forschung thematisiert beispielsweise Ausdrucksstärke, Graphalgorithmen, Anwendungsbeispiele oder Verifikationsansätze. Diese Arbeit beschäftigt sich mit der Verifikation k-induktiver Invarianten für Graphtransformationssysteme - einem Ansatz, der eine existierende Technik zur Verifikation 1-induktiver Invarianten erweitert. Anstatt den Zustandsraum eines Systems zu berechnen, überprüft Verifikation mit 1-Induktion Verhalten (Graphtransformationsregeln) symbolisch, um Schlussfolgerungen zur Gültigkeit von Graphbedingungen zu ziehen. Die Idee basiert auf dem Prinzip eines Induktionsbeweises: Falls der initiale Zustand eines Systems eine Bedingung erfüllt und falls alle Regeln die Erfüllung der Bedingung bewahren, kann auf die Gültigkeit der Bedingung im gesamten Zustandsraum geschlossen werden, ohne diesen tatsächlich zu berechnen. Allerdings bringt dieser Ansatz auch spezifische Nachteile mit sich: Die lokale Natur der Anwendung von Graphregeln führt zu einem Mangel an Kontext während der symbolischen Analyse möglicher Regelanwendungen. Diese Arbeit führt aus, dass dieser Mangel an Kontext teilweise behoben werden kann, indem k-Induktion statt 1-Induktion verwendet wird. Eine k-induktive Invariante ist eine Graphbedingung, deren Gültigkeit in einem Pfad von k-1 Regelanwendungen die Gültigkeit nach jeder etwaigen weiteren Regelanwendung zur Folge hat. Durch die Berücksichtigung solcher Pfade von Transformationen steht mehr Kontext während der Analyse zur Verfügung als bei der Analyse nur einer Regelanwendung bei 1-Induktion. Daher erweitert diese Arbeit bestehende Forschungsergebnisse und eine Implementierung zur Verifikation 1-induktiver Invarianten um k-Induktion. Zusätzlich wird eine Technik vorgestellt, die auch die Analyse der Induktionsbasis symbolisch ausführt. Dies erlaubt die Verifikation von Systemen mit einer unendlichen Zahl an möglichen initialen Zuständen. Sowohl k-induktive Invarianten als auch deren Induktionsbasis werden - für Graphtransformationssysteme - formal beschrieben. Basierend darauf stellt diese Arbeit Theoreme und Kontruktionen vor, die diesen Verifikationsansatz mathemathisch umsetzen und seine Korrektheit beweisen. Da jedoch uneingeschränkte Graphbedingungen in einer möglichen Implementierung zu Nichtterminierung oder langen Ausführungszeiten führen, stellt diese Arbeit auch einen eingeschränkten Verifikationsansatz vor, der die Form der zugelassenen Graphtransformationssysteme und Graphbedingungen in Spezifikationen einschränkt. Auch dieser Ansatz wird formalisiert, bewiesen - und das Verfahren terminiert per Konstruktion. Der Ansatz wurde in Form eines automatisch ausführbaren Verifikationswerkzeugs implementiert und wurde in Bezug auf seine Anwendbarkeit, Performanz und des Grades der Vollständigkeit evaluiert. KW - formal verification KW - graph transformations KW - inductive invariant checking KW - k-induction KW - graph constraints KW - application conditions KW - k-inductive invariant KW - graph transformation systems KW - formale Verifikation KW - Graphtransformationen KW - Verifikation induktiver Invarianten KW - k-Induktion KW - Graphbedingungen KW - Anwendungsbedingungen KW - k-induktive Invariante KW - Graphtransformationssysteme Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-442742 ER - TY - THES A1 - Elsaid, Mohamed Esameldin Mohamed T1 - Virtual machines live migration cost modeling and prediction T1 - Modellierung und Vorhersage der Live-Migrationskosten für Virtuelle Maschinen N2 - Dynamic resource management is an essential requirement for private and public cloud computing environments. With dynamic resource management, the physical resources assignment to the cloud virtual resources depends on the actual need of the applications or the running services, which enhances the cloud physical resources utilization and reduces the offered services cost. In addition, the virtual resources can be moved across different physical resources in the cloud environment without an obvious impact on the running applications or services production. This means that the availability of the running services and applications in the cloud is independent on the hardware resources including the servers, switches and storage failures. This increases the reliability of using cloud services compared to the classical data-centers environments. In this thesis we briefly discuss the dynamic resource management topic and then deeply focus on live migration as the definition of the compute resource dynamic management. Live migration is a commonly used and an essential feature in cloud and virtual data-centers environments. Cloud computing load balance, power saving and fault tolerance features are all dependent on live migration to optimize the virtual and physical resources usage. As we will discuss in this thesis, live migration shows many benefits to cloud and virtual data-centers environments, however the cost of live migration can not be ignored. Live migration cost includes the migration time, downtime, network overhead, power consumption increases and CPU overhead. IT admins run virtual machines live migrations without an idea about the migration cost. So, resources bottlenecks, higher migration cost and migration failures might happen. The first problem that we discuss in this thesis is how to model the cost of the virtual machines live migration. Secondly, we investigate how to make use of machine learning techniques to help the cloud admins getting an estimation of this cost before initiating the migration for one of multiple virtual machines. Also, we discuss the optimal timing for a specific virtual machine before live migration to another server. Finally, we propose practical solutions that can be used by the cloud admins to be integrated with the cloud administration portals to answer the raised research questions above. Our research methodology to achieve the project objectives is to propose empirical models based on using VMware test-beds with different benchmarks tools. Then we make use of the machine learning techniques to propose a prediction approach for virtual machines live migration cost. Timing optimization for live migration is also proposed in this thesis based on using the cost prediction and data-centers network utilization prediction. Live migration with persistent memory clusters is also discussed at the end of the thesis. The cost prediction and timing optimization techniques proposed in this thesis could be practically integrated with VMware vSphere cluster portal such that the IT admins can now use the cost prediction feature and timing optimization option before proceeding with a virtual machine live migration. Testing results show that our proposed approach for VMs live migration cost prediction shows acceptable results with less than 20% prediction error and can be easily implemented and integrated with VMware vSphere as an example of a commonly used resource management portal for virtual data-centers and private cloud environments. The results show that using our proposed VMs migration timing optimization technique also could save up to 51% of migration time of the VMs migration time for memory intensive workloads and up to 27% of the migration time for network intensive workloads. This timing optimization technique can be useful for network admins to save migration time with utilizing higher network rate and higher probability of success. At the end of this thesis, we discuss the persistent memory technology as a new trend in servers memory technology. Persistent memory modes of operation and configurations are discussed in detail to explain how live migration works between servers with different memory configuration set up. Then, we build a VMware cluster with persistent memory inside server and also with DRAM only servers to show the live migration cost difference between the VMs with DRAM only versus the VMs with persistent memory inside. N2 - Die dynamische Ressourcenverwaltung ist eine wesentliche Voraussetzung für private und öffentliche Cloud-Computing-Umgebungen. Bei der dynamischen Ressourcenverwaltung hängt die Zuweisung der physischen Ressourcen zu den virtuellen Cloud-Ressourcen vom tatsächlichen Bedarf der Anwendungen oder der laufenden Dienste ab, was die Auslastung der physischen Cloud-Ressourcen verbessert und die Kosten für die angebotenen Dienste reduziert. Darüber hinaus können die virtuellen Ressourcen über verschiedene physische Ressourcen in der Cloud-Umgebung verschoben werden, ohne dass dies einen offensichtlichen Einfluss auf die laufenden Anwendungen oder die Produktion der Dienste hat. Das bedeutet, dass die Verfügbarkeit der laufenden Dienste und Anwendungen in der Cloud unabhängig von den Hardwareressourcen einschließlich der Server, Netzwerke und Speicherausfälle ist. Dies erhöht die Zuverlässigkeit bei der Nutzung von Cloud-Diensten im Vergleich zu klassischen Rechenzentrumsumgebungen. In dieser Arbeit wird das Thema der dynamischen Ressourcenverwaltung kurz erörtert, um sich dann eingehend mit der Live-Migration als Definition der dynamischen Verwaltung von Compute-Ressourcen zu beschäftigen. Live-Migration ist eine häufig verwendete und wesentliche Funktion in Cloud- und virtuellen Rechenzentrumsumgebungen. Cloud-Computing-Lastausgleich, Energiespar- und Fehlertoleranzfunktionen sind alle von der Live-Migration abhängig, um die Nutzung der virtuellen und physischen Ressourcen zu optimieren. Wie wir in dieser Arbeit erörtern werden, zeigt die Live-Migration viele Vorteile für Cloud- und virtuelle Rechenzentrumsumgebungen, jedoch können die Kosten der Live-Migration nicht ignoriert werden. Zu den Kosten der Live-Migration gehören die Migrationszeit, die Ausfallzeit, der Netzwerk-Overhead, der Anstieg des Stromverbrauchs und der CPU-Overhead. IT-Administratoren führen Live-Migrationen von virtuellen Maschinen durch, ohne eine Vorstellung von den Migrationskosten zu haben. So kann es zu Ressourcenengpässen, höheren Migrationskosten und Migrationsfehlern kommen. Das erste Problem, das wir in dieser Arbeit diskutieren, ist, wie man die Kosten der Live-Migration virtueller Maschinen modellieren kann. Zweitens untersuchen wir, wie maschinelle Lerntechniken eingesetzt werden können, um den Cloud-Administratoren zu helfen, eine Schätzung dieser Kosten zu erhalten, bevor die Migration für eine oder mehrere virtuelle Maschinen eingeleitet wird. Außerdem diskutieren wir das optimale Timing für eine bestimmte virtuelle Maschine vor der Live-Migration auf einen anderen Server. Schließlich schlagen wir praktische Lösungen vor, die von den Cloud-Admins verwendet werden können, um in die Cloud-Administrationsportale integriert zu werden, um die oben aufgeworfenen Forschungsfragen zu beantworten. Unsere Forschungsmethodik zur Erreichung der Projektziele besteht darin, empirische Modelle vorzuschlagen, die auf der Verwendung von VMware-Testbeds mit verschiedenen Benchmark-Tools basieren. Dann nutzen wir die Techniken des maschinellen Lernens, um einen Vorhersageansatz für die Kosten der Live-Migration virtueller Maschinen vorzuschlagen. Die Timing-Optimierung für die Live-Migration wird ebenfalls in dieser Arbeit vorgeschlagen, basierend auf der Kostenvorhersage und der Vorhersage der Netzwerkauslastung des Rechenzentrums. Die Live-Migration mit Clustern mit persistentem Speicher wird ebenfalls am Ende der Arbeit diskutiert. Die in dieser Arbeit vorgeschlagenen Techniken zur Kostenvorhersage und Timing-Optimierung könnten praktisch in das VMware vSphere-Cluster-Portal integriert werden, so dass die IT-Administratoren nun die Funktion zur Kostenvorhersage und die Option zur Timing-Optimierung nutzen können, bevor sie mit einer Live-Migration der virtuellen Maschine fortfahren. Die Testergebnisse zeigen, dass unser vorgeschlagener Ansatz für die VMs-Live-Migrationskostenvorhersage akzeptable Ergebnisse mit weniger als 20\% Fehler in der Vorhersagegenauigkeit zeigt und leicht implementiert und in VMware vSphere als Beispiel für ein häufig verwendetes Ressourcenmanagement-Portal für virtuelle Rechenzentren und private Cloud-Umgebungen integriert werden kann. Die Ergebnisse zeigen, dass mit der von uns vorgeschlagenen Technik zur Timing-Optimierung der VMs-Migration auch bis zu 51\% der Migrationszeit für speicherintensive Workloads und bis zu 27\% der Migrationszeit für netzwerkintensive Workloads eingespart werden können. Diese Timing-Optimierungstechnik kann für Netzwerkadministratoren nützlich sein, um Migrationszeit zu sparen und dabei eine höhere Netzwerkrate und eine höhere Erfolgswahrscheinlichkeit zu nutzen. Am Ende dieser Arbeit wird die persistente Speichertechnologie als neuer Trend in der Server-Speichertechnologie diskutiert. Die Betriebsarten und Konfigurationen des persistenten Speichers werden im Detail besprochen, um zu erklären, wie die Live-Migration zwischen Servern mit unterschiedlichen Speicherkonfigurationen funktioniert. Dann bauen wir einen VMware-Cluster mit persistentem Speicher im Server und auch mit Servern nur mit DRAM auf, um den Kostenunterschied bei der Live-Migration zwischen den VMs mit nur DRAM und den VMs mit persistentem Speicher im Server zu zeigen. KW - virtual KW - cloud KW - computing KW - machines KW - live migration KW - machine learning KW - prediction KW - Wolke KW - Computing KW - Live-Migration KW - maschinelles Lernen KW - Maschinen KW - Vorhersage KW - virtuell Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-540013 ER - TY - THES A1 - Freitas da Cruz, Harry T1 - Standardizing clinical predictive modeling T1 - Standardisierung der klinischen Vorhersagemodellierung BT - standardizing development, validation, and interpretation of clinical prediction models BT - Standardisierung der Entwicklung, Validierung und Interpretierung von klinischen Vorhersagemodellen N2 - An ever-increasing number of prediction models is published every year in different medical specialties. Prognostic or diagnostic in nature, these models support medical decision making by utilizing one or more items of patient data to predict outcomes of interest, such as mortality or disease progression. While different computer tools exist that support clinical predictive modeling, I observed that the state of the art is lacking in the extent to which the needs of research clinicians are addressed. When it comes to model development, current support tools either 1) target specialist data engineers, requiring advanced coding skills, or 2) cater to a general-purpose audience, therefore not addressing the specific needs of clinical researchers. Furthermore, barriers to data access across institutional silos, cumbersome model reproducibility and extended experiment-to-result times significantly hampers validation of existing models. Similarly, without access to interpretable explanations, which allow a given model to be fully scrutinized, acceptance of machine learning approaches will remain limited. Adequate tool support, i.e., a software artifact more targeted at the needs of clinical modeling, can help mitigate the challenges identified with respect to model development, validation and interpretation. To this end, I conducted interviews with modeling practitioners in health care to better understand the modeling process itself and ascertain in what aspects adequate tool support could advance the state of the art. The functional and non-functional requirements identified served as the foundation for a software artifact that can be used for modeling outcome and risk prediction in health research. To establish the appropriateness of this approach, I implemented a use case study in the Nephrology domain for acute kidney injury, which was validated in two different hospitals. Furthermore, I conducted user evaluation to ascertain whether such an approach provides benefits compared to the state of the art and the extent to which clinical practitioners could benefit from it. Finally, when updating models for external validation, practitioners need to apply feature selection approaches to pinpoint the most relevant features, since electronic health records tend to contain several candidate predictors. Building upon interpretability methods, I developed an explanation-driven recursive feature elimination approach. This method was comprehensively evaluated against state-of-the art feature selection methods. Therefore, this thesis' main contributions are three-fold, namely, 1) designing and developing a software artifact tailored to the specific needs of the clinical modeling domain, 2) demonstrating its application in a concrete case in the Nephrology context and 3) development and evaluation of a new feature selection approach applicable in a validation context that builds upon interpretability methods. In conclusion, I argue that appropriate tooling, which relies on standardization and parametrization, can support rapid model prototyping and collaboration between clinicians and data scientists in clinical predictive modeling. N2 - Die Zahl der jährlich veröffentlichten Vorhersagemodelle in verschiedenen medizinischen Fachrichtungen nimmt stetig zu. Solche prognostischen oder diagnostischen Modelle helfen bei der medizinischen Entscheidungsfindung, indem sie zum Beispiel Vorhersagen zur Mortalität oder zum Krankheitsverlauf erlauben. Obwohl bereits Softwarewerkzeuge für die Entwicklung klinischer Vorhersagemodelle existieren, genügt der Stand der Technik noch immer nicht den Anforderungen klinischer Wissenschaftler. So kommt es, dass aktuelle Softwarewerkzeuge zur Modellentwicklung entweder 1) auf die Anforderungen von Datenwissenschaftlicher zugeschnitten sind und folglich Programmierkenntnisse voraussetzen, oder 2) zu generisch sind und somit den tatsächlichen Anforderungen klinischer Wissenschaftler nicht gerecht werden. Überdies wird die Reproduzierbarkeit der Modelle sowie die Durchführung und Validierung von Experimenten durch verteilte Datenbestände und Informationen, sogenannte Datensilos, stark eingeschränkt. Ähnlich verhält es sich bei der Akzeptanz von Modellen des maschinellen Lernens, welche ohne interpretierbare Erklärungen von Vorhersagen kaum gegeben sein dürfte. Eine auf diese Anforderungen klinischer Modellbildung ausgerichtete Softwarelösung kann dabei helfen, die identifizierten Herausforderungen bezüglich Modellentwicklung, -validierung und -interpretation zu bewältigen und die Akzeptanz und Nutzung unter Klinikern zu stärken. Um den Modellierungsprozess zu verstehen und zu eruieren, in welchem Ausmaß eine angemessene Softwarelösung den Stand der Technik voranbringen könnte, wurden im Zuge dieser Arbeit Interviews mit praktizierenden Modellierern im Gesundheitsbereich geführt. Daraus leiten sich funktionale und nichtfunktionale Anforderungen ab, die als Grundlage eines Softwareartefaktes für die Modellierung von Outcome- und Risikovorhersagen in der Gesundheitsforschung verwendet wurden. Um die Eignung meines Ansatzes zu verifizieren, habe ich den Anwendungsfall „akutes Nierenversagen“ im Bereich der Nephrologie in zwei verschiedenen Krankenhäusern betrachtet und validiert. Darüber hinaus wurde eine Nutzerevaluierung durchgeführt um herauszufinden, ob ein solcher Ansatz im Vergleich zum Stand der Technik Vorteile bietet und inwieweit klinische Praktiker davon profitieren können. Außerdem müssen praktizierende Kliniker bei der Aktualisierung von Modellen für die externe Validierung Ansätze zur Merkmalsselektion anwenden, da elektronische Gesundheitsakten in der Regel mehrere erklärende Merkmale enthalten. Aufbauend auf Methoden zur Interpretierbarkeit habe ich einen erklärungsorientierten rekursiven Eliminierungsansatz entwickelt. Dieser neue Ansatz wurde umfassend mit Standardverfahren der Merkmalsselektion verglichen. Daraus leiten sich folgende Forschungsbeiträge dieser Arbeit ab: 1) Entwurf und Entwicklung eines Softwareartefakts, welches auf die speziellen Bedürfnisse der klinischen Modellierungsdomäne zugeschnitten ist, 2) Demonstration seiner Anwendbarkeit für das konkrete Fallbeispiel „akutes Nierenversagen“ und 3) Entwicklung und Evaluierung eines neuen, auf Interpretierbarkeitsmethoden basierenden Ansatzes, zur Merkmalsselektion in einem Validierungskontext. Zusammenfassend ist zu folgern, dass ein geeignetes auf Standardisierung und Parametrisierung gestütztes Tool die schnelle prototypische Entwicklung und die Zusammenarbeit von Klinikern und Datenwissenschaftlern an klinischen Vorhersagemodellen unterstützen kann. KW - Predictive Modeling KW - Prädiktive Modellierung KW - Clinical Data KW - Klinische Daten KW - Künstliche Intelligenz KW - Vorhersagemodellierung KW - Überwachtes Lernen KW - Artificial Intelligence KW - Supervised Learning Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-514960 ER - TY - THES A1 - Gawron, Marian T1 - Towards automated advanced vulnerability analysis N2 - The identification of vulnerabilities in IT infrastructures is a crucial problem in enhancing the security, because many incidents resulted from already known vulnerabilities, which could have been resolved. Thus, the initial identification of vulnerabilities has to be used to directly resolve the related weaknesses and mitigate attack possibilities. The nature of vulnerability information requires a collection and normalization of the information prior to any utilization, because the information is widely distributed in different sources with their unique formats. Therefore, the comprehensive vulnerability model was defined and different sources have been integrated into one database. Furthermore, different analytic approaches have been designed and implemented into the HPI-VDB, which directly benefit from the comprehensive vulnerability model and especially from the logical preconditions and postconditions. Firstly, different approaches to detect vulnerabilities in both IT systems of average users and corporate networks of large companies are presented. Therefore, the approaches mainly focus on the identification of all installed applications, since it is a fundamental step in the detection. This detection is realized differently depending on the target use-case. Thus, the experience of the user, as well as the layout and possibilities of the target infrastructure are considered. Furthermore, a passive lightweight detection approach was invented that utilizes existing information on corporate networks to identify applications. In addition, two different approaches to represent the results using attack graphs are illustrated in the comparison between traditional attack graphs and a simplistic graph version, which was integrated into the database as well. The implementation of those use-cases for vulnerability information especially considers the usability. Beside the analytic approaches, the high data quality of the vulnerability information had to be achieved and guaranteed. The different problems of receiving incomplete or unreliable information for the vulnerabilities are addressed with different correction mechanisms. The corrections can be carried out with correlation or lookup mechanisms in reliable sources or identifier dictionaries. Furthermore, a machine learning based verification procedure was presented that allows an automatic derivation of important characteristics from the textual description of the vulnerabilities. N2 - Die Erkennung von Schwachstellen ist ein schwerwiegendes Problem bei der Absicherung von modernen IT-Systemen. Mehrere Sicherheitsvorfälle hätten durch die vorherige Erkennung von Schwachstellen verhindert werden können, da in diesen Vorfällen bereits bekannte Schwachstellen ausgenutzt wurden. Der Stellenwert der Sicherheit von IT Systemen nimmt immer weiter zu, was auch mit der Aufmerksamkeit, die seit kurzem auf die Sicherheit gelegt wird, zu begründen ist. Somit nimmt auch der Stellenwert einer Schwachstellenanalyse der IT Systeme immer mehr zu, da hierdurch potenzielle Angriffe verhindert und Sicherheitslücken geschlossen werden können. Die Informationen über Sicherheitslücken liegen in verschiedenen Quellen in unterschiedlichen Formaten vor. Aus diesem Grund wird eine Normalisierungsmethode benötigt, um die verschiedenen Informationen in ein einheitliches Format zu bringen. Das damit erzeugte Datenmodell wird in der HPI-VDB gespeichert, in die auch darauf aufbauende Analyseansätze integriert wurden. Diese Analysemethoden profitieren direkt von den Eigenschaften des Datenmodells, das maschinenlesbare Vor- und Nachbedingungen enthält. Zunächst wurden verschiedene Methoden zur Erkennung von Schwachstellen in IT Systemen von durchschnittlichen Nutzern und auch in Systemen von großen Firmen entwickelt. Hierbei wird der Identifikation der installierten Programme die größte Aufmerksamkeit beigemessen, da es der grundlegende Bestandteil der Erkennung von Schwachstellen ist. Für die Ansätze wird weiterhin die Erfahrung des Nutzers und die Eigenschaften der Zielumgebung berücksichtigt. Zusätzlich wurden zwei weitere Ansätze zur Repräsentation der Ergebnisse integriert. Hierfür wurden traditionelle Angriffsgraphen mit einer vereinfachten Variante verglichen, die auch in die Datenbank integriert wurde. Des Weiteren spielt die Datenqualität eine wichtige Rolle, da die Effizienz der Analysemethoden von der Qualität der Informationen abhängt. Deshalb wurden Probleme wie Unvollständigkeit und Unzuverlässigkeit der Informationen mit verschiedenen Korrekturansätzen bewältigt. Diese Korrekturen werden mithilfe von Korrelationen und Maschinellem Lernen bewerkstelligt, wobei die automatische Ausführbarkeit eine grundlegende Anforderung darstellt. KW - IT-security KW - vulnerability KW - analysis KW - IT-Sicherheit KW - Schwachstelle KW - Analyse Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-426352 ER - TY - THES A1 - Ghahremani, Sona T1 - Incremental self-adaptation of dynamic architectures attaining optimality and scalability T1 - Inkrementelle Selbstanpassung dynamischer Architekturen zum Erreichen von Optimalität und Skalierbarkeit N2 - The landscape of software self-adaptation is shaped in accordance with the need to cost-effectively achieve and maintain (software) quality at runtime and in the face of dynamic operation conditions. Optimization-based solutions perform an exhaustive search in the adaptation space, thus they may provide quality guarantees. However, these solutions render the attainment of optimal adaptation plans time-intensive, thereby hindering scalability. Conversely, deterministic rule-based solutions yield only sub-optimal adaptation decisions, as they are typically bound by design-time assumptions, yet they offer efficient processing and implementation, readability, expressivity of individual rules supporting early verification. Addressing the quality-cost trade-of requires solutions that simultaneously exhibit the scalability and cost-efficiency of rulebased policy formalism and the optimality of optimization-based policy formalism as explicit artifacts for adaptation. Utility functions, i.e., high-level specifications that capture system objectives, support the explicit treatment of quality-cost trade-off. Nevertheless, non-linearities, complex dynamic architectures, black-box models, and runtime uncertainty that makes the prior knowledge obsolete are a few of the sources of uncertainty and subjectivity that render the elicitation of utility non-trivial. This thesis proposes a twofold solution for incremental self-adaptation of dynamic architectures. First, we introduce Venus, a solution that combines in its design a ruleand an optimization-based formalism enabling optimal and scalable adaptation of dynamic architectures. Venus incorporates rule-like constructs and relies on utility theory for decision-making. Using a graph-based representation of the architecture, Venus captures rules as graph patterns that represent architectural fragments, thus enabling runtime extensibility and, in turn, support for dynamic architectures; the architecture is evaluated by assigning utility values to fragments; pattern-based definition of rules and utility enables incremental computation of changes on the utility that result from rule executions, rather than evaluating the complete architecture, which supports scalability. Second, we introduce HypeZon, a hybrid solution for runtime coordination of multiple off-the-shelf adaptation policies, which typically offer only partial satisfaction of the quality and cost requirements. Realized based on meta-self-aware architectures, HypeZon complements Venus by re-using existing policies at runtime for balancing the quality-cost trade-off. The twofold solution of this thesis is integrated in an adaptation engine that leverages state- and event-based principles for incremental execution, therefore, is scalable for large and dynamic software architectures with growing size and complexity. The utility elicitation challenge is resolved by defining a methodology to train utility-change prediction models. The thesis addresses the quality-cost trade-off in adaptation of dynamic software architectures via design-time combination (Venus) and runtime coordination (HypeZon) of rule- and optimization-based policy formalisms, while offering supporting mechanisms for optimal, cost-effective, scalable, and robust adaptation. The solutions are evaluated according to a methodology that is obtained based on our systematic literature review of evaluation in self-healing systems; the applicability and effectiveness of the contributions are demonstrated to go beyond the state-of-the-art in coverage of a wide spectrum of the problem space for software self-adaptation. N2 - Die Landschaft der Software-Selbstanpassungen ist von der Notwendigkeit geprägt, zur Laufzeit und angesichts dynamischer Betriebsbedingungen kosteneffizient (Software-)Qualität zu erreichen und aufrechtzuerhalten. Optimierungsbasierte Lösungen führen eine umfassende Suche im Anpassungsraum durch und können daher Qualitätsgarantien bieten. Allerdings machen diese Lösungen das Erreichen optimaler Anpassungspläne zeitintensiv und behindern dadurch die Skalierbarkeit. Umgekehrt führen deterministische regelbasierte Lösungen nur zu suboptimalen Anpassungsentscheidungen, da sie typischerweise an Annahmen zur Entwurfszeit gebunden sind. Sie bieten jedoch eine effiziente Verarbeitung und Implementierung, Lesbarkeit und Ausdruckskraft einzelner Regeln und unterstützen so eine frühzeitige Überprüfung der Korrektheit. Um den Kompromiss zwischen Qualität und Kosten anzugehen, sind Lösungen erforderlich, die gleichzeitig die Skalierbarkeit und Kosteneffizienz des regelbasierten Strategieformalismus und die Optimalität des optimierungsbasierten Strategieformalismus als explizite Artefakte für die Anpassung berücksichtigen. Utility-Funktionen, d.h. Spezifikationen auf abstrakter Ebene, die Systemziele erfassen, unterstützen die explizite Behandlung des Qualität-Kosten-Kompromisses. Dennoch sind Nichtlinearitäten, komplexe dynamische Architekturen, Black-Box-Modelle und Laufzeitunsicherheit, die das Vorwissen überflüssig macht, einige der Quellen von Unsicherheit und Subjektivität, die die Utility-Erhöhung nicht trivial machen. Diese Arbeit schlägt eine zweifältige Lösung für die inkrementelle Selbstanpassung dynamischer Architekturen vor. Zunächst stellen wir Venus vor, eine Lösung, die in ihrem Design einen regel- und optimierungsbasierten Formalismus kombiniert und so eine optimale und skalierbare Anpassung dynamischer Architekturen ermöglicht. Venus enthält regelartige Konstrukte und nutzt die Utility-Theorie für die Entscheidungsfindung. Mithilfe einer graphbasierten Darstellung der Architektur erfasst Venus Regeln als Graphmuster, die Architekturfragmente darstellen, und ermöglicht so die Erweiterbarkeit zur Laufzeit und damit die Unterstützung dynamischer Architekturen. Die Architektur wird bewertet, indem den Fragmenten Utility-Werte zugewiesen werden. Die graphbasierte Definition von Regeln und Utility ermöglicht die inkrementelle Berechnung von Änderungen der Utility, die sich aus Regelausführungen ergeben, anstatt die gesamte Architektur zu bewerten, was die Skalierbarkeit verbessert. Des weiteren stellen wir HypeZon vor, eine Hybridlösung zur Laufzeitkoordination mehrerer Standardanpassungsstrategien, die typischerweise nur eine partielle Erfüllung der Qualitäts- und Kostenanforderungen bieten. HypeZon wurde auf der Grundlage der meta-selbstwahrnehmenden Architekturen umgesetzt und ergänzt Venus durch die Wiederverwendung bestehender Strategien zur Laufzeit, um den Kompromiss zwischen Qualität und Kosten auszubalancieren. Die zweifältige Lösung aus dieser Dissertation ist in eine Anpassungs-Engine integriert, die zustands- und ereignisbasierte Prinzipien für die inkrementelle Ausführung nutzt und daher für große und dynamische Softwarearchitekturen mit wachsender Größe und Komplexität skalierbar ist. Die Herausforderung der Erhöhung der Utility wird durch die Definition einer Methodik gelöst, die zum Trainieren von Modellen zur Vorhersage von Utility-Änderungen verwendet wird. Die Dissertation befasst sich mit dem Qualität-Kosten-Kompromiss bei der Anpassung dynamischer Softwarearchitekturen durch Entwurfszeitkombination (Venus) und Laufzeitkoordination (HypeZon) von regel- und optimierungsbasierten Strategieformalismen und bietet gleichzeitig unterstützende Mechanismen für optimale, kosteneffektive, skalierbare und robuste Anpassung. Die Lösungen werden nach einer Methodik bewertet, die auf unserer systematischen Literaturrecherche zur Bewertung von selbstheilenden Systemen basiert. Die Anwendbarkeit und Wirksamkeit der Lösungen geht nachweislich über den Stand der Technik hinaus und deckt ein breites Spektrum des Problembereichs der Software-Selbstanpassung ab. KW - self-healing KW - self-adaptive systems KW - architecture-based software adaptation KW - utility functions KW - prediction models KW - meta self-adaptation KW - model-driven engineering KW - scalable KW - architekturbasierte Softwareanpassung KW - Meta-Selbstanpassung KW - modellgesteuerte Entwicklung KW - Vorhersagemodelle KW - skalierbar KW - selbstanpassende Systeme KW - selbstheilende Systeme KW - Utility-Funktionen Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-624232 ER - TY - THES A1 - Groß, Sascha T1 - Detecting and mitigating information flow threats in Android OS Y1 - 2019 ER - TY - THES A1 - Grüner, Andreas T1 - Towards practical and trust-enhancing attribute aggregation for self-sovereign identity N2 - Identity management is at the forefront of applications’ security posture. It separates the unauthorised user from the legitimate individual. Identity management models have evolved from the isolated to the centralised paradigm and identity federations. Within this advancement, the identity provider emerged as a trusted third party that holds a powerful position. Allen postulated the novel self-sovereign identity paradigm to establish a new balance. Thus, extensive research is required to comprehend its virtues and limitations. Analysing the new paradigm, initially, we investigate the blockchain-based self-sovereign identity concept structurally. Moreover, we examine trust requirements in this context by reference to patterns. These shapes comprise major entities linked by a decentralised identity provider. By comparison to the traditional models, we conclude that trust in credential management and authentication is removed. Trust-enhancing attribute aggregation based on multiple attribute providers provokes a further trust shift. Subsequently, we formalise attribute assurance trust modelling by a metaframework. It encompasses the attestation and trust network as well as the trust decision process, including the trust function, as central components. A secure attribute assurance trust model depends on the security of the trust function. The trust function should consider high trust values and several attribute authorities. Furthermore, we evaluate classification, conceptual study, practical analysis and simulation as assessment strategies of trust models. For realising trust-enhancing attribute aggregation, we propose a probabilistic approach. The method exerts the principle characteristics of correctness and validity. These values are combined for one provider and subsequently for multiple issuers. We embed this trust function in a model within the self-sovereign identity ecosystem. To practically apply the trust function and solve several challenges for the service provider that arise from adopting self-sovereign identity solutions, we conceptualise and implement an identity broker. The mediator applies a component-based architecture to abstract from a single solution. Standard identity and access management protocols build the interface for applications. We can conclude that the broker’s usage at the side of the service provider does not undermine self-sovereign principles, but fosters the advancement of the ecosystem. The identity broker is applied to sample web applications with distinct attribute requirements to showcase usefulness for authentication and attribute-based access control within a case study. N2 - Das Identitätsmanagement ist Kernbestandteil der Sicherheitsfunktionen von Applikationen. Es unterscheidet berechtigte Benutzung von illegitimer Verwendung. Die Modelle des Identitätsmanagements haben sich vom isolierten zum zentralisierten Paradigma und darüber hinaus zu Identitätsverbünden weiterentwickelt. Im Rahmen dieser Evolution ist der Identitätsanbieter zu einer mächtigen vertrauenswürdigen dritten Partei aufgestiegen. Zur Etablierung eines bis jetzt noch unvorstellbaren Machtgleichgewichts wurde der Grundgedanke der selbstbestimmten Identität proklamiert. Eine tiefgehende Analyse des neuen Konzepts unterstützt auf essentielle Weise das generelle Verständnis der Vorzüge und Defizite. Bei der Analyse des Modells untersuchen wir zu Beginn strukturelle Komponenten des selbstbestimmten Identitätsmanagements basierend auf der Blockchain Technologie. Anschließend erforschen wir Vertrauensanforderungen in diesem Kontext anhand von Mustern. Diese schematischen Darstellungen illustrieren das Verhältnis der Hauptakteure im Verbund mit einem dezentralisierten Identitätsanbieter. Im Vergleich zu den traditionellen Paradigmen, können wir festellen, dass kein Vertrauen mehr in das Verwalten von Anmeldeinformationen und der korrekten Authentifizierung benötigt wird. Zusätzlich bewirkt die Verwendung von vertrauensfördernder Attributaggregation eine weitere Transformation der Vertrauenssituation. Darauffolgend formalisieren wir die Darstellung von Vertrauensmodellen in Attribute Assurance mit Hilfe eines Meta-Frameworks. Als zentrale Komponenten sind das Attestierungs- und Vertrauensnetzwerk sowie der Vertrauensentscheidungsprozess, einschließlich der Vertrauensfunktion, enthalten. Ein sicheres Vertrauensmodell beruht auf der Sicherheit der Vertrauensfunktion. Hohe Vertrauenswerte sowie mehrere Attributaussteller sollten dafür berücksichtigt werden. Des Weiteren evaluieren wir Klassifikation, die konzeptionelle und praktische Analyse sowie die Simulation als Untersuchungsansätze für Vertrauensmodelle. Für die Umsetzung der vertrauensfördernden Attributaggregation schlagen wir einen wahrscheinlichkeitstheoretischen Ansatz vor. Die entwickelte Methode basiert auf den primären Charakteristiken der Korrektheit und Gültigkeit von Attributen. Diese Indikatoren werden für einen und anschließend für mehrere Merkmalsanbieter kombiniert. Zusätzlich betten wir die daraus entstehende Vertrauensfunktion in ein vollständiges Modell auf Basis des Ökosystem von selbstbestimmten Identitäten ein. Für die praktische Anwendung der Vertrauensfunktion und die Überwindung mehrerer Herausforderungen für den Dienstanbieter, bei der Einführung selbstbestimmter Identitätslösungen, konzipieren und implementieren wir einen Identitätsbroker. Dieser Vermittler besteht aus einer komponentenbasierten Architektur, um von einer dedizierten selbstbestimmten Identitätslösung zu abstrahieren. Zusätzlich bilden etablierte Identitäts- und Zugriffsverwaltungsprotokolle die Schnittstelle zu herkömmlichen Anwendungen. Der Einsatz des Brokers auf der Seite des Dienstanbieters unterminiert nicht die Grundsätze der selbstbestimmten Identität. Im Gegensatz wird die Weiterentwicklung des entsprechenden Ökosystems gefördert. Innerhalb einer Fallstudie wird die Verwendung des Identitätsbrokers bei Anwendungen mit unterschiedlichen Anforderungen an Benutzerattribute betrachtet, um die Nützlichkeit bei der Authentifizierung und Attributbasierten Zugriffskontrolle zu demonstrieren. KW - identity KW - self-sovereign identity KW - trust KW - attribute assurance KW - Identität KW - selbst-souveräne Identitäten KW - Vertrauen KW - Attributsicherung Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-567450 ER - TY - THES A1 - Grütze, Toni T1 - Adding value to text with user-generated content N2 - In recent years, the ever-growing amount of documents on the Web as well as in closed systems for private or business contexts led to a considerable increase of valuable textual information about topics, events, and entities. It is a truism that the majority of information (i.e., business-relevant data) is only available in unstructured textual form. The text mining research field comprises various practice areas that have the common goal of harvesting high-quality information from textual data. These information help addressing users' information needs. In this thesis, we utilize the knowledge represented in user-generated content (UGC) originating from various social media services to improve text mining results. These social media platforms provide a plethora of information with varying focuses. In many cases, an essential feature of such platforms is to share relevant content with a peer group. Thus, the data exchanged in these communities tend to be focused on the interests of the user base. The popularity of social media services is growing continuously and the inherent knowledge is available to be utilized. We show that this knowledge can be used for three different tasks. Initially, we demonstrate that when searching persons with ambiguous names, the information from Wikipedia can be bootstrapped to group web search results according to the individuals occurring in the documents. We introduce two models and different means to handle persons missing in the UGC source. We show that the proposed approaches outperform traditional algorithms for search result clustering. Secondly, we discuss how the categorization of texts according to continuously changing community-generated folksonomies helps users to identify new information related to their interests. We specifically target temporal changes in the UGC and show how they influence the quality of different tag recommendation approaches. Finally, we introduce an algorithm to attempt the entity linking problem, a necessity for harvesting entity knowledge from large text collections. The goal is the linkage of mentions within the documents with their real-world entities. A major focus lies on the efficient derivation of coherent links. For each of the contributions, we provide a wide range of experiments on various text corpora as well as different sources of UGC. The evaluation shows the added value that the usage of these sources provides and confirms the appropriateness of leveraging user-generated content to serve different information needs. N2 - Die steigende Zahl an Dokumenten, welche in den letzten Jahren im Web sowie in geschlossenen Systemen aus dem privaten oder geschäftlichen Umfeld erstellt wurden, führte zu einem erheblichen Zuwachs an wertvollen Informationen über verschiedenste Themen, Ereignisse, Organisationen und Personen. Die meisten Informationen liegen lediglich in unstrukturierter, textueller Form vor. Das Forschungsgebiet des "Text Mining" befasst sich mit dem schwierigen Problem, hochwertige Informationen in strukturierter Form aus Texten zu gewinnen. Diese Informationen können dazu eingesetzt werden, Nutzern dabei zu helfen, ihren Informationsbedarf zu stillen. In dieser Arbeit nutzen wir Wissen, welches in nutzergenerierten Inhalten verborgen ist und aus unterschiedlichsten sozialen Medien stammt, um Text Mining Ergebnisse zu verbessern. Soziale Medien bieten eine Fülle an Informationen mit verschiedenen Schwerpunkten. Eine wesentliche Funktion solcher Medien ist es, den Nutzern zu ermöglichen, Inhalte mit ihrer Interessensgruppe zu teilen. Somit sind die ausgetauschten Daten in diesen Diensten häufig auf die Interessen der Nutzerbasis ausgerichtet. Die Popularität sozialer Medien wächst stetig und führt dazu, dass immer mehr inhärentes Wissen verfügbar wird. Dieses Wissen kann unter anderem für drei verschiedene Aufgabenstellungen genutzt werden. Zunächst zeigen wir, dass Informationen aus Wikipedia hilfreich sind, um Ergebnisse von Personensuchen im Web nach den in ihnen diskutierten Personen aufzuteilen. Dazu führen wir zwei Modelle zur Gruppierung der Ergebnisse und verschiedene Methoden zum Umgang mit fehlenden Wikipedia Einträgen ein, und zeigen, dass die entwickelten Ansätze traditionelle Methoden zur Gruppierung von Suchergebnissen übertreffen. Des Weiteren diskutieren wir, wie die Klassifizierung von Texten auf Basis von "Folksonomien" Nutzern dabei helfen kann, neue Informationen zu identifizieren, die ihren Interessen entsprechen. Wir konzentrieren uns insbesondere auf temporäre Änderungen in den nutzergenerierten Inhalten, um zu zeigen, wie stark ihr Einfluss auf die Qualität verschiedener "Tag"-Empfehlungsmethoden ist. Zu guter Letzt führen wir einen Algorithmus ein, der es ermöglicht, Nennungen von Echtweltinstanzen in Texten zu disambiguieren und mit ihren Repräsentationen in einer Wissensdatenbank zu verknüpfen. Das Hauptaugenmerk liegt dabei auf der effizienten Erkennung von kohärenten Verknüpfungen. Wir stellen für jeden Teil der Arbeit eine große Vielfalt an Experimenten auf diversen Textkorpora und unterschiedlichen Quellen von nutzergenerierten Inhalten an. Damit heben wir das Potential hervor, das die Nutzung jener Quellen bietet, um die unterschiedlichen Informationsbedürfnisse abzudecken. T2 - Mehrwert für Texte mittels nutzergenerierter Inhalte KW - nutzergenerierte Inhalte KW - text mining KW - Klassifikation KW - Clusteranalyse KW - Entitätsverknüpfung KW - user-generated content KW - text mining KW - classification KW - clustering KW - entity linking Y1 - 2018 ER - TY - THES A1 - Hagedorn, Christopher T1 - Parallel execution of causal structure learning on graphics processing units T1 - Parallele Ausführung von kausalem Strukturlernen auf Grafikprozessoren N2 - Learning the causal structures from observational data is an omnipresent challenge in data science. The amount of observational data available to Causal Structure Learning (CSL) algorithms is increasing as data is collected at high frequency from many data sources nowadays. While processing more data generally yields higher accuracy in CSL, the concomitant increase in the runtime of CSL algorithms hinders their widespread adoption in practice. CSL is a parallelizable problem. Existing parallel CSL algorithms address execution on multi-core Central Processing Units (CPUs) with dozens of compute cores. However, modern computing systems are often heterogeneous and equipped with Graphics Processing Units (GPUs) to accelerate computations. Typically, these GPUs provide several thousand compute cores for massively parallel data processing. To shorten the runtime of CSL algorithms, we design efficient execution strategies that leverage the parallel processing power of GPUs. Particularly, we derive GPU-accelerated variants of a well-known constraint-based CSL method, the PC algorithm, as it allows choosing a statistical Conditional Independence test (CI test) appropriate to the observational data characteristics. Our two main contributions are: (1) to reflect differences in the CI tests, we design three GPU-based variants of the PC algorithm tailored to CI tests that handle data with the following characteristics. We develop one variant for data assuming the Gaussian distribution model, one for discrete data, and another for mixed discrete-continuous data and data with non-linear relationships. Each variant is optimized for the appropriate CI test leveraging GPU hardware properties, such as shared or thread-local memory. Our GPU-accelerated variants outperform state-of-the-art parallel CPU-based algorithms by factors of up to 93.4× for data assuming the Gaussian distribution model, up to 54.3× for discrete data, up to 240× for continuous data with non-linear relationships and up to 655× for mixed discrete-continuous data. However, the proposed GPU-based variants are limited to datasets that fit into a single GPU’s memory. (2) To overcome this shortcoming, we develop approaches to scale our GPU-based variants beyond a single GPU’s memory capacity. For example, we design an out-of-core GPU variant that employs explicit memory management to process arbitrary-sized datasets. Runtime measurements on a large gene expression dataset reveal that our out-of-core GPU variant is 364 times faster than a parallel CPU-based CSL algorithm. Overall, our proposed GPU-accelerated variants speed up CSL in numerous settings to foster CSL’s adoption in practice and research. N2 - Das Lernen von kausalen Strukturen aus Beobachtungsdatensätzen ist eine allgegenwärtige Herausforderung im Data Science-Bereich. Die für die Algorithmen des kausalen Strukturlernens (CSL) zur Verfügung stehende Menge von Beobachtungsdaten nimmt zu, da heutzutage mit hoher Frequenz Daten aus vielen Datenquellen gesammelt werden. Während die Verarbeitung von höheren Datenmengen im Allgemeinen zu einer höheren Genauigkeit bei CSL führt, hindert die damit einhergehende Erhöhung der Laufzeit von CSL-Algorithmen deren breite Anwendung in der Praxis. CSL ist ein parallelisierbares Problem. Bestehende parallele CSL-Algorithmen eignen sich für die Ausführung auf Mehrkern-Hauptprozessoren (CPUs) mit Dutzenden von Rechenkernen. Moderne Computersysteme sind jedoch häufig heterogen. Um notwendige Berechnungen zu beschleunigen, sind die Computersysteme typischerweise mit Grafikprozessoren (GPUs) ausgestattet, wobei diese GPUs mehrere tausend Rechenkerne für eine massive parallele Datenverarbeitung bereitstellen. Um die Laufzeit von Algorithmen für das kausale Strukturlernen zu verkürzen, entwickeln wir im Rahmen dieser Arbeit effiziente Ausführungsstrategien, die die parallele Verarbeitungsleistung von GPUs nutzen. Dabei entwerfen wir insbesondere GPU-beschleunigte Varianten des PC-Algorithmus, der eine bekannte Constraint-basierte CSL-Methode ist. Dieser Algorithmus ermöglicht die Auswahl eines – den Eigenschaften der Beobachtungsdaten entsprechenden – statistischen Tests auf bedingte Unabhängigkeit (CI-Test). Wir leisten in dieser Doktorarbeit zwei wissenschaftliche Hauptbeiträge: (1) Um den Unterschieden in den CI-Tests Rechnung zu tragen, entwickeln wir drei GPU-basierte, auf CI-Tests zugeschnittene Varianten des PC-Algorithmus. Dadurch können Daten mit den folgenden Merkmalen verarbeitet werden: eine Variante fokussiert sich auf Daten, die das Gaußsche Verteilungsmodell annehmen, eine weitere auf diskrete Daten und die dritte Variante setzt den Fokus auf gemischte diskret-kontinuierliche Daten sowie Daten mit nicht-linearen funktionalen Beziehungen. Jede Variante ist für den entsprechenden CI-Test optimiert und nutzt Eigenschaften der GPU-Hardware wie beispielsweise ”Shared Memory” oder ”Thread-local Memory” aus. Unsere GPU-beschleunigten Varianten übertreffen die modernsten parallelen CPU-basierten Algorithmen um Faktoren von bis zu 93,4x für Daten, die das Gaußsche Verteilungsmodell annehmen, bis zu 54,3x für diskrete Daten, bis zu 240x für kontinuierliche Daten mit nichtlinearen Beziehungen und bis zu 655x für gemischte diskret-kontinuierliche Daten. Die vorgeschlagenen GPU-basierten Varianten sind dabei jedoch auf Datensätze beschränkt, die in den Speicher einer einzelnen GPU passen. (2) Um diese Schwachstelle zu beseitigen, entwickeln wir Ansätze zur Skalierung unserer GPU-basierten Varianten über die Speicherkapazität einer einzelnen GPU hinaus. So entwerfen wir beispielsweise eine auf einer expliziten Speicherverwaltung aufbauenden Out-of-Core-Variante für eine einzelne GPU, um Datensätze beliebiger Größe zu verarbeiten. Laufzeitmessungen auf einem großen Genexpressionsdatensatz zeigen, dass unsere Out-of-Core GPU-Variante 364-mal schneller ist als ein paralleler CPU-basierter CSL-Algorithmus. Insgesamt beschleunigen unsere vorgestellten GPU-basierten Varianten das kausale Strukturlernen in zahlreichen Situationen und unterstützen dadurch die breite Anwendung des kausalen Strukturlernens in Praxis und Forschung. KW - causal structure learning KW - GPU acceleration KW - causal discovery KW - parallel processing KW - GPU-Beschleunigung KW - kausale Entdeckung KW - kausales Strukturlernen KW - parallele Verarbeitung Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-597582 ER - TY - THES A1 - Harmouch, Hazar T1 - Single-column data profiling N2 - The research area of data profiling consists of a large set of methods and processes to examine a given dataset and determine metadata about it. Typically, different data profiling tasks address different kinds of metadata, comprising either various statistics about individual columns (Single-column Analysis) or relationships among them (Dependency Discovery). Among the basic statistics about a column are data type, header, the number of unique values (the column's cardinality), maximum and minimum values, the number of null values, and the value distribution. Dependencies involve, for instance, functional dependencies (FDs), inclusion dependencies (INDs), and their approximate versions. Data profiling has a wide range of conventional use cases, namely data exploration, cleansing, and integration. The produced metadata is also useful for database management and schema reverse engineering. Data profiling has also more novel use cases, such as big data analytics. The generated metadata describes the structure of the data at hand, how to import it, what it is about, and how much of it there is. Thus, data profiling can be considered as an important preparatory task for many data analysis and mining scenarios to assess which data might be useful and to reveal and understand a new dataset's characteristics. In this thesis, the main focus is on the single-column analysis class of data profiling tasks. We study the impact and the extraction of three of the most important metadata about a column, namely the cardinality, the header, and the number of null values. First, we present a detailed experimental study of twelve cardinality estimation algorithms. We classify the algorithms and analyze their efficiency, scaling far beyond the original experiments and testing theoretical guarantees. Our results highlight their trade-offs and point out the possibility to create a parallel or a distributed version of these algorithms to cope with the growing size of modern datasets. Then, we present a fully automated, multi-phase system to discover human-understandable, representative, and consistent headers for a target table in cases where headers are missing, meaningless, or unrepresentative for the column values. Our evaluation on Wikipedia tables shows that 60% of the automatically discovered schemata are exact and complete. Considering more schema candidates, top-5 for example, increases this percentage to 72%. Finally, we formally and experimentally show the ghost and fake FDs phenomenon caused by FD discovery over datasets with missing values. We propose two efficient scores, probabilistic and likelihood-based, for estimating the genuineness of a discovered FD. Our extensive set of experiments on real-world and semi-synthetic datasets show the effectiveness and efficiency of these scores. N2 - Das Forschungsgebiet Data Profiling besteht aus einer Vielzahl von Methoden und Prozessen, die es erlauben Datensätze zu untersuchen und Metadaten über diese zu ermitteln. Typischerweise erzeugen verschiedene Data-Profiling-Techniken unterschiedliche Arten von Metadaten, die entweder verschiedene Statistiken einzelner Spalten (Single-Column Analysis) oder Beziehungen zwischen diesen (Dependency Discovery) umfassen. Zu den grundlegenden Statistiken einer Spalte gehören unter anderem ihr Datentyp, ihr Name, die Anzahl eindeutiger Werte (Kardinalität der Spalte), Maximal- und Minimalwerte, die Anzahl an Null-Werten sowie ihre Werteverteilung. Im Falle von Abhängigkeiten kann es sich beispielsweise um funktionale Abhängigkeiten (FDs), Inklusionsabhängigkeiten (INDs) sowie deren approximative Varianten handeln. Data Profiling besitzt vielfältige Anwendungsmöglichkeiten, darunter fallen die Datenexploration, -bereinigung und -integration. Darüber hinaus sind die erzeugten Metadaten sowohl für den Einsatz in Datenbankmanagementsystemen als auch für das Reverse Engineering von Datenbankschemata hilfreich. Weiterhin finden Methoden des Data Profilings immer häufiger Verwendung in neuartigen Anwendungsfällen, wie z.B. der Analyse von Big Data. Dabei beschreiben die generierten Metadaten die Struktur der vorliegenden Daten, wie diese zu importieren sind, von was sie handeln und welchen Umfang sie haben. Somit kann das Profiling von Datenbeständen als eine wichtige, vorbereitende Aufgabe für viele Datenanalyse- und Data-Mining Szenarien angesehen werden. Sie ermöglicht die Beurteilung, welche Daten nützlich sein könnten, und erlaubt es zudem die Eigenschaften eines neuen Datensatzes aufzudecken und zu verstehen. Der Schwerpunkt dieser Arbeit bildet das Single-Column Profiling. Dabei werden sowohl die Auswirkungen als auch die Extraktion von drei der wichtigsten Metadaten einer Spalte untersucht, nämlich ihrer Kardinalität, ihres Namens und ihrer Anzahl an Null-Werten. Die vorliegende Arbeit beginnt mit einer detaillierten experimentellen Studie von zwölf Algorithmen zur Kardinalitätsschätzung. Diese Studie klassifiziert die Algorithmen anhand verschiedener Kriterien und analysiert ihre Effizienz. Dabei sind die Experimente im Vergleich zu den Originalpublikationen weitaus umfassender und testen die theoretischen Garantien der untersuchten Algorithmen. Unsere Ergebnisse geben Aufschluss über Abwägungen zwischen den Algorithmen und weisen zudem auf die Möglichkeit einer parallelen bzw. verteilten Algorithmenversion hin, wodurch die stetig anwachsende Datenmenge moderner Datensätze bewältigt werden könnten. Anschließend wird ein vollautomatisches, mehrstufiges System vorgestellt, mit dem sich im Falle fehlender, bedeutungsloser oder nicht repräsentativer Kopfzeilen einer Zieltabelle menschenverständliche, repräsentative und konsistente Kopfzeilen ermitteln lassen. Unsere Auswertung auf Wikipedia-Tabellen zeigt, dass 60% der automatisch entdeckten Schemata exakt und vollständig sind. Werden darüber hinaus mehr Schemakandidaten in Betracht gezogen, z.B. die Top-5, erhöht sich dieser Prozentsatz auf 72%. Schließlich wird das Phänomen der Geist- und Schein-FDs formell und experimentell untersucht, welches bei der Entdeckung von FDs auf Datensätzen mit fehlenden Werten auftreten kann. Um die Echtheit einer entdeckten FD effizient abzuschätzen, schlagen wir sowohl eine probabilistische als auch eine wahrscheinlichkeitsbasierte Bewertungsmethode vor. Die Wirksamkeit und Effizienz beider Bewertungsmethoden zeigt sich in unseren umfangreichen Experimenten mit realen und halbsynthetischen Datensätzen. KW - Data profiling KW - Functional dependencies KW - Data quality KW - Schema discovery KW - Cardinality estimation KW - Metanome KW - Missing values KW - Kardinalitätsschätzung KW - Datenqualität KW - Funktionale Abhängigkeiten KW - Fehlende Werte KW - Schema-Entdeckung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-474554 ER - TY - THES A1 - Herzberg, Nico T1 - Integrating events into non-automated business process environments BT - enabling transparency, traceability, and optimization for business processes driven by humans Y1 - 2018 ER - TY - THES A1 - Hesse, Guenter T1 - A benchmark for enterprise stream processing architectures T1 - Ein Benchmark für Architekturen zur Datenstromverarbeitung im Unternehmenskontext N2 - Data stream processing systems (DSPSs) are a key enabler to integrate continuously generated data, such as sensor measurements, into enterprise applications. DSPSs allow to steadily analyze information from data streams, e.g., to monitor manufacturing processes and enable fast reactions to anomalous behavior. Moreover, DSPSs continuously filter, sample, and aggregate incoming streams of data, which reduces the data size, and thus data storage costs. The growing volumes of generated data have increased the demand for high-performance DSPSs, leading to a higher interest in these systems and to the development of new DSPSs. While having more DSPSs is favorable for users as it allows choosing the system that satisfies their requirements the most, it also introduces the challenge of identifying the most suitable DSPS regarding current needs as well as future demands. Having a solution to this challenge is important because replacements of DSPSs require the costly re-writing of applications if no abstraction layer is used for application development. However, quantifying performance differences between DSPSs is a difficult task. Existing benchmarks fail to integrate all core functionalities of DSPSs and lack tool support, which hinders objective result comparisons. Moreover, no current benchmark covers the combination of streaming data with existing structured business data, which is particularly relevant for companies. This thesis proposes a performance benchmark for enterprise stream processing called ESPBench. With enterprise stream processing, we refer to the combination of streaming and structured business data. Our benchmark design represents real-world scenarios and allows for an objective result comparison as well as scaling of data. The defined benchmark query set covers all core functionalities of DSPSs. The benchmark toolkit automates the entire benchmark process and provides important features, such as query result validation and a configurable data ingestion rate. To validate ESPBench and to ease the use of the benchmark, we propose an example implementation of the ESPBench queries leveraging the Apache Beam software development kit (SDK). The Apache Beam SDK is an abstraction layer designed for developing stream processing applications that is applied in academia as well as enterprise contexts. It allows to run the defined applications on any of the supported DSPSs. The performance impact of Apache Beam is studied in this dissertation as well. The results show that there is a significant influence that differs among DSPSs and stream processing applications. For validating ESPBench, we use the example implementation of the ESPBench queries developed using the Apache Beam SDK. We benchmark the implemented queries executed on three modern DSPSs: Apache Flink, Apache Spark Streaming, and Hazelcast Jet. The results of the study prove the functioning of ESPBench and its toolkit. ESPBench is capable of quantifying performance characteristics of DSPSs and of unveiling differences among systems. The benchmark proposed in this thesis covers all requirements to be applied in enterprise stream processing settings, and thus represents an improvement over the current state-of-the-art. N2 - Data Stream Processing Systems (DSPSs) sind eine Schlüsseltechnologie, um kontinuierlich generierte Daten, wie beispielsweise Sensormessungen, in Unternehmensanwendungen zu integrieren. Die durch DSPSs ermöglichte permanente Analyse von Datenströmen kann dabei zur Überwachung von Produktionsprozessen genutzt werden, um möglichst zeitnah auf ungewollte Veränderungen zu reagieren. Darüber hinaus filtern, sampeln und aggregieren DSPSs einkommende Daten, was die Datengröße reduziert und so auch etwaige Kosten für die Datenspeicherung. Steigende Datenvolumen haben in den letzten Jahren den Bedarf für performante DSPSs steigen lassen, was zur Entwicklung neuer DSPSs führte. Während eine große Auswahl an verfügbaren Systemen generell gut für Nutzer ist, stellt es potentielle Anwender auch vor die Herausforderung, das für aktuelle und zukünftige Anforderungen passendste DSPS zu identifizieren. Es ist wichtig, eine Lösung für diese Herausforderung zu haben, da das Austauschen von einem DSPS zu teuren Anpassungen oder Neuentwicklungen der darauf laufenden Anwendungen erfordert, falls für deren Entwicklung keine Abstraktionsschicht verwendet wurde. Das quantitative Vergleichen von DSPSs ist allerdings eine schwierige Aufgabe. Existierende Benchmarks decken nicht alle Kernfunktionalitäten von DSPSs ab und haben keinen oder unzureichenden Tool-Support, was eine objektive Ergebnisberechnung hinsichtlich der Performanz erschwert. Zudem beinhaltet kein Benchmark die Integration von Streamingdaten und strukturierten Geschäftsdaten, was ein besonders für Unternehmen relevantes Szenario ist. Diese Dissertation stellt ESPBench vor, einen neuen Benchmark für Stream Processing-Szenarien im Unternehmenskontext. Der geschäftliche Kontext wird dabei durch die Verbindung von Streamingdaten und Geschäftsdaten dargestellt. Das Design von ESPBench repräsentiert Szenarien der realen Welt, stellt die objektive Berechnung von Benchmarkergebnissen sicher und erlaubt das Skalieren über Datencharakteristiken. Das entwickelte Toolkit des Benchmarks stellt wichtige Funktionalitäten bereit, wie beispielsweise die Automatisierung den kompletten Benchmarkprozesses sowie die Überprüfung der Abfrageergebnisse hinsichtlich ihrer Korrektheit. Um ESPBench zu validieren und die Anwendung weiter zu vereinfachen, haben wir eine Beispielimplementierung der Queries veröffentlicht. Die Implementierung haben wir mithilfe des in Industrie und Wissenschaft eingesetzten Softwareentwicklungsbaukastens Apache Beam durchgeführt, der es ermöglicht, entwickelte Anwendungen auf allen unterstützten DSPSs auszuführen. Den Einfluss auf die Performanz des Verwendens von Apache Beam wird dabei ebenfalls in dieser Arbeit untersucht. Weiterhin nutzen wir die veröffentlichte Beispielimplementierung der Queries um drei moderne DSPSs mit ESPBench zu untersuchen: Apache Flink, Apache Spark Streaming und Hazelcast Jet. Der Ergebnisse der Studie verdeutlichen die Funktionsfähigkeit von ESPBench und dessen Toolkit. ESPBench befähigt Performanzcharakteristiken von DSPSs zu quantifizieren und Unterschiede zwischen Systemen aufzuzeigen. Der in dieser Dissertation vorgestellte Benchmark erfüllt alle Anforderungen, um in Stream Processing-Szenarien im Unternehmenskontext eingesetzt zu werden und stellt somit eine Verbesserung der aktuellen Situation dar. KW - stream processing KW - performance KW - benchmarking KW - dsps KW - espbench KW - benchmark KW - Performanz KW - Datenstromverarbeitung KW - Benchmark Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-566000 ER - TY - THES A1 - Hildebrandt, Dieter T1 - Service-oriented 3D geovisualization systems T1 - Serviceorientierte 3D-Geovisualisierungssysteme N2 - 3D geovisualization systems (3DGeoVSs) that use 3D geovirtual environments as a conceptual and technical framework are increasingly used for various applications. They facilitate obtaining insights from ubiquitous geodata by exploiting human abilities that other methods cannot provide. 3DGeoVSs are often complex and evolving systems required to be adaptable and to leverage distributed resources. Designing a 3DGeoVS based on service-oriented architectures, standards, and image-based representations (SSI) facilitates resource sharing and the agile and efficient construction and change of interoperable systems. In particular, exploiting image-based representations (IReps) of 3D views on geodata supports taking full advantage of the potential of such system designs by providing an efficient, decoupled, interoperable, and increasingly applied representation. However, there is insufficient knowledge on how to build service-oriented, standards-based 3DGeoVSs that exploit IReps. This insufficiency is substantially due to technology and interoperability gaps between the geovisualization domain and further domains that such systems rely on. This work presents a coherent framework of contributions that support designing the software architectures of targeted systems and exploiting IReps for providing, styling, and interacting with geodata. The contributions uniquely integrate existing concepts from multiple domains and novel contributions for identified limitations. The proposed software reference architecture (SRA) for 3DGeoVSs based on SSI facilitates designing concrete software architectures of such systems. The SRA describes the decomposition of 3DGeoVSs into a network of services and integrates the following contributions to facilitate exploiting IReps effectively and efficiently. The proposed generalized visualization pipeline model generalizes the prevalent visualization pipeline model and overcomes its expressiveness limitations with respect to transforming IReps. The proposed approach for image-based provisioning enables generating and supplying service consumers with image-based views (IViews). IViews act as first-class data entities in the communication between services and provide a suitable IRep and encoding of geodata. The proposed approach for image-based styling separates concerns of styling from image generation and enables styling geodata uniformly represented as IViews specified as algebraic compositions of high-level styling operators. The proposed approach for interactive image-based novel view generation enables generating new IViews from existing IViews in response to interactive manipulations of the viewing camera and includes an architectural pattern that generalizes common novel view generation. The proposed interactive assisting, constrained 3D navigation technique demonstrates how a navigation technique can be built that supports users in navigating multiscale virtual 3D city models, operates in 3DGeoVSs based on SSI as an application of the SRA, can exploit IReps, and can support collaborating services in exploiting IReps. The validity of the contributions is supported by proof-of-concept prototype implementations and applications and effectiveness and efficiency studies including a user study. Results suggest that this work promises to support designing 3DGeoVSs based on SSI that are more effective and efficient and that can exploit IReps effectively and efficiently. This work presents a template software architecture and key building blocks for building novel IT solutions and applications for geodata, e.g., as components of spatial data infrastructures. N2 - 3D-Geovisualisierungssysteme (3DGeoVSs), die geovirtuelle 3D-Umgebungen als konzeptionellen und technischen Rahmen nutzen, werden zunehmend für verschiedene Anwendungen eingesetzt. Sie erleichtern es durch die Ausnutzung menschlicher Fähigkeiten Erkenntnisse aus allgegenwärtigen Geodaten zu gewinnen, die andere Methoden nicht liefern können. 3DGeoVSs sind oft komplexe und kontinuierlich weiter entwickelte Systeme, die anpassungsfähig sein müssen und auf die Nutzung verteilter Ressourcen angewiesen sind. Die Entwicklung eines 3DGeoVS auf der Basis von serviceorientierten Architekturen, Standards und bildbasierten Repräsentationen (SSI) erleichtert die gemeinsame Nutzung von verteilten Ressourcen und die agile und effiziente Entwicklung und Änderung von interoperablen Systemen. Insbesondere unterstützt die Nutzung bildbasierter Repräsentationen (IReps) von 3D-Ansichten auf Geodaten die vollständige Realisierung des Potenzials solcher Systementwürfe durch die Bereitstellung einer effizienten, entkoppelten, interoperablen und zunehmend verwendeten Repräsentationsform. Es besteht jedoch ein Mangel an Wissen darüber, wie 3DGeoVSs entwickelt werden können, die auf serviceorientierten Architekturen und Standards basieren und IReps ausnutzen können. Dieser Mangel ist wesentlich zurückzuführen auf die Technologie- und Interoperabilitätslücken zwischen dem Bereich der Geovisualisierung und weiteren Bereichen, auf die solche Systeme angewiesen sind. Diese Arbeit präsentiert ein kohärentes Rahmenwerk von Beiträgen, die dabei unterstützen können, die Softwarearchitekturen betrachteter Systeme zu entwerfen und IReps für die Bereitstellung, die visuelle Gestaltung und die Interaktion mit Geodaten zu nutzen. Die Beiträge integrieren auf besondere Weise vorhandene Konzepte aus unterschiedlichen Bereichen und neuartige Lösungen für identifizierte Einschränkungen bisheriger Ansätze. Die vorgeschlagene Software-Referenzarchitektur (SRA) für 3DGeoVSs unterstützt den Entwurf konkreter Softwarearchitekturen betrachteter Systemen. Sie beschreibt die Zerlegung von 3DGeoVSs in ein Netzwerk von Diensten. Um IReps effektiv und effizient nutzen zu können, integriert sie zudem die folgenden Beiträge. Das vorgeschlagene generalisierte Visualisierungspipelinemodell generalisiert das weit verbreitete Visualisierungspipelinemodell und überwindet dessen Einschränkungen in Bezug auf die Verarbeitung von IReps. Der vorgeschlagene Ansatz für die bildbasierte Bereitstellung von Geodaten ermöglicht es bildbasierte Sichten (IViews) zu erzeugen und Dienstkonsumenten mit ihnen zu versorgen. IViews sind erstrangige Datenentitäten in der Kommunikation zwischen Diensten und stellen eine geeignete IRep und Kodierung von Geodaten dar. Der vorgeschlagene Ansatz für die bildbasierte, visuelle Gestaltung trennt die Zuständigkeiten der Erzeugung eines Bildes von denen der visuellen Gestaltung des Bildes. Der Ansatz ermöglicht die visuelle Gestaltung von einheitlich durch IViews repräsentierten Geodaten. Die visuelle Gestaltung wird dabei durch die algebraische Komposition abstrakter Gestaltungsoperatoren spezifiziert. Der vorgeschlagene Ansatz für die interaktive Bilderzeugung ermöglicht es als Reaktion auf interaktive Manipulationen der Betrachtungskamera neue, durch IViews repräsentierte 3D-Ansichten von Geodaten aus bestehenden 3D-Ansichten zu erzeugen. Der Ansatz umfasst ein Architekturmuster, das bisherige Ansätze zusammenfasst und verallgemeinert. Die vorgeschlagene assistierenden, einschränkenden 3D-Navigationstechnik demonstriert, wie eine interaktive Navigationstechnik entwickelt werden kann, die Nutzer beim Navigieren in multiskalaren virtuellen 3D Stadtmodellen unterstützt, als Anwendung der vorgeschlagenen SRA in SSI-basierten 3DGeoVSs funktioniert und für diesen Zweck sowohl IReps nutzt, als auch andere Dienste bei der Nutzung von IReps unterstützt. Die Validität der Beiträge dieser Arbeit wird gestützt durch prototypische Implementierungen und Anwendungen, sowie Effektivitäts- und Effizienzstudien einschließlich einer Nutzerstudie. Die Ergebnisse deuten darauf hin, dass diese Arbeit dabei unterstützen kann, 3DGeoVSs basierend auf SSI zu entwerfen, die sowohl effektiver und effizienter sind, als auch IReps effektiv und effizient nutzen können. Diese Arbeit stellt eine Muster-Softwarearchitektur und Schlüsselbausteine für die Entwicklung neuartiger IT-Lösungen und -Anwendungen für Geodaten vor, die sich beispielsweise in Geodateninfrastrukturen integrieren lassen. KW - 3D geovisualization system KW - 3D geovirtual environment KW - service-oriented architecture (SOA) KW - standard KW - image-based representation KW - 3D-Geovisualisierungssystem KW - 3D-geovirtuelle Umgebung KW - Serviceorientierte Architektur (SOA) KW - Standard KW - bildbasierte Repräsentation Y1 - 2017 ER - TY - THES A1 - Ion, Alexandra T1 - Metamaterial devices T1 - Metamaterial-Geräte N2 - Digital fabrication machines such as 3D printers excel at producing arbitrary shapes, such as for decorative objects. In recent years, researchers started to engineer not only the outer shape of objects, but also their internal microstructure. Such objects, typically based on 3D cell grids, are known as metamaterials. Metamaterials have been used to create materials that, e.g., change their volume, or have variable compliance. While metamaterials were initially understood as materials, we propose to think of them as devices. We argue that thinking of metamaterials as devices enables us to create internal structures that offer functionalities to implement an input-process-output model without electronics, but purely within the material’s internal structure. In this thesis, we investigate three aspects of such metamaterial devices that implement parts of the input-process-output model: (1) materials that process analog inputs by implementing mechanisms based on their microstructure, (2) that process digital signals by embedding mechanical computation into the object’s microstructure, and (3) interactive metamaterial objects that output to the user by changing their outside to interact with their environment. The input to our metamaterial devices is provided directly by the users interacting with the device by means of physically pushing the metamaterial, e.g., turning a handle, pushing a button, etc. The design of such intricate microstructures, which enable the functionality of metamaterial devices, is not obvious. The complexity of the design arises from the fact that not only a suitable cell geometry is necessary, but that additionally cells need to play together in a well-defined way. To support users in creating such microstructures, we research and implement interactive design tools. These tools allow experts to freely edit their materials, while supporting novice users by auto-generating cells assemblies from high-level input. Our tools implement easy-to-use interactions like brushing, interactively simulate the cell structures’ deformation directly in the editor, and export the geometry as a 3D-printable file. Our goal is to foster more research and innovation on metamaterial devices by allowing the broader public to contribute. N2 - Digitale Fabrikationsmaschinen, wie 3D-Drucker, eignen sich hervorragend um beliebige Formen zu produzieren. Daher sind sie bei Endnutzern für die Erstellung von dekorativen Elementen sehr beliebt. Forscher hingegen haben in den letzten Jahren damit begonnen, nicht nur die äußere Form zu betrachten, sondern auch Mikrostrukturen im Inneren. Solche Strukturen, die meist auf einem 3-dimensionalen Gitter angeordnet sind, sind als "Metamaterialien" bekannt. Metamaterialien wurden entwickelt, um Eigenschaften wie Volumenänderung oder lokalisiert die Steifheit des Materials zu steuern. Traditionell werden Metamaterialien als Materialien betrachtet, wir hingegen betrachten sie als Geräte. In dieser Arbeit zeigen wir, dass die Betrachtung von Metamaterialien als Geräte es erlaubt Strukturen zu kreieren, die Geräte nach dem Eingabe-Verarbeitung-Ausgabe Prinzip realisieren -- und das gänzlich ohne Elektronik. Wir untersuchen 3 Aspekte von solchen funktionsfähigen Metamaterial-Geräten die jeweils Teile des EVA Prinzips implementieren: (1) Materialien, die analoge Eingabe als Mechanismen, die durch ihre Mikrostruktur bestimmt sind, verarbeiten, (2) Materialien, die digitale Eingabe verarbeiten und mechanische Berechnungen in ihrer Mikrostruktur durchführen und (3) Materialien, die ihre äußere Textur dynamisch verändern können um mit dem Nutzer zu kommunizieren. Die Eingabe für Metamaterial-Geräte ist in dieser Arbeit direkt durch den Nutzer gegeben, der mit dem Gerät interagiert, zum Beispiel durch Drücken eines Griffs, eines Knopfes, etc. Das Design von solchen filigranen Mikrostrukturen, die die Funktionalität der Metamaterial-Geräte definieren, ist nicht offensichtlich oder einfach. Der Designprozess ist komplex, weil nicht nur eine Zellstruktur gefunden werden muss, die die gewünschte Deformation durchführt, sondern die Zellstrukturen zusätzlich auf wohldefinierte Weise zusammenspielen müssen. Um Nutzern die Erstellung von diesen Mikrostrukturen zu ermöglichen, unterstützen wir sie durch interaktive Computerprogramme, die wir in dieser Arbeit untersuchen und implementieren. Wir haben Software entwickelt, die es Experten erlaubt die Mikrostrukturen frei zu platzieren und zu editieren, während Laien durch automatisch generierte Strukturen geholfen wird. Unsere Software beinhaltet einfach zu bedienende Interaktionskonzepte, wie zum Beispiel das aufmalen von funktionalen Eigenschaften auf Objekte, eine integrierte Vorschau der Deformation, oder der 3D-druckfähige Export der erstellten Geometrie. Das Ziel dieser Arbeit ist es langfristig Forschung und Innovation von Metamaterial-Geräten zu fördern, so dass sich sogar die breite Masse in das Thema einbringen kann. KW - metamaterials KW - computational design KW - fabrication KW - 3D printing KW - programmable matter KW - Metamaterialien KW - computergestützte Gestaltung KW - Fabrikation KW - 3D-Druck KW - programmierbare Materie Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-429861 ER - TY - THES A1 - Jaeger, David T1 - Enabling Big Data security analytics for advanced network attack detection T1 - Ermöglichung von Big Data Sicherheitsanalysen für erweiterte Angriffserkennung in Netzwerken N2 - The last years have shown an increasing sophistication of attacks against enterprises. Traditional security solutions like firewalls, anti-virus systems and generally Intrusion Detection Systems (IDSs) are no longer sufficient to protect an enterprise against these advanced attacks. One popular approach to tackle this issue is to collect and analyze events generated across the IT landscape of an enterprise. This task is achieved by the utilization of Security Information and Event Management (SIEM) systems. However, the majority of the currently existing SIEM solutions is not capable of handling the massive volume of data and the diversity of event representations. Even if these solutions can collect the data at a central place, they are neither able to extract all relevant information from the events nor correlate events across various sources. Hence, only rather simple attacks are detected, whereas complex attacks, consisting of multiple stages, remain undetected. Undoubtedly, security operators of large enterprises are faced with a typical Big Data problem. In this thesis, we propose and implement a prototypical SIEM system named Real-Time Event Analysis and Monitoring System (REAMS) that addresses the Big Data challenges of event data with common paradigms, such as data normalization, multi-threading, in-memory storage, and distributed processing. In particular, a mostly stream-based event processing workflow is proposed that collects, normalizes, persists and analyzes events in near real-time. In this regard, we have made various contributions in the SIEM context. First, we propose a high-performance normalization algorithm that is highly parallelized across threads and distributed across nodes. Second, we are persisting into an in-memory database for fast querying and correlation in the context of attack detection. Third, we propose various analysis layers, such as anomaly- and signature-based detection, that run on top of the normalized and correlated events. As a result, we demonstrate our capabilities to detect previously known as well as unknown attack patterns. Lastly, we have investigated the integration of cyber threat intelligence (CTI) into the analytical process, for instance, for correlating monitored user accounts with previously collected public identity leaks to identify possible compromised user accounts. In summary, we show that a SIEM system can indeed monitor a large enterprise environment with a massive load of incoming events. As a result, complex attacks spanning across the whole network can be uncovered and mitigated, which is an advancement in comparison to existing SIEM systems on the market. N2 - Die letzten Jahre haben gezeigt, dass die Komplexität von Angriffen auf Unternehmensnetzwerke stetig zunimmt. Herkömmliche Sicherheitslösungen, wie Firewalls, Antivirus-Programme oder generell Intrusion Detection Systeme (IDS), sind nicht mehr ausreichend, um Unternehmen vor solch ausgefeilten Angriffen zu schützen. Ein verbreiteter Lösungsansatz für dieses Problem ist das Sammeln und Analysieren von Ereignissen innerhalb des betroffenen Unternehmensnetzwerks mittels Security Information and Event Management (SIEM) Systemen. Die Mehrheit der derzeitigen SIEM-Lösungen auf dem Markt ist allerdings nicht in er Lage, das riesige Datenvolumen und die Vielfalt der Ereignisdarstellungen zu bewältigen. Auch wenn diese Lösungen die Daten an einem zentralen Ort sammeln können, können sie weder alle relevanten Informationen aus den Ereignissen extrahieren noch diese über verschiedene Quellen hinweg korrelieren. Aktuell werden daher nur relativ einfache Angriffe erkannt, während komplexe mehrstufige Angriffe unentdeckt bleiben. Zweifellos stehen Sicherheitsverantwortliche großer Unternehmen einem typischen Big Data-Problem gegenüber. In dieser Arbeit wird ein prototypisches SIEM-System vorgeschlagen und implementiert, welches den Big Data-Anforderungen von Ereignisdaten mit gängigen Paradigmen, wie Datennormalisierung, Multithreading, In-Memory/Speicherung und verteilter Verarbeitung begegnet. Insbesondere wird ein größtenteils stream-basierter Workflow für die Ereignisverarbeitung vorgeschlagen, der Ereignisse in nahezu Echtzeit erfasst, normalisiert, persistiert und analysiert. In diesem Zusammenhang haben wir verschiedene Beiträge im SIEM-Kontext geleistet. Erstens schlagen wir einen Algorithmus für die Hochleistungsnormalisierung vor, der, über Threads hinweg, hochgradig parallelisiert und auf Knoten verteilt ist. Zweitens persistieren wir in eine In-Memory-Datenbank, um im Rahmen der Angriffserkennung eine schnelle Abfrage und Korrelation von Ereignissen zu ermöglichen. Drittens schlagen wir verschiedene Analyseansätze, wie beispielsweise die anomalie- und musterbasierte Erkennung, vor, die auf normalisierten und korrelierten Ereignissen basieren. Damit können wir bereits bekannte als auch bisher unbekannte Arten von Angriffen erkennen. Zuletzt haben wir die Integration von sogenannter Cyber Threat Intelligence (CTI) in den Analyseprozess untersucht. Als Beispiel erfassen wir veröffentlichte Identitätsdiebstähle von großen Dienstanbietern, um Nutzerkonten zu identifizieren, die möglicherweise in nächster Zeit durch den Missbrauch verloren gegangener Zugangsdaten kompromittiert werden könnten. Zusammenfassend zeigen wir, dass ein SIEM-System tatsächlich ein großes Unternehmensnetzwerk mit einer massiven Menge an eingehenden Ereignissen überwachen kann. Dadurch können komplexe Angriffe, die sich über das gesamte Netzwerk erstrecken, aufgedeckt und abgewehrt werden. Dies ist ein Fortschritt gegenüber den auf dem Markt vorhandenen SIEM-Systemen. KW - intrusion detection KW - Angriffserkennung KW - network security KW - Netzwerksicherheit KW - Big Data KW - Big Data KW - event normalization KW - Ereignisnormalisierung KW - SIEM KW - SIEM KW - IDS KW - IDS KW - multi-step attack KW - mehrstufiger Angriff Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-435713 ER - TY - THES A1 - Jain, Nitisha T1 - Representation and curation of knowledge graphs with embeddings N2 - Knowledge graphs are structured repositories of knowledge that store facts about the general world or a particular domain in terms of entities and their relationships. Owing to the heterogeneity of use cases that are served by them, there arises a need for the automated construction of domain- specific knowledge graphs from texts. While there have been many research efforts towards open information extraction for automated knowledge graph construction, these techniques do not perform well in domain-specific settings. Furthermore, regardless of whether they are constructed automatically from specific texts or based on real-world facts that are constantly evolving, all knowledge graphs inherently suffer from incompleteness as well as errors in the information they hold. This thesis investigates the challenges encountered during knowledge graph construction and proposes techniques for their curation (a.k.a. refinement) including the correction of semantic ambiguities and the completion of missing facts. Firstly, we leverage existing approaches for the automatic construction of a knowledge graph in the art domain with open information extraction techniques and analyse their limitations. In particular, we focus on the challenging task of named entity recognition for artwork titles and show empirical evidence of performance improvement with our proposed solution for the generation of annotated training data. Towards the curation of existing knowledge graphs, we identify the issue of polysemous relations that represent different semantics based on the context. Having concrete semantics for relations is important for downstream appli- cations (e.g. question answering) that are supported by knowledge graphs. Therefore, we define the novel task of finding fine-grained relation semantics in knowledge graphs and propose FineGReS, a data-driven technique that discovers potential sub-relations with fine-grained meaning from existing pol- ysemous relations. We leverage knowledge representation learning methods that generate low-dimensional vectors (or embeddings) for knowledge graphs to capture their semantics and structure. The efficacy and utility of the proposed technique are demonstrated by comparing it with several baselines on the entity classification use case. Further, we explore the semantic representations in knowledge graph embed- ding models. In the past decade, these models have shown state-of-the-art results for the task of link prediction in the context of knowledge graph comple- tion. In view of the popularity and widespread application of the embedding techniques not only for link prediction but also for different semantic tasks, this thesis presents a critical analysis of the embeddings by quantitatively measuring their semantic capabilities. We investigate and discuss the reasons for the shortcomings of embeddings in terms of the characteristics of the underlying knowledge graph datasets and the training techniques used by popular models. Following up on this, we propose ReasonKGE, a novel method for generating semantically enriched knowledge graph embeddings by taking into account the semantics of the facts that are encapsulated by an ontology accompanying the knowledge graph. With a targeted, reasoning-based method for generating negative samples during the training of the models, ReasonKGE is able to not only enhance the link prediction performance, but also reduce the number of semantically inconsistent predictions made by the resultant embeddings, thus improving the quality of knowledge graphs. N2 - Wissensgraphen sind strukturierte Wissenssammlungen, die Fakten über die allgemeine Welt oder eine bestimmte Dom¨ane in Form von Entitäten und deren Beziehungen speichern. Aufgrund der Heterogenität der Anwendungsfälle, für die sie verwendet werden, besteht ein Bedarf an der automatischen Erstellung von domänenspezifischen Wissensgraphen aus Texten. Obwohl es viele Forschungsbem¨uhungen in Richtung offener Informationsextraktion für die automatische Konstruktion von Wissensgraphen gegeben hat, sind diese Techniken in domänenspezifischen Umgebungen nicht sehr leistungsfähig. Darüber hinaus leiden alle Wissensgraphen, unabhängig davon, ob sie automatisch aus spezifischen Texten oder auf der Grundlage realer Fakten, die sich ständig weiterentwickeln, konstruiert werden, unter Unvollständigkeit und Fehlern in den darin enthaltenen Informationen. Diese Arbeit untersucht die Herausforderungen, die bei der Konstruktion von Wissensgraphen auftreten, und schlägt Techniken zu ihrer Kuratierung (auch bekannt als Verfeinerung) vor, einschließlich der Korrektur semantischer Mehrdeutigkeiten und der Vervollständigung fehlender Fakten. Zunächst nutzen wir bestehende Ansätze für die automatische Erstellung eines Wissensgraphen im Kunstbereich mit offenen Informationsextraktionstechniken und analysieren deren Grenzen. Insbesondere konzentrieren wir uns auf die anspruchsvolle Aufgabe der Named Entity Recognition für Kunstwerke und zeigen empirische Belege für eine Leistungsverbesserung mit der von uns vorgeschlagenen Lösung für die Generierung von annotierten Trainingsdaten. Im Hinblick auf die Kuratierung bestehender Wissensgraphen identifizieren wir das Problem polysemer Relationen, die je nach Kontext unterschiedliche Semantiken repräsentieren. Konkrete Semantiken für Relationen sind wichtig für nachgelagerte Anwendungen (z.B. Fragenbeantwortung), die durch Wissensgraphen unterstützt werden. Daher definieren wir die neuartige Aufgabe, feinkörnige Relationssemantiken in Wissensgraphen zu finden und schlagen FineGReS vor, eine datengesteuerte Technik, die eine datengesteuerte Technik, die potenzielle Unterbeziehungen mit feinkörniger Bedeutung aus bestehenden polysemen Beziehungen entdeckt. Wir nutzen Lernmethoden zur Wissensrepräsentation, die niedrigdimensionale Vektoren (oder Einbettungen) für Wissensgraphen erzeugen, um deren Semantik und Struktur zu erfassen. Die Wirksamkeit und Nützlichkeit der vorgeschlagenen Technik wird durch den Vergleich mit verschiedenen Basisverfahren im Anwendungsfall der Entitätsklassifizierung demonstriert. Darüber hinaus untersuchen wir die semantischen Repräsentationen in Modellen zur Einbettung von Wissensgraphen. In den letzten zehn Jahren haben diese Modelle in den letzten zehn Jahren die besten Ergebnisse bei der Vorhersage von Links im Zusammenhang mit der Vervollständigung von Wissensgraphen erzielt. Angesichts der Popularität und der weit verbreiteten Anwendung der Einbettungstechniken nicht nur für die Linkvorhersage, sondern auch für andere semantische Aufgaben, wird in dieser Arbeit eine kritische Analyse der Einbettungen durch quantitative Messung ihrer semantischen Fähigkeiten vorgenommen. Wir untersuchen und diskutieren die Gründe für die Unzulänglichkeiten von Einbettungen in Bezug auf die Eigenschaften der zugrundeliegenden Wissensgraphen-Datensätze und die von den populären Modellen verwendeten Trainingstechniken. Darauf aufbauend schlagen wir ReasonKGE vor, eine neuartige Methode zur Erzeugung semantisch angereicherter Wissensgrapheneinbettungen durch Berücksichtigung der Semantik der Fakten, die durch eine den Wissensgraphen begleitende Ontologie gekapselt sind. Mit einer gezielten, schlussfolgernden Methode zur Erzeugung von Negativproben während des Trainings der Modelle ist ReasonKGE in der Lage, nicht nur die Leistung der Link-Vorhersage zu verbessern, sondern auch die Anzahl der semantisch inkonsistenten Vorhersagen der resultierenden Einbettungen zu reduzieren und damit die Qualität der Wissensgraphen zu verbessern. KW - knowledge graphs KW - embeddings KW - knowledge graph construction KW - knowledge graph refinement KW - domain-specific knowledge graphs KW - named entity recognition KW - semantic representations KW - domänenspezifisches Wissensgraphen KW - Einbettungen KW - Konstruktion von Wissensgraphen KW - Wissensgraphen Verfeinerung KW - Wissensgraphen KW - Named-Entity-Erkennung KW - semantische Repräsentationen Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-612240 ER - TY - THES A1 - Jiang, Lan T1 - Discovering metadata in data files N2 - It is estimated that data scientists spend up to 80% of the time exploring, cleaning, and transforming their data. A major reason for that expenditure is the lack of knowledge about the used data, which are often from different sources and have heterogeneous structures. As a means to describe various properties of data, metadata can help data scientists understand and prepare their data, saving time for innovative and valuable data analytics. However, metadata do not always exist: some data file formats are not capable of storing them; metadata were deleted for privacy concerns; legacy data may have been produced by systems that were not designed to store and handle meta- data. As data are being produced at an unprecedentedly fast pace and stored in diverse formats, manually creating metadata is not only impractical but also error-prone, demanding automatic approaches for metadata detection. In this thesis, we are focused on detecting metadata in CSV files – a type of plain-text file that, similar to spreadsheets, may contain different types of content at arbitrary positions. We propose a taxonomy of metadata in CSV files and specifically address the discovery of three different metadata: line and cell type, aggregations, and primary keys and foreign keys. Data are organized in an ad-hoc manner in CSV files, and do not follow a fixed structure, which is assumed by common data processing tools. Detecting the structure of such files is a prerequisite of extracting information from them, which can be addressed by detecting the semantic type, such as header, data, derived, or footnote, of each line or each cell. We propose the supervised- learning approach Strudel to detect the type of lines and cells. CSV files may also include aggregations. An aggregation represents the arithmetic relationship between a numeric cell and a set of other numeric cells. Our proposed AggreCol algorithm is capable of detecting aggregations of five arithmetic functions in CSV files. Note that stylistic features, such as font style and cell background color, do not exist in CSV files. Our proposed algorithms address the respective problems by using only content, contextual, and computational features. Storing a relational table is also a common usage of CSV files. Primary keys and foreign keys are important metadata for relational databases, which are usually not present for database instances dumped as plain-text files. We propose the HoPF algorithm to holistically detect both constraints in relational databases. Our approach is capable of distinguishing true primary and foreign keys from a great amount of spurious unique column combinations and inclusion dependencies, which can be detected by state-of-the-art data profiling algorithms. N2 - Schätzungen zufolge verbringen Datenwissenschaftler bis zu 80% ihrer Zeit mit der Erkundung, Bereinigung und Umwandlung ihrer Daten. Ein Hauptgrund für diesen Aufwand ist das fehlende Wissen über die verwendeten Daten, die oft aus unterschiedlichen Quellen stammen und heterogene Strukturen aufweisen. Als Mittel zur Beschreibung verschiedener Dateneigenschaften können Metadaten Datenwissenschaftlern dabei helfen, ihre Daten zu verstehen und aufzubereiten, und so wertvolle Zeit die Datenanalysen selbst sparen. Metadaten sind jedoch nicht immer vorhanden: Zum Beispiel sind einige Dateiformate nicht in der Lage, sie zu speichern; Metadaten können aus Datenschutzgründen gelöscht worden sein; oder ältere Daten wurden möglicherweise von Systemen erzeugt, die nicht für die Speicherung und Verarbeitung von Metadaten konzipiert waren. Da Daten in einem noch nie dagewesenen Tempo produziert und in verschiedenen Formaten gespeichert werden, ist die manuelle Erstellung von Metadaten nicht nur unpraktisch, sondern auch fehleranfällig, so dass automatische Ansätze zur Metadatenerkennung erforderlich sind. In dieser Arbeit konzentrieren wir uns auf die Erkennung von Metadaten in CSV-Dateien - einer Art von Klartextdateien, die, ähnlich wie Tabellenkalkulationen, verschiedene Arten von Inhalten an beliebigen Positionen enthalten können. Wir schlagen eine Taxonomie der Metadaten in CSV-Dateien vor und befassen uns speziell mit der Erkennung von drei verschiedenen Metadaten: Zeile und Zellensemantischer Typ, Aggregationen sowie Primärschlüssel und Fremdschlüssel. Die Daten sind in CSV-Dateien ad-hoc organisiert und folgen keiner festen Struktur, wie sie von gängigen Datenverarbeitungsprogrammen angenommen wird. Die Erkennung der Struktur solcher Dateien ist eine Voraussetzung für die Extraktion von Informationen aus ihnen, die durch die Erkennung des semantischen Typs jeder Zeile oder jeder Zelle, wie z. B. Kopfzeile, Daten, abgeleitete Daten oder Fußnote, angegangen werden kann. Wir schlagen den Ansatz des überwachten Lernens, genannt „Strudel“ vor, um den strukturellen Typ von Zeilen und Zellen zu klassifizieren. CSV-Dateien können auch Aggregationen enthalten. Eine Aggregation stellt die arithmetische Beziehung zwischen einer numerischen Zelle und einer Reihe anderer numerischer Zellen dar. Der von uns vorgeschlagene „Aggrecol“-Algorithmus ist in der Lage, Aggregationen von fünf arithmetischen Funktionen in CSV-Dateien zu erkennen. Da stilistische Merkmale wie Schriftart und Zellhintergrundfarbe in CSV-Dateien nicht vorhanden sind, die von uns vorgeschlagenen Algorithmen die entsprechenden Probleme, indem sie nur die Merkmale Inhalt, Kontext und Berechnungen verwenden. Die Speicherung einer relationalen Tabelle ist ebenfalls eine häufige Verwendung von CSV-Dateien. Primär- und Fremdschlüssel sind wichtige Metadaten für relationale Datenbanken, die bei Datenbankinstanzen, die als reine Textdateien gespeichert werden, normalerweise nicht vorhanden sind. Wir schlagen den „HoPF“-Algorithmus vor, um beide Constraints in relationalen Datenbanken ganzheitlich zu erkennen. Unser Ansatz ist in der Lage, echte Primär- und Fremdschlüssel von einer großen Menge an falschen eindeutigen Spaltenkombinationen und Einschlussabhängigkeiten zu unterscheiden, die von modernen Data-Profiling-Algorithmen erkannt werden können. KW - data preparation KW - metadata detection KW - data wrangling KW - Datenaufbereitung KW - Datentransformation KW - Erkennung von Metadaten Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-566204 ER - TY - THES A1 - Katzmann, Maximilian T1 - About the analysis of algorithms on networks with underlying hyperbolic geometry T1 - Über die Analyse von Algorithmen auf Netzwerken mit zugrundeliegender hyperbolischer Geometrie N2 - Many complex systems that we encounter in the world can be formalized using networks. Consequently, they have been in the focus of computer science for decades, where algorithms are developed to understand and utilize these systems. Surprisingly, our theoretical understanding of these algorithms and their behavior in practice often diverge significantly. In fact, they tend to perform much better on real-world networks than one would expect when considering the theoretical worst-case bounds. One way of capturing this discrepancy is the average-case analysis, where the idea is to acknowledge the differences between practical and worst-case instances by focusing on networks whose properties match those of real graphs. Recent observations indicate that good representations of real-world networks are obtained by assuming that a network has an underlying hyperbolic geometry. In this thesis, we demonstrate that the connection between networks and hyperbolic space can be utilized as a powerful tool for average-case analysis. To this end, we first introduce strongly hyperbolic unit disk graphs and identify the famous hyperbolic random graph model as a special case of them. We then consider four problems where recent empirical results highlight a gap between theory and practice and use hyperbolic graph models to explain these phenomena theoretically. First, we develop a routing scheme, used to forward information in a network, and analyze its efficiency on strongly hyperbolic unit disk graphs. For the special case of hyperbolic random graphs, our algorithm beats existing performance lower bounds. Afterwards, we use the hyperbolic random graph model to theoretically explain empirical observations about the performance of the bidirectional breadth-first search. Finally, we develop algorithms for computing optimal and nearly optimal vertex covers (problems known to be NP-hard) and show that, on hyperbolic random graphs, they run in polynomial and quasi-linear time, respectively. Our theoretical analyses reveal interesting properties of hyperbolic random graphs and our empirical studies present evidence that these properties, as well as our algorithmic improvements translate back into practice. N2 - Viele komplexe Systeme mit denen wir tagtäglich zu tun haben, können mit Hilfe von Netzwerken beschrieben werden, welche daher schon jahrzehntelang im Fokus der Informatik stehen. Dort werden Algorithmen entwickelt, um diese Systeme besser verstehen und nutzen zu können. Überraschenderweise unterscheidet sich unsere theoretische Vorstellung dieser Algorithmen jedoch oft immens von derem praktischen Verhalten. Tatsächlich neigen sie dazu auf echten Netzwerken viel effizienter zu sein, als man im schlimmsten Fall erwarten würde. Eine Möglichkeit diese Diskrepanz zu erfassen ist die Average-Case Analyse bei der man die Unterschiede zwischen echten Instanzen und dem schlimmsten Fall ausnutzt, indem ausschließlich Netzwerke betrachtet werden, deren Eigenschaften die von echten Graphen gut abbilden. Jüngste Beobachtungen zeigen, dass gute Abbildungen entstehen, wenn man annimmt, dass einem Netzwerk eine hyperbolische Geometrie zugrunde liegt. In dieser Arbeit wird demonstriert, dass hyperbolische Netzwerke als mächtiges Werkzeug der Average-Case Analyse dienen können. Dazu werden stark-hyperbolische Unit-Disk-Graphen eingeführt und die bekannten hyperbolischen Zufallsgraphen als ein Sonderfall dieser identifiziert. Anschließend werden auf diesen Modellen vier Probleme analysiert, um Resultate vorangegangener Experimente theoretisch zu erklären, die eine Diskrepanz zwischen Theorie und Praxis aufzeigten. Zuerst wird ein Routing Schema zum Transport von Nachrichten entwickelt und dessen Effizienz auf stark-hyperbolischen Unit-Disk-Graphen untersucht. Allgemeingültige Effizienzschranken können so auf hyperbolischen Zufallsgraphen unterboten werden. Anschließend wird das hyperbolische Zufallsgraphenmodell verwendet, um praktische Beobachtungen der bidirektionalen Breitensuche theoretisch zu erklären und es werden Algorithmen entwickelt, um optimale und nahezu optimale Knotenüberdeckungen zu berechnen (NP-schwer), deren Laufzeit auf diesen Graphen jeweils polynomiell und quasi-linear ist. In den Analysen werden neue Eigenschaften von hyperbolischen Zufallsgraphen aufgedeckt und empirisch gezeigt, dass sich diese sowie die algorithmischen Verbesserungen auch auf echten Netzwerken nachweisen lassen. KW - graph theory KW - hyperbolic geometry KW - average-case analysis KW - Average-Case Analyse KW - Graphentheorie KW - hyperbolische Geometrie Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-582965 ER - TY - THES A1 - Klimke, Jan T1 - Web-based provisioning and application of large-scale virtual 3D city models T1 - Webbasierte Bereitstellung und Anwendung von großen virtuellen 3D-Stadtmodellen N2 - Virtual 3D city models represent and integrate a variety of spatial data and georeferenced data related to urban areas. With the help of improved remote-sensing technology, official 3D cadastral data, open data or geodata crowdsourcing, the quantity and availability of such data are constantly expanding and its quality is ever improving for many major cities and metropolitan regions. There are numerous fields of applications for such data, including city planning and development, environmental analysis and simulation, disaster and risk management, navigation systems, and interactive city maps. The dissemination and the interactive use of virtual 3D city models represent key technical functionality required by nearly all corresponding systems, services, and applications. The size and complexity of virtual 3D city models, their management, their handling, and especially their visualization represent challenging tasks. For example, mobile applications can hardly handle these models due to their massive data volume and data heterogeneity. Therefore, the efficient usage of all computational resources (e.g., storage, processing power, main memory, and graphics hardware, etc.) is a key requirement for software engineering in this field. Common approaches are based on complex clients that require the 3D model data (e.g., 3D meshes and 2D textures) to be transferred to them and that then render those received 3D models. However, these applications have to implement most stages of the visualization pipeline on client side. Thus, as high-quality 3D rendering processes strongly depend on locally available computer graphics resources, software engineering faces the challenge of building robust cross-platform client implementations. Web-based provisioning aims at providing a service-oriented software architecture that consists of tailored functional components for building web-based and mobile applications that manage and visualize virtual 3D city models. This thesis presents corresponding concepts and techniques for web-based provisioning of virtual 3D city models. In particular, it introduces services that allow us to efficiently build applications for virtual 3D city models based on a fine-grained service concept. The thesis covers five main areas: 1. A Service-Based Concept for Image-Based Provisioning of Virtual 3D City Models It creates a frame for a broad range of services related to the rendering and image-based dissemination of virtual 3D city models. 2. 3D Rendering Service for Virtual 3D City Models This service provides efficient, high-quality 3D rendering functionality for virtual 3D city models. In particular, it copes with requirements such as standardized data formats, massive model texturing, detailed 3D geometry, access to associated feature data, and non-assumed frame-to-frame coherence for parallel service requests. In addition, it supports thematic and artistic styling based on an expandable graphics effects library. 3. Layered Map Service for Virtual 3D City Models It generates a map-like representation of virtual 3D city models using an oblique view. It provides high visual quality, fast initial loading times, simple map-based interaction and feature data access. Based on a configurable client framework, mobile and web-based applications for virtual 3D city models can be created easily. 4. Video Service for Virtual 3D City Models It creates and synthesizes videos from virtual 3D city models. Without requiring client-side 3D rendering capabilities, users can create camera paths by a map-based user interface, configure scene contents, styling, image overlays, text overlays, and their transitions. The service significantly reduces the manual effort typically required to produce such videos. The videos can automatically be updated when the underlying data changes. 5. Service-Based Camera Interaction It supports task-based 3D camera interactions, which can be integrated seamlessly into service-based visualization applications. It is demonstrated how to build such web-based interactive applications for virtual 3D city models using this camera service. These contributions provide a framework for design, implementation, and deployment of future web-based applications, systems, and services for virtual 3D city models. The approach shows how to decompose the complex, monolithic functionality of current 3D geovisualization systems into independently designed, implemented, and operated service- oriented units. In that sense, this thesis also contributes to microservice architectures for 3D geovisualization systems—a key challenge of today’s IT systems engineering to build scalable IT solutions. N2 - Virtuelle 3D-Stadtmodelle repräsentieren und integrieren eine große Bandbreite von Geodaten und georeferenzierten Daten über städtische Gebiete. Verfügbarkeit, Quantität und Qualität solcher Daten verbessern sich ständig für viele Städte und Metropolregionen, nicht zuletzt bedingt durch verbesserte Erfassungstechnologien, amtliche 3D-Kataster, offene Geodaten oder Geodaten-Crowdsourcing. Die Anwendungsfelder für virtuelle 3D-Stadtmodelle sind vielfältig. Sie reichen von Stadtplanung und Stadtentwicklung, Umweltanalysen und -simulationen, über Katastrophen- und Risikomanagement, bis hin zu Navigationssystemen und interaktiven Stadtkarten. Die Verbreitung und interaktive Nutzung von virtuellen 3D-Stadtmodellen stellt hierbei eine technische Kernfunktionalität für fast alle entsprechenden Systeme, Services und Anwendungen dar. Aufgrund der Komplexität und Größe virtueller 3D-Stadtmodelle stellt ihre Verwaltung, ihre Verarbeitung und insbesondere ihre Visualisierung eine große Herausforderung dar. Daher können zum Beispiel mobile Anwendungen virtuelle 3D-Stadtmodelle, wegen ihres massiven Datenvolumens und ihrer Datenheterogenität, kaum effizient handhaben. Die effiziente Nutzung von Rechenressourcen, wie zum Beispiel Prozessorleistung, Hauptspeicher, Festplattenspeicher und Grafikhardware, bildet daher eine Schlüsselanforderung an die Softwaretechnik in diesem Bereich. Heutige Ansätze beruhen häufig auf komplexen Clients, zu denen 3D-Modelldaten (z.B. 3D-Netze und 2D- Texturen) transferiert werden müssen und die das Rendering dieser Daten selbst ausführen. Nachteilig ist dabei unter anderem, dass sie die meisten Stufen der Visualisierungspipeline auf der Client-Seite ausführen müssen. Es ist daher softwaretechnisch schwer, robuste Cross-Plattform-Implementierungen für diese Clients zu erstellen, da hoch qualitative 3D-Rendering-Prozesse nicht unwesentlich von lokalen computergrafischen Ressourcen abhängen. Die webbasierte Bereitstellung virtueller 3D-Stadtmodelle beruht auf einer serviceorientierten Softwarearchitektur. Diese besteht aus spezifischen funktionalen Komponenten für die Konstruktion von mobilen oder webbasierten Anwendungen für die Verarbeitung und Visualisierung von komplexen virtuellen 3D-Stadtmodellen. Diese Arbeit beschreibt entsprechende Konzepte und Techniken für eine webbasierte Bereitstellung von virtuellen 3D-Stadtmodellen. Es werden insbesondere Services vorgestellt, die eine effiziente Entwicklung von Anwendungen für virtuelle 3D-Stadtmodelle auf Basis eines feingranularen Dienstekonzepts ermöglichen. Die Arbeit gliedert sich in fünf thematische Hauptbeiträge: 1. Ein servicebasiertes Konzept für die bildbasierte Bereitstellung von virtuellen 3D-Stadtmodellen: Es wird ein konzeptioneller Rahmen für eine Reihe von Services in Bezug auf das Rendering und die bildbasierte Bereitstellung virtueller 3D-Stadtmodelle eingeführt. 2. 3D-Rendering-Service für virtuelle 3D-Stadtmodelle: Dieser Service stellt eine effiziente, hochqualitative 3D-Renderingfunktionalität für virtuelle 3D-Stadtmodelle bereit. Insbesondere werden Anforderungen, wie zum Beispiel standardisierte Datenformate, massive Modelltexturierung, detaillierte 3D-Geometrien, Zugriff auf assoziierte Fachdaten und fehlende Frame-zu-Frame-Kohärenz bei parallelen Serviceanfragen erfüllt. Der Service unterstützt zudem die thematische und gestalterische Stilisierung der Darstellungen auf Basis einer erweiterbaren Grafikeffektbibliothek. 3. Layered-Map-Service für virtuelle 3D-Stadtmodelle: Dieser Service generiert eine kartenverwandte Darstellung in Form einer Schrägansicht auf virtuelle 3D-Stadtmodelle in hoher Renderingqualität. Er weist eine schnelle initiale Ladezeit, eine einfache, kartenbasierte Interaktion und Zugang zu den Fachdaten des virtuellen 3D-Stadtmodells auf. Mittels eines konfigurierbaren Client-Frameworks können damit sowohl mobile, als auch webbasierte Anwendungen für virtuelle 3D Stadtmodelle einfach erstellt werden. 4. Video-Service für virtuelle 3D-Stadtmodelle: Dieser Service erstellt und synthetisiert Videos aus virtuellen 3D-Stadtmodellen. Nutzern wird ermöglicht 3D-Kamerapfade auf einfache Weise über eine kartenbasierte Nutzungsschnittstelle zu erstellen. Weiterhin können die Szeneninhalte, die Stilisierung der Szene, sowie Bild- und Textüberlagerungen konfigurieren und Übergänge zwischen einzelnen Szenen festzulegen, ohne dabei clientseitige 3D-Rendering-Fähigkeiten vorauszusetzen. Das System reduziert den manuellen Aufwand für die Produktion von Videos für virtuelle 3D-Stadtmodelle erheblich. Videos können zudem automatisiert aktualisiert werden, wenn sich zugrunde liegende Daten ändern. 5. Servicebasierte Kamerainteraktion Die vorgestellten Services unterstützen aufgabenbasierte 3D-Kamerainteraktionen und deren Integration in servicebasierte Visualisierungsanwendungen. Es wird gezeigt, wie webbasierte interaktive Anwendungen für virtuelle 3D-Stadtmodelle mit Hilfe von Kameraservices umgesetzt werden können. Diese Beiträge bieten einen Rahmen für das Design, die Implementierung und die Bereitstellung zukünftiger webbasierter Anwendungen, Systeme und Services für virtuelle 3D-Stadtmodelle. Der Ansatz zeigt, wie die meist komplexe, monolithische Funktionalität heutiger 3D-Geovisualisierungssysteme in unabhängig entworfene, implementierte und betriebene serviceorientierte Einheiten zerlegt werden kann. In diesem Sinne stellt diese Arbeit auch einen Beitrag für die Entwicklung von Microservice-Architekturen für 3D-Geovisualisierungssysteme bereit – eine aktuelle Herausforderung in der Softwaresystemtechnik in Hinblick auf den Aufbau skalierender IT-Lösungen. KW - 3D city model KW - 3D geovisualization KW - 3D portrayal KW - serverside 3D rendering KW - CityGML KW - 3D-Stadtmodell KW - 3D-Geovisualisierung KW - 3D-Rendering KW - serverseitiges 3D-Rendering KW - serviceorientierte Architekturen KW - service-oriented architectures Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-428053 ER - TY - THES A1 - Koumarelas, Ioannis T1 - Data preparation and domain-agnostic duplicate detection N2 - Successfully completing any data science project demands careful consideration across its whole process. Although the focus is often put on later phases of the process, in practice, experts spend more time in earlier phases, preparing data, to make them consistent with the systems' requirements or to improve their models' accuracies. Duplicate detection is typically applied during the data cleaning phase, which is dedicated to removing data inconsistencies and improving the overall quality and usability of data. While data cleaning involves a plethora of approaches to perform specific operations, such as schema alignment and data normalization, the task of detecting and removing duplicate records is particularly challenging. Duplicates arise when multiple records representing the same entities exist in a database. Due to numerous reasons, spanning from simple typographical errors to different schemas and formats of integrated databases. Keeping a database free of duplicates is crucial for most use-cases, as their existence causes false negatives and false positives when matching queries against it. These two data quality issues have negative implications for tasks, such as hotel booking, where users may erroneously select a wrong hotel, or parcel delivery, where a parcel can get delivered to the wrong address. Identifying the variety of possible data issues to eliminate duplicates demands sophisticated approaches. While research in duplicate detection is well-established and covers different aspects of both efficiency and effectiveness, our work in this thesis focuses on the latter. We propose novel approaches to improve data quality before duplicate detection takes place and apply the latter in datasets even when prior labeling is not available. Our experiments show that improving data quality upfront can increase duplicate classification results by up to 19%. To this end, we propose two novel pipelines that select and apply generic as well as address-specific data preparation steps with the purpose of maximizing the success of duplicate detection. Generic data preparation, such as the removal of special characters, can be applied to any relation with alphanumeric attributes. When applied, data preparation steps are selected only for attributes where there are positive effects on pair similarities, which indirectly affect classification, or on classification directly. Our work on addresses is twofold; first, we consider more domain-specific approaches to improve the quality of values, and, second, we experiment with known and modified versions of similarity measures to select the most appropriate per address attribute, e.g., city or country. To facilitate duplicate detection in applications where gold standard annotations are not available and obtaining them is not possible or too expensive, we propose MDedup. MDedup is a novel, rule-based, and fully automatic duplicate detection approach that is based on matching dependencies. These dependencies can be used to detect duplicates and can be discovered using state-of-the-art algorithms efficiently and without any prior labeling. MDedup uses two pipelines to first train on datasets with known labels, learning to identify useful matching dependencies, and then be applied on unseen datasets, regardless of any existing gold standard. Finally, our work is accompanied by open source code to enable repeatability of our research results and application of our approaches to other datasets. N2 - Die erfolgreiche Durchführung eines datenwissenschaftlichen Projekts erfordert eine Reihe sorgfältiger Abwägungen, die während des gesamten Prozessesverlaufs zu treffen sind. Obwohl sich der Schwerpunkt oft auf spätere Prozessphasen konzentriert, verbringen Experten in der Praxis jedoch einen Großteil ihrer Zeit in frühen Projektphasen in denen sie Daten aufbereiten, um sie mit den Anforderungen vorhandener Systeme in Einklang zu bringen oder die Genauigkeit ihrer Modelle zu verbessern. Die Duplikaterkennung wird üblicherweise während der Datenbereinigungsphase durchgeführt, sie dient der Beseitigung von Dateninkonsistenzen und somit der Verbesserung von Gesamtqualität und Benutzerfreundlichkeit der Daten. Während die Datenbereinigung eine Vielzahl von Ansätzen zur Durchführung spezifischer Operationen wie etwa dem Schema-Abgleich und der Datennormalisierung umfasst, stellt die Identifizierung und Entfernung doppelter Datensätze eine besondere Herausforderung dar. Dabei entstehen Duplikate, wenn mehrere Datensätze, welche die gleichen Entitäten repräsentieren, in einer Datenbank vorhanden sind. Die Gründe dafür sind vielfältig und reichen von einfachen Schreibfehlern bis hin zu unterschiedlichen Schemata und Formaten integrierter Datenbanken. Eine Datenbank duplikatfrei zu halten, ist für die meisten Anwendungsfälle von entscheidender Bedeutung, da ihre Existenz zu falschen Negativ- und Falsch-Positiv-Abfragen führt. So können sich derartige Datenqualitätsprobleme negativ auf Aufgaben wie beispielsweise Hotelbuchungen oder Paketzustellungen auswirken, was letztlich dazu führen kann, dass Benutzer ein falsches Hotel buchen, oder Pakete an eine falsche Adresse geliefert werden. Um ein breites Spektrum potenzieller Datenprobleme zu identifizieren, deren Lösung die Beseitigung von Duplikaten erleichtert, sind eine Reihe ausgefeilter Ansätze erforderlich. Obgleich der Forschungsbereich der Duplikaterkennung mit der Untersuchung verschiedenster Effizienz und Effektivitätsaspekte bereits gut etabliert ist, konzentriert sich diese Arbeit auf letztgenannte Aspekte. Wir schlagen neue Ansätze zur Verbesserung der Datenqualität vor, die vor der Duplikaterkennung erfolgen, und wenden letztere auf Datensätze an, selbst wenn diese über keine im Vorfeld erstellten Annotationen verfügen. Unsere Experimente zeigen, dass durch eine im Vorfeld verbesserte Datenqualität die Ergebnisse der sich anschließenden Duplikatklassifizierung um bis zu 19% verbessert werden können. Zu diesem Zweck schlagen wir zwei neuartige Pipelines vor, die sowohl generische als auch adressspezifische Datenaufbereitungsschritte auswählen und anwenden, um den Erfolg der Duplikaterkennung zu maximieren. Die generische Datenaufbereitung, wie z.B. die Entfernung von Sonderzeichen, kann auf jede Relation mit alphanumerischen Attributen angewendet werden. Bei entsprechender Anwendung werden Datenaufbereitungsschritte nur für Attribute ausgewählt, bei denen sich positive Auswirkungen auf Paarähnlichkeiten ergeben, welche sich direkt oder indirekt auf die Klassifizierung auswirken. Unsere Arbeit an Adressen umfasst zwei Aspekte: erstens betrachten wir mehr domänenspezifische Ansätze zur Verbesserung der Adressqualität, zweitens experimentieren wir mit bekannten und modifizierten Versionen verschiedener Ähnlichkeitsmaße, um infolgedessen das am besten geeignete Ähnlichkeitsmaß für jedes Adressattribut, z.B. Stadt oder Land, zu bestimmen. Um die Erkennung von Duplikaten bei Anwendungen zu erleichtern, in denen Goldstandard-Annotationen nicht zur Verfügung stehen und deren Beschaffung aus Kostengründen nicht möglich ist, schlagen wir MDedup vor. MDedup ist ein neuartiger, regelbasierter und vollautomatischer Ansatz zur Dublikaterkennung, der auf Matching Dependencies beruht. Diese Abhängigkeiten können zur Erkennung von Duplikaten genutzt und mit Hilfe modernster Algorithmen effizient ohne vorhergehenden Annotationsaufwand entdeckt werden. MDedup verwendet zwei Pipelines, um zunächst auf annotierten Datensätzen zu trainieren, wobei die Identifizierung nützlicher Matching-Abhängigkeiten erlernt wird, welche dann unabhängig von einem bestehenden Goldstandard auf ungesehenen Datensätzen angewendet werden können. Schließlich stellen wir den im Rahmen dieser Arbeit entstehenden Quellcode zur Verfügung, wodurch sowohl die Wiederholbarkeit unserer Forschungsergebnisse als auch die Anwendung unserer Ansätze auf anderen Datensätzen gewährleistet werden soll. T2 - Datenaufbereitung und domänenagnostische Duplikaterkennung KW - duplicate detection KW - data cleaning KW - entity resolution KW - record linkage KW - data preparation KW - data matching KW - address normalization KW - machine learning KW - matching dependencies KW - Adressnormalisierung KW - Datenbereinigung KW - Datenabgleich KW - Datenaufbereitung KW - Duplikaterkennung KW - Entitätsauflösung KW - Maschinelles Lernen KW - Abgleich von Abhängigkeiten KW - Datensatzverknüpfung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-489131 ER - TY - THES A1 - Kovács, Róbert T1 - Human-scale personal fabrication N2 - The availability of commercial 3D printers and matching 3D design software has allowed a wide range of users to create physical prototypes – as long as these objects are not larger than hand size. However, when attempting to create larger, "human-scale" objects, such as furniture, not only are these machines too small, but also the commonly used 3D design software is not equipped to design with forces in mind — since forces increase disproportionately with scale. In this thesis, we present a series of end-to-end fabrication software systems that support users in creating human-scale objects. They achieve this by providing three main functions that regular "small-scale" 3D printing software does not offer: (1) subdivision of the object into small printable components combined with ready-made objects, (2) editing based on predefined elements sturdy enough for larger scale, i.e., trusses, and (3) functionality for analyzing, detecting, and fixing structural weaknesses. The presented software systems also assist the fabrication process based on either 3D printing or steel welding technology. The presented systems focus on three levels of engineering challenges: (1) fabricating static load-bearing objects, (2) creating mechanisms that involve motion, such as kinematic installations, and finally (3) designing mechanisms with dynamic repetitive movement where power and energy play an important role. We demonstrate and verify the versatility of our systems by building and testing human-scale prototypes, ranging from furniture pieces, pavilions, to animatronic installations and playground equipment. We have also shared our system with schools, fablabs, and fabrication enthusiasts, who have successfully created human-scale objects that can withstand with human-scale forces. N2 - Die Verfügbarkeit kommerzieller 3D-Drucker und die dazugehörige Software ermöglicht einer großen Bandbreite von Nutzern, physikalische Prototypen selbst herzustellen. Allerdings gilt dies oft nur für handgroße Objekte. Diese Limitation ist auf der einen Seite den kleinen Maschinengrößen von 3D-Druckern geschuldet, andererseits müssen aber auch signifikante, einwirkende Kräfte bereits im Entwurf berücksichtigt werden, was in aktuellen Anwendungen lediglich Benutzern mit entsprechendem Know-How vorbehalten ist. In dieser Arbeit stelle ich eine Reihe von Software-Komplettlösungen vor, die es einer breiten Benutzergruppe erlaubt, große "human-scale" Strukturen, wie Möbel, zu entwerfen und herzustellen. Diese Systeme gehen in drei Kernaspekten über herkömmliche 3D-Druck-Entwurfsanwendungen hinaus: (1) Die Unterteilung von großen Strukturen in eine Kombination aus druckbaren Objekten und Standardteilen. (2) Entwurf von statisch tragenden Strukturen. (3) Funktionalität zum Erkennen, Analysieren und Beheben von strukturellen Schwachstellen. Dabei beschränkt sich diese Arbeit nicht auf Softwarelösungen, sondern unterstützt die Benutzer im gesamten Herstellungsprozess, sowohl bei Prozessen basierend auf dem FDM 3D-Druck, als auch beim Schweißen von Metallen. Die verschiedenen Systeme, die hier vorgestellt werden, ermöglichen die Erstellungen von tragfähigen, statischen Strukturen über kinematische Installation bis hin zu dynamischen Konstruktionen. Solche gefertigten Konstrukte wie Möbel, Pavillons, Spielplatzgeräte, als auch animierte Installationen demonstrieren die Funktionalität und das weite Anwendungsspektrum des Ansatzes. Ergebnisse dieser Arbeit kamen bereits an Schulen, FabLabs und bei Privatpersonen zum Einsatz, die mit der Software erfolgreich eigene und funktionale "human-scale"-Großstrukturen entwerfen und herstellen konnten. KW - 3D printing KW - fabrication KW - human-scale KW - load-bearing KW - dynamics KW - force KW - 3D Druck KW - Fabrikation KW - Großformat KW - Kraft KW - Tragfähigkeit KW - Dynamik Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-555398 ER - TY - THES A1 - Koßmann, Jan T1 - Unsupervised database optimization BT - efficient index selection & data dependency-driven query optimization N2 - The amount of data stored in databases and the complexity of database workloads are ever- increasing. Database management systems (DBMSs) offer many configuration options, such as index creation or unique constraints, which must be adapted to the specific instance to efficiently process large volumes of data. Currently, such database optimization is complicated, manual work performed by highly skilled database administrators (DBAs). In cloud scenarios, manual database optimization even becomes infeasible: it exceeds the abilities of the best DBAs due to the enormous number of deployed DBMS instances (some providers maintain millions of instances), missing domain knowledge resulting from data privacy requirements, and the complexity of the configuration tasks. Therefore, we investigate how to automate the configuration of DBMSs efficiently with the help of unsupervised database optimization. While there are numerous configuration options, in this thesis, we focus on automatic index selection and the use of data dependencies, such as functional dependencies, for query optimization. Both aspects have an extensive performance impact and complement each other by approaching unsupervised database optimization from different perspectives. Our contributions are as follows: (1) we survey automated state-of-the-art index selection algorithms regarding various criteria, e.g., their support for index interaction. We contribute an extensible platform for evaluating the performance of such algorithms with industry-standard datasets and workloads. The platform is well-received by the community and has led to follow-up research. With our platform, we derive the strengths and weaknesses of the investigated algorithms. We conclude that existing solutions often have scalability issues and cannot quickly determine (near-)optimal solutions for large problem instances. (2) To overcome these limitations, we present two new algorithms. Extend determines (near-)optimal solutions with an iterative heuristic. It identifies the best index configurations for the evaluated benchmarks. Its selection runtimes are up to 10 times lower compared with other near-optimal approaches. SWIRL is based on reinforcement learning and delivers solutions instantly. These solutions perform within 3 % of the optimal ones. Extend and SWIRL are available as open-source implementations. (3) Our index selection efforts are complemented by a mechanism that analyzes workloads to determine data dependencies for query optimization in an unsupervised fashion. We describe and classify 58 query optimization techniques based on functional, order, and inclusion dependencies as well as on unique column combinations. The unsupervised mechanism and three optimization techniques are implemented in our open-source research DBMS Hyrise. Our approach reduces the Join Order Benchmark’s runtime by 26 % and accelerates some TPC-DS queries by up to 58 times. Additionally, we have developed a cockpit for unsupervised database optimization that allows interactive experiments to build confidence in such automated techniques. In summary, our contributions improve the performance of DBMSs, support DBAs in their work, and enable them to contribute their time to other, less arduous tasks. N2 - Sowohl die Menge der in Datenbanken gespeicherten Daten als auch die Komplexität der Datenbank-Workloads steigen stetig an. Datenbankmanagementsysteme bieten viele Konfigurationsmöglichkeiten, zum Beispiel das Anlegen von Indizes oder die Definition von Unique Constraints. Diese Konfigurations-möglichkeiten müssen für die spezifische Datenbankinstanz angepasst werden, um effizient große Datenmengen verarbeiten zu können. Heutzutage wird die komplizierte Datenbankoptimierung manuell von hochqualifizierten Datenbankadministratoren vollzogen. In Cloud-Szenarien ist die manuelle Daten-bankoptimierung undenkbar: Die enorme Anzahl der verwalteten Systeme (einige Anbieter verwalten Millionen von Instanzen), das fehlende Domänenwissen durch Datenschutzanforderungen und die Kom-plexität der Konfigurationsaufgaben übersteigen die Fähigkeiten der besten Datenbankadministratoren. Aus diesen Gründen betrachten wir, wie die Konfiguration von Datenbanksystemen mit der Hilfe von Unsupervised Database Optimization effizient automatisiert werden kann. Während viele Konfigura-tionsmöglichkeiten existieren, konzentrieren wir uns auf die automatische Indexauswahl und die Nutzung von Datenabhängigkeiten, zum Beispiel Functional Dependencies, für die Anfrageoptimierung. Beide Aspekte haben großen Einfluss auf die Performanz und ergänzen sich gegenseitig, indem sie Unsupervised Database Optimization aus verschiedenen Perspektiven betrachten. Wir leisten folgende Beiträge: (1) Wir untersuchen dem Stand der Technik entsprechende automatisierte Indexauswahlalgorithmen hinsichtlich verschiedener Kriterien, zum Beispiel bezüglich ihrer Berücksichtigung von Indexinteraktionen. Wir stellen eine erweiterbare Plattform zur Leistungsevaluierung solcher Algorithmen mit Industriestandarddatensätzen und -Workloads zur Verfügung. Diese Plattform wird von der Forschungsgemeinschaft aktiv verwendet und hat bereits zu weiteren Forschungsarbeiten geführt. Mit unserer Plattform leiten wir die Stärken und Schwächen der untersuchten Algorithmen ab. Wir kommen zu dem Schluss, dass bestehende Lösung häufig Skalierungsschwierigkeiten haben und nicht in der Lage sind, schnell (nahezu) optimale Lösungen für große Problemfälle zu ermitteln. (2) Um diese Einschränkungen zu bewältigen, stellen wir zwei neue Algorithmen vor. Extend ermittelt (nahezu) optimale Lösungen mit einer iterativen Heuristik. Das Verfahren identifiziert die besten Indexkonfigurationen für die evaluierten Benchmarks und seine Laufzeit ist bis zu 10-mal geringer als die Laufzeit anderer nahezu optimaler Ansätze. SWIRL basiert auf Reinforcement Learning und ermittelt Lösungen ohne Wartezeit. Diese Lösungen weichen maximal 3 % von den optimalen Lösungen ab. Extend und SWIRL sind verfügbar als Open-Source-Implementierungen. (3) Ein Mechanismus, der mittels automatischer Workload-Analyse Datenabhängigkeiten für die Anfrageoptimierung bestimmt, ergänzt die vorigen Beiträge. Wir beschreiben und klassifizieren 58 Techniken, die auf Functional, Order und Inclusion Dependencies sowie Unique Column Combinations basieren. Der Analysemechanismus und drei Optimierungstechniken sind in unserem Open-Source-Forschungsdatenbanksystem Hyrise implementiert. Der Ansatz reduziert die Laufzeit des Join Order Benchmark um 26 % und erreicht eine bis zu 58-fache Beschleunigung einiger TPC-DS-Anfragen. Darüber hinaus haben wir ein Cockpit für Unsupervised Database Optimization entwickelt. Dieses Cockpit ermöglicht interaktive Experimente, um Vertrauen in automatisierte Techniken zur Datenbankoptimie-rung zu schaffen. Zusammenfassend lässt sich festhalten, dass unsere Beiträge die Performanz von Datenbanksystemen verbessern, Datenbankadministratoren in ihrer Arbeit unterstützen und ihnen ermöglichen, ihre Zeit anderen, weniger mühsamen, Aufgaben zu widmen. KW - Datenbank KW - Datenbanksysteme KW - database KW - DBMS KW - Hyrise KW - index selection KW - database systems KW - RL KW - reinforcement learning KW - query optimization KW - data dependencies KW - functional dependencies KW - order dependencies KW - unique column combinations KW - inclusion dependencies KW - funktionale Abhängigkeiten KW - Anfrageoptimierung KW - Query-Optimierung KW - extend KW - SWIRL KW - unsupervised KW - database optimization KW - self-driving KW - autonomous Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-589490 ER - TY - THES A1 - Kraus, Sara Milena T1 - A Systems Medicine approach for heart valve diseases BT - addressing the proteomic landscape and differential expression software N2 - In Systems Medicine, in addition to high-throughput molecular data (*omics), the wealth of clinical characterization plays a major role in the overall understanding of a disease. Unique problems and challenges arise from the heterogeneity of data and require new solutions to software and analysis methods. The SMART and EurValve studies establish a Systems Medicine approach to valvular heart disease -- the primary cause of subsequent heart failure. With the aim to ascertain a holistic understanding, different *omics as well as the clinical picture of patients with aortic stenosis (AS) and mitral regurgitation (MR) are collected. Our task within the SMART consortium was to develop an IT platform for Systems Medicine as a basis for data storage, processing, and analysis as a prerequisite for collaborative research. Based on this platform, this thesis deals on the one hand with the transfer of the used Systems Biology methods to their use in the Systems Medicine context and on the other hand with the clinical and biomolecular differences of the two heart valve diseases. To advance differential expression/abundance (DE/DA) analysis software for use in Systems Medicine, we state 21 general software requirements and features of automated DE/DA software, including a novel concept for the simple formulation of experimental designs that can represent complex hypotheses, such as comparison of multiple experimental groups, and demonstrate our handling of the wealth of clinical data in two research applications DEAME and Eatomics. In user interviews, we show that novice users are empowered to formulate and test their multiple DE hypotheses based on clinical phenotype. Furthermore, we describe insights into users' general impression and expectation of the software's performance and show their intention to continue using the software for their work in the future. Both research applications cover most of the features of existing tools or even extend them, especially with respect to complex experimental designs. Eatomics is freely available to the research community as a user-friendly R Shiny application. Eatomics continued to help drive the collaborative analysis and interpretation of the proteomic profile of 75 human left myocardial tissue samples from the SMART and EurValve studies. Here, we investigate molecular changes within the two most common types of valvular heart disease: aortic valve stenosis (AS) and mitral valve regurgitation (MR). Through DE/DA analyses, we explore shared and disease-specific protein alterations, particularly signatures that could only be found in the sex-stratified analysis. In addition, we relate changes in the myocardial proteome to parameters from clinical imaging. We find comparable cardiac hypertrophy but differences in ventricular size, the extent of fibrosis, and cardiac function. We find that AS and MR show many shared remodeling effects, the most prominent of which is an increase in the extracellular matrix and a decrease in metabolism. Both effects are stronger in AS. In muscle and cytoskeletal adaptations, we see a greater increase in mechanotransduction in AS and an increase in cortical cytoskeleton in MR. The decrease in proteostasis proteins is mainly attributable to the signature of female patients with AS. We also find relevant therapeutic targets. In addition to the new findings, our work confirms several concepts from animal and heart failure studies by providing the largest collection of human tissue from in vivo collected biopsies to date. Our dataset contributing a resource for isoform-specific protein expression in two of the most common valvular heart diseases. Apart from the general proteomic landscape, we demonstrate the added value of the dataset by showing proteomic and transcriptomic evidence for increased expression of the SARS-CoV-2- receptor at pressure load but not at volume load in the left ventricle and also provide the basis of a newly developed metabolic model of the heart. N2 - In der Systemmedizin spielt zusätzlich zu den molekularen Hochdurchsatzdaten (*omics) die Fülle an klinischer Charakterisierung eine große Rolle im Gesamtverständnis einer Krankheit. Hieraus ergeben sich Probleme und Herausforderungen unter anderem in Bezug auf Softwarelösungen und Analysemethoden. Die SMART- und EurValve-Studien etablieren einen systemmedizinischen Ansatz für Herzklappenerkrankungen -- die Hauptursache für eine spätere Herzinsuffizienz. Mit dem Ziel ein ganzheitliches Verständnis zu etablieren, werden verschiedene *omics sowie das klinische Bild von Patienten mit Aortenstenosen (AS) und Mitralklappeninsuffizienz (MR) erhoben. Unsere Aufgabe innerhalb des SMART Konsortiums bestand in der Entwicklung einer IT-Plattform für Systemmedizin als Grundlage für die Speicherung, Verarbeitung und Analyse von Daten als Voraussetzung für gemeinsame Forschung. Ausgehend von dieser Plattform beschäftigt sich diese Arbeit einerseits mit dem Transfer der genutzten systembiologischen Methoden hin zu einer Nutzung im systemmedizinischen Kontext und andererseits mit den klinischen und biomolekularen Unterschieden der beiden Herzklappenerkrankungen. Um die Analysesoftware für differenzielle Expression/Abundanz, eine häufig genutzte Methode der System Biologie, für die Nutzung in der Systemmedizin voranzutreiben, erarbeiten wir 21 allgemeine Softwareanforderungen und Funktionen einer automatisierten DE/DA Software. Darunter ist ein neuartiges Konzept für die einfache Formulierung experimenteller Designs, die auch komplexe Hypothesen wie den Vergleich mehrerer experimenteller Gruppen abbilden können und demonstrieren unseren Umgang mit der Fülle klinischer Daten in zwei Forschungsanwendungen -- DEAME und Eatomics. In Nutzertests zeigen wir, dass Nutzer befähigt werden, ihre vielfältigen Hypothesen zur differenziellen Expression basierend auf dem klinischen Phänotyp zu formulieren und zu testen, auch ohne einen dedizierten Hintergrund in Bioinformatik. Darüber hinaus beschreiben wir Einblicke in den allgemeinen Eindruck der Nutzer, ihrer Erwartung an die Leistung der Software und zeigen ihre Absicht, die Software auch in der Zukunft für ihre Arbeit zu nutzen. Beide Forschungsanwendungen decken die meisten Funktionen bestehender Tools ab oder erweitern sie sogar, insbesondere im Hinblick auf komplexe experimentelle Designs. Eatomics steht der Forschungsgemeinschaft als benutzerfreundliche R Shiny-Anwendung frei zur Verfügung. \textit{Eatomics} hat weiterhin dazu beigetragen, die gemeinsame Analyse und Interpretation des Proteomprofils von 75 menschlichen linken Myokardgewebeproben aus den SMART- und EurValve-Studien voran zu treiben. Hier untersuchen wir die molekularen Veränderungen innerhalb der beiden häufigsten Arten von Herzklappenerkrankungen: AS und MR. Durch DE/DA Analysen erarbeiten wir gemeinsame und krankheitsspezifische Proteinveränderungen, insbesondere Signaturen, die nur in einer geschlechtsstratifizierten Analyse gefunden werden konnten. Darüber hinaus beziehen wir Veränderungen des Myokardproteoms auf Parameter aus der klinischen Bildgebung. Wir finden eine vergleichbare kardiale Hypertrophie, aber Unterschiede in der Ventrikelgröße, dem Ausmaß der Fibrose und der kardialen Funktion. Wir stellen fest, dass AS und MR viele gemeinsame Remodelling-Effekte zeigen, von denen die wichtigsten die Zunahme der extrazellulären Matrix und eine Abnahme des Metabolismus sind. Beide Effekte sind bei AS stärker. Zusätzlich zeigt sich eine größere Variabilität zwischen den einzelnen Patienten mit AS. Bei Muskel- und Zytoskelettanpassungen sehen wir einen stärkeren Anstieg der Mechanotransduktion bei AS und einen Anstieg des kortikalen Zytoskeletts bei MR. Die Abnahme von Proteinen der Proteostase ist vor allem der Signatur von weiblichen Patienten mit AS zuzuschreiben. Außerdem finden wir therapierelevante Proteinveränderungen. Zusätzlich zu den neuen Erkenntnissen bestätigt unsere Arbeit mehrere Konzepte aus Tierstudien und Studien zu Herzversagen durch die bislang größte Kollektion von humanem Gewebe aus in vivo Biopsien. Mit unserem Datensatz stellen wir eine Ressource für die isoformspezifische Proteinexpression bei zwei der häufigsten Herzklappenerkrankungen zur Verfügung. Abgesehen von der allgemeinen Proteomlandschaft zeigen wir den Mehrwert des Datensatzes, indem wir proteomische und transkriptomische Beweise für eine erhöhte Expression des SARS-CoV-2- Rezeptors bei Drucklast, jedoch nicht bei Volumenlast im linken Ventrikel aufzeigen und außerdem die Grundlage eines neu entwickelten metabolischen Modells des Herzens liefern. KW - Systems Medicine KW - Systemmedizin KW - Proteomics KW - Proteom KW - Heart Valve Diseases KW - Herzklappenerkrankungen KW - Differential Expression Analysis KW - Software KW - Software Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-522266 ER - TY - THES A1 - Krejca, Martin Stefan T1 - Theoretical analyses of univariate estimation-of-distribution algorithms N2 - Optimization is a core part of technological advancement and is usually heavily aided by computers. However, since many optimization problems are hard, it is unrealistic to expect an optimal solution within reasonable time. Hence, heuristics are employed, that is, computer programs that try to produce solutions of high quality quickly. One special class are estimation-of-distribution algorithms (EDAs), which are characterized by maintaining a probabilistic model over the problem domain, which they evolve over time. In an iterative fashion, an EDA uses its model in order to generate a set of solutions, which it then uses to refine the model such that the probability of producing good solutions is increased. In this thesis, we theoretically analyze the class of univariate EDAs over the Boolean domain, that is, over the space of all length-n bit strings. In this setting, the probabilistic model of a univariate EDA consists of an n-dimensional probability vector where each component denotes the probability to sample a 1 for that position in order to generate a bit string. My contribution follows two main directions: first, we analyze general inherent properties of univariate EDAs. Second, we determine the expected run times of specific EDAs on benchmark functions from theory. In the first part, we characterize when EDAs are unbiased with respect to the problem encoding. We then consider a setting where all solutions look equally good to an EDA, and we show that the probabilistic model of an EDA quickly evolves into an incorrect model if it is always updated such that it does not change in expectation. In the second part, we first show that the algorithms cGA and MMAS-fp are able to efficiently optimize a noisy version of the classical benchmark function OneMax. We perturb the function by adding Gaussian noise with a variance of σ², and we prove that the algorithms are able to generate the true optimum in a time polynomial in σ² and the problem size n. For the MMAS-fp, we generalize this result to linear functions. Further, we prove a run time of Ω(n log(n)) for the algorithm UMDA on (unnoisy) OneMax. Last, we introduce a new algorithm that is able to optimize the benchmark functions OneMax and LeadingOnes both in O(n log(n)), which is a novelty for heuristics in the domain we consider. N2 - Optimierung ist ein Hauptbestandteil technologischen Fortschritts und oftmals computergestützt. Da viele Optimierungsprobleme schwer sind, ist es jedoch unrealistisch, eine optimale Lösung in angemessener Zeit zu erwarten. Daher werden Heuristiken verwendet, also Programme, die versuchen hochwertige Lösungen schnell zu erzeugen. Eine konkrete Klasse sind Estimation-of-Distribution-Algorithmen (EDAs), die sich durch das Entwickeln probabilistischer Modelle über dem Problemraum auszeichnen. Ein solches Modell wird genutzt, um neue Lösungen zu erzeugen und damit das Modell zu verfeinern, um im nächsten Schritt mit erhöhter Wahrscheinlichkeit bessere Lösungen zu generieren. In dieser Arbeit untersuchen wir die Klasse univariater EDAs in der booleschen Domäne, also im Raum aller Bitstrings der Länge n. Das probabilistische Modell eines univariaten EDAs besteht dann aus einem n-dimensionalen Wahrscheinlichkeitsvektor, in dem jede Komponente die Wahrscheinlichkeit angibt, eine 1 an der entsprechenden Stelle zu erzeugen. Mein Beitrag folgt zwei Hauptrichtungen: Erst untersuchen wir allgemeine inhärente Eigenschaften univariater EDAs. Danach bestimmen wir die erwartete Laufzeit gewisser EDAs auf Benchmarks aus der Theorie. Im ersten Abschnitt charakterisieren wir, wann EDAs unbefangen bezüglich der Problemcodierung sind. Dann untersuchen wir sie in einem Szenario, in dem alle Lösungen gleich gut sind, und zeigen, dass sich ihr Modell schnell zu einem falschen entwickelt, falls es immer so angepasst wird, dass sich im Erwartungswert nichts ändert. Im zweiten Abschnitt zeigen wir, dass die Algorithmen cGA und MMAS-fp eine verrauschte Variante des klassischen Benchmarks OneMax effizient optimieren, bei der eine Gaussverteilung mit Varianz σ² hinzuaddiert wird. Wir beweisen, dass die Algorithmen das wahre Optimum in polynomieller Zeit bezüglich σ² und n erzeugen. Für den MMAS-fp verallgemeinern wir dieses Ergebnis auf lineare Funktionen. Weiterhin beweisen wir eine Laufzeit von Ω(n log(n)) für den Algorithmus UMDA auf OneMax (ohne Rauschen). Zuletzt führen wir einen neuen Algorithmus ein, der die Benchmarks OneMax und LeadingOnes in O(n log(n)) optimiert, was zuvor für noch keine Heuristik gezeigt wurde. T2 - Theoretische Analysen univariater Estimation-of-Distribution-Algorithmen KW - theory KW - estimation-of-distribution algorithms KW - univariate KW - pseudo-Boolean optimization KW - run time analysis KW - Theorie KW - Estimation-of-Distribution-Algorithmen KW - univariat KW - pseudoboolesche Optimierung KW - Laufzeitanalyse Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-434870 ER - TY - THES A1 - Krentz, Konrad-Felix T1 - A Denial-of-Sleep-Resilient Medium Access Control Layer for IEEE 802.15.4 Networks T1 - Eine Denial-of-Sleep-Resiliente Mediumzugriffsschicht für IEEE-802.15.4-Netzwerke N2 - With the emergence of the Internet of things (IoT), plenty of battery-powered and energy-harvesting devices are being deployed to fulfill sensing and actuation tasks in a variety of application areas, such as smart homes, precision agriculture, smart cities, and industrial automation. In this context, a critical issue is that of denial-of-sleep attacks. Such attacks temporarily or permanently deprive battery-powered, energy-harvesting, or otherwise energy-constrained devices of entering energy-saving sleep modes, thereby draining their charge. At the very least, a successful denial-of-sleep attack causes a long outage of the victim device. Moreover, to put battery-powered devices back into operation, their batteries have to be replaced. This is tedious and may even be infeasible, e.g., if a battery-powered device is deployed at an inaccessible location. While the research community came up with numerous defenses against denial-of-sleep attacks, most present-day IoT protocols include no denial-of-sleep defenses at all, presumably due to a lack of awareness and unsolved integration problems. After all, despite there are many denial-of-sleep defenses, effective defenses against certain kinds of denial-of-sleep attacks are yet to be found. The overall contribution of this dissertation is to propose a denial-of-sleep-resilient medium access control (MAC) layer for IoT devices that communicate over IEEE 802.15.4 links. Internally, our MAC layer comprises two main components. The first main component is a denial-of-sleep-resilient protocol for establishing session keys among neighboring IEEE 802.15.4 nodes. The established session keys serve the dual purpose of implementing (i) basic wireless security and (ii) complementary denial-of-sleep defenses that belong to the second main component. The second main component is a denial-of-sleep-resilient MAC protocol. Notably, this MAC protocol not only incorporates novel denial-of-sleep defenses, but also state-of-the-art mechanisms for achieving low energy consumption, high throughput, and high delivery ratios. Altogether, our MAC layer resists, or at least greatly mitigates, all denial-of-sleep attacks against it we are aware of. Furthermore, our MAC layer is self-contained and thus can act as a drop-in replacement for IEEE 802.15.4-compliant MAC layers. In fact, we implemented our MAC layer in the Contiki-NG operating system, where it seamlessly integrates into an existing protocol stack. N2 - Mit dem Aufkommen des Internets der Dinge (IoT), werden immer mehr batteriebetriebene und energieerntende Geräte in diversen Anwendungsbereichen eingesetzt, etwa in der Heimautomatisierung, Präzisionslandwirtschaft, Industrieautomatisierung oder intelligenten Stadt. In diesem Kontext stellen sogenannte Denial-of-Sleep-Angriffe eine immer kritischer werdende Bedrohung dar. Solche Angriffe halten batteriebetriebene, energieerntende oder anderweitig energiebeschränkte Geräte zeitweise oder chronisch ab, in energiesparende Schlafmodi überzugehen. Erfolgreiche Denial-of-Sleep-Angriffe führen zumindest zu einer langen Ausfallzeit der betroffenen Geräte. Um betroffene batteriebetriebene Geräte wieder in Betrieb zu nehmen, müssen zudem deren Batterien gewechselt werden. Dies ist mühsam oder eventuell sogar unmöglich, z.B. wenn solche Geräte an unzugänglichen Orten installiert sind. Obwohl die Forschungsgemeinschaft bereits viele Denial-of-Sleep-Abwehrmechanismen vorgeschlagen hat, besitzen die meisten aktuellen IoT-Protokolle überhaupt keine Denial-of-Sleep-Abwehrmechanismen. Dies kann zum einen daran liegen, dass man des Problems noch nicht gewahr ist, aber zum anderen auch daran, dass viele Integrationsfragen bislang ungeklärt sind. Des Weiteren existieren bisher sowieso noch keine effektiven Abwehrmechanismen gegen bestimmte Denial-of-Sleep-Angriffe. Der Hauptbeitrag dieser Dissertation ist die Entwicklung einer Denial-of-Sleep-resilienten Mediumzugriffsschicht für IoT-Geräte, die via IEEE-802.15.4-Funkverbindungen kommunizieren. Die entwickelte Mediumzugriffsschicht besitzt zwei Hauptkomponenten. Die erste Hauptkomponente ist ein Denial-of-Sleep-resilientes Protokoll zur Etablierung von Sitzungsschlüsseln zwischen benachbarten IEEE-802.15.4-Knoten. Diese Sitzungsschlüssel dienen einerseits der grundlegenden Absicherung des Funkverkehrs und andererseits der Implementierung zusätzlicher Denial-of-Sleep-Abwehrmechanismen in der zweiten Hauptkomponente. Die zweite Hauptkomponente ist ein Denial-of-Sleep-resilientes Mediumzugriffsprotokoll. Bemerkenswert an diesem Mediumzugriffsprotokoll ist, dass es nicht nur neuartige Denial-of-Sleep-Abwehrmechanismen enthält, sondern auch dem Stand der Technik entsprechende Mechanismen zur Verringerung des Energieverbrauchs, zur Steigerung des Durchsatzes sowie zur Erhöhung der Zuverlässigkeit. Zusammenfassend widersteht bzw. mildert unsere Denial-of-Sleep-resiliente Mediumzugriffsschicht alle uns bekannten Denial-of-Sleep-Angriffe, die gegen sie gefahren werden können. Außerdem kann unsere Denial-of-Sleep-resiliente Mediumzugriffsschicht ohne Weiteres an Stelle von IEEE-802.15.4-konformen Mediumzugriffsschichten eingesetzt werden. Dies zeigen wir durch die nahtlose Integration unserer Mediumzugriffsschicht in den Netzwerk-Stack des Betriebssystems Contiki-NG. KW - medium access control KW - denial of sleep KW - internet of things KW - Mediumzugriffskontrolle KW - Schlafentzugsangriffe KW - Internet der Dinge Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-439301 ER - TY - THES A1 - Krohmer, Anton T1 - Structures & algorithms in hyperbolic random graphs T1 - Strukturen & Algorithmen in Hyperbolischen Zufallsgraphen N2 - Complex networks are ubiquitous in nature and society. They appear in vastly different domains, for instance as social networks, biological interactions or communication networks. Yet in spite of their different origins, these networks share many structural characteristics. For instance, their degree distribution typically follows a power law. This means that the fraction of vertices of degree k is proportional to k^(−β) for some constant β; making these networks highly inhomogeneous. Furthermore, they also typically have high clustering, meaning that links between two nodes are more likely to appear if they have a neighbor in common. To mathematically study the behavior of such networks, they are often modeled as random graphs. Many of the popular models like inhomogeneous random graphs or Preferential Attachment excel at producing a power law degree distribution. Clustering, on the other hand, is in these models either not present or artificially enforced. Hyperbolic random graphs bridge this gap by assuming an underlying geometry to the graph: Each vertex is assigned coordinates in the hyperbolic plane, and two vertices are connected if they are nearby. Clustering then emerges as a natural consequence: Two nodes joined by an edge are close by and therefore have many neighbors in common. On the other hand, the exponential expansion of space in the hyperbolic plane naturally produces a power law degree sequence. Due to the hyperbolic geometry, however, rigorous mathematical treatment of this model can quickly become mathematically challenging. In this thesis, we improve upon the understanding of hyperbolic random graphs by studying its structural and algorithmical properties. Our main contribution is threefold. First, we analyze the emergence of cliques in this model. We find that whenever the power law exponent β is 2 < β < 3, there exists a clique of polynomial size in n. On the other hand, for β >= 3, the size of the largest clique is logarithmic; which severely contrasts previous models with a constant size clique in this case. We also provide efficient algorithms for finding cliques if the hyperbolic node coordinates are known. Second, we analyze the diameter, i. e., the longest shortest path in the graph. We find that it is of order O(polylog(n)) if 2 < β < 3 and O(logn) if β > 3. To complement these findings, we also show that the diameter is of order at least Ω(logn). Third, we provide an algorithm for embedding a real-world graph into the hyperbolic plane using only its graph structure. To ensure good quality of the embedding, we perform extensive computational experiments on generated hyperbolic random graphs. Further, as a proof of concept, we embed the Amazon product recommendation network and observe that products from the same category are mapped close together. N2 - Komplexe Netzwerke sind in Natur und Gesellschaft allgegenwärtig. Sie tauchen in unterschiedlichsten Domänen auf, wie zum Beispiel als soziale Netzwerke, biologische Interaktionen oder Kommunikationsnetzwerke. Trotz ihrer verschiedenen Ursprünge haben diese Netzwerke jedoch viele strukturelle Gemeinsamkeiten. So sind die Grade der Knoten typischerweise Pareto-verteilt. Das heißt, der Anteil an Knoten mit k Nachbarn ist proportional zu k-ß , wobei ß eine beliebige Konstante ist. Weiterhin haben solche Netzwerke einen hohen Clusterkoezienten, was bedeutet, dass zwei benachbarte Knoten viele gemeinsame Nachbarn haben. Um das Verhalten solcher Netzwerke mathematisch zu studieren, werden sie häug als Zufallsgraphen modelliert. Klassische Modelle wie inhomogene Zufallsgraphen oder das Preferential-Attachment-Modell erzeugen Graphen mit Pareto-verteilten Knotengraden. Cluster sind darin jedoch häug nicht vorhanden, oder werden durch das Hinzufügen unnatürlicher Strukturen künstlich erzeugt. Hyperbolische Zufallsgraphen lösen dieses Problem, indem sie dem Graphen eine Geometrie zugrunde legen. Jeder Knoten erhält hyperbolische Koordinaten, und zwei Knoten sind verbunden, wenn ihre hyperbolische Distanz klein ist. Cluster entstehen dann natürlich, da benachbarte Knoten samt ihrer Nachbarschaften in der Geometrie nah beieinander liegen, und die Pareto-Verteilung der Knotengrade folgt aus der expo- nentiellen Expansion des hyperbolischen Raumes. Durch die hyperbolische Geometrie wird jedoch auch die mathematische Analyse des Modells schnell kompliziert. In dieser Arbeit studieren wir die strukturellen und algorithmischen Eigenschaften von hyperbolischen Zufallsgraphen. Wir beginnen mit der Analyse von Cliquen. Wir beobachten, dass wenn der Pareto-Exponent ß zwischen 2 und 3 liegt, es Cliquen von polynomieller Größe in n gibt. Mit ß > 3 ist die größte Clique noch logarithmisch groß, was früheren Modellen mit konstanter Cliquengröße stark widerspricht. Wir geben auch einen ezienten Algorithmus zur Cliquenndung an, wenn die Koordinaten der Knoten bekannt sind. Als Zweites analysieren wir den Durchmesser, also den längsten kürzesten Pfad in hyperbolischen Zufallsgraphen. Wir beweisen, dass er O (log 3-ß n) lang ist, wenn 2 < ß < 3, und O (log n) falls ß > 3. Komplementär dazu zeigen wir, dass der Durchmesser mindestens Q(log n) beträgt. Als Drittes entwickeln wir einen Algorithmus, der reale Netzwerke in die hyperbolische Ebene einbettet. Um eine gute Qualität zu gewährleisten, evaluieren wir den Algorithmus auf über 6000 zufällig generierten hyperbolischen Graphen. Weiterhin betten wir exemplarisch den Produktempfehlungsgraphen von Amazon ein und beobachten, dass Produkte aus gleichen Kategorien in der Einbettung nah beieinander liegen. KW - random graphs KW - power law KW - massive networks KW - hyperbolic random graphs KW - Zufallsgraphen KW - Pareto-Verteilung KW - gigantische Netzwerke KW - hyperbolische Zufallsgraphen Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-395974 ER - TY - THES A1 - Kruse, Sebastian T1 - Scalable data profiling T1 - Skalierbares Data Profiling BT - distributed discovery and analysis of structural metadata BT - Entdecken und Analysieren struktureller Metadaten N2 - Data profiling is the act of extracting structural metadata from datasets. Structural metadata, such as data dependencies and statistics, can support data management operations, such as data integration and data cleaning. Data management often is the most time-consuming activity in any data-related project. Its support is extremely valuable in our data-driven world, so that more time can be spent on the actual utilization of the data, e. g., building analytical models. In most scenarios, however, structural metadata is not given and must be extracted first. Therefore, efficient data profiling methods are highly desirable. Data profiling is a computationally expensive problem; in fact, most dependency discovery problems entail search spaces that grow exponentially in the number of attributes. To this end, this thesis introduces novel discovery algorithms for various types of data dependencies – namely inclusion dependencies, conditional inclusion dependencies, partial functional dependencies, and partial unique column combinations – that considerably improve over state-of-the-art algorithms in terms of efficiency and that scale to datasets that cannot be processed by existing algorithms. The key to those improvements are not only algorithmic innovations, such as novel pruning rules or traversal strategies, but also algorithm designs tailored for distributed execution. While distributed data profiling has been mostly neglected by previous works, it is a logical consequence on the face of recent hardware trends and the computational hardness of dependency discovery. To demonstrate the utility of data profiling for data management, this thesis furthermore presents Metacrate, a database for structural metadata. Its salient features are its flexible data model, the capability to integrate various kinds of structural metadata, and its rich metadata analytics library. We show how to perform a data anamnesis of unknown, complex datasets based on this technology. In particular, we describe in detail how to reconstruct the schemata and assess their quality as part of the data anamnesis. The data profiling algorithms and Metacrate have been carefully implemented, integrated with the Metanome data profiling tool, and are available as free software. In that way, we intend to allow for easy repeatability of our research results and also provide them for actual usage in real-world data-related projects. N2 - Data Profiling bezeichnet das Extrahieren struktureller Metadaten aus Datensätzen. Stukturelle Metadaten, z.B. Datenabhängigkeiten und Statistiken, können bei der Datenverwaltung unterstützen. Tatsächlich beansprucht das Verwalten von Daten, z.B. Datenreinigung und -integration, in vielen datenbezogenen Projekten einen Großteil der Zeit. Die Unterstützung solcher verwaltenden Aktivitäten ist in unserer datengetriebenen Welt insbesondere deswegen sehr wertvoll, weil so mehr Zeit auf die eigentlich wertschöpfende Arbeit mit den Daten verwendet werden kann, z.B. auf das Erstellen analytischer Modelle. Allerdings sind strukturelle Metadaten in den meisten Fällen nicht oder nur unvollständig vorhanden und müssen zunächst extahiert werden. Somit sind effiziente Data-Profiling-Methoden erstrebenswert. Probleme des Data Profiling sind in der Regel sehr berechnungsintensiv: Viele Datenabhängigkeitstypen spannen einen exponentiell in der Anzahl der Attribute wachsenden Suchraum auf. Aus diesem Grund beschreibt die vorliegende Arbeit neue Algorithmen zum Auffinden verschiedener Arten von Datenabhängigkeiten – nämlich Inklusionsabhängigkeiten, bedingter Inklusionsabhängigkeiten, partieller funktionaler Abhängigkeiten sowie partieller eindeutiger Spaltenkombinationen – die bekannte Algorithmen in Effizienz und Skalierbarkeit deutlich übertreffen und somit Datensätze verarbeiten können, an denen bisherige Algorithmen gescheitert sind. Um die Nützlichkeit struktureller Metadaten für die Datenverwaltung zu demonstrieren, stellt diese Arbeit des Weiteren das System Metacrate vor, eine Datenbank für strukturelle Metadaten. Deren besondere Merkmale sind ein flexibles Datenmodell; die Fähigkeit, verschiedene Arten struktureller Metadaten zu integrieren; und eine umfangreiche Bibliothek an Metadatenanalysen. Mithilfe dieser Technologien führen wir eine Datenanamnese unbekannter, komplexer Datensätze durch. Insbesondere beschreiben wir dabei ausführlicher, wie Schemata rekonstruiert und deren Qualität abgeschätzt werden können. Wir haben oben erwähnte Data-Profiling-Algorithmen sowie Metacrate sorgfältig implementiert, mit dem Data-Profiling-Programm Metanome integriert und stellen beide als freie Software zur Verfügung. Dadurch wollen wir nicht nur die Nachvollziehbarkeit unserer Forschungsergebnisse möglichst einfach gestalten, sondern auch deren Einsatz in der Praxis ermöglichen. KW - data profiling KW - metadata KW - inclusion dependencies KW - functional dependencies KW - distributed computation KW - metacrate KW - Data Profiling KW - Metadaten KW - Inklusionsabhängigkeiten KW - funktionale Abhängigkeiten KW - verteilte Berechnung KW - Metacrate Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-412521 ER - TY - THES A1 - Ladleif, Jan T1 - Enforceability aspects of smart contracts on blockchain networks T1 - Aspekte der Durchsetzung von Smart Contracts in Blockchain-Netzwerken N2 - Smart contracts promise to reform the legal domain by automating clerical and procedural work, and minimizing the risk of fraud and manipulation. Their core idea is to draft contract documents in a way which allows machines to process them, to grasp the operational and non-operational parts of the underlying legal agreements, and to use tamper-proof code execution alongside established judicial systems to enforce their terms. The implementation of smart contracts has been largely limited by the lack of an adequate technological foundation which does not place an undue amount of trust in any contract party or external entity. Only recently did the emergence of Decentralized Applications (DApps) change this: Stored and executed via transactions on novel distributed ledger and blockchain networks, powered by complex integrity and consensus protocols, DApps grant secure computation and immutable data storage while at the same time eliminating virtually all assumptions of trust. However, research on how to effectively capture, deploy, and most of all enforce smart contracts with DApps in mind is still in its infancy. Starting from the initial expression of a smart contract's intent and logic, to the operation of concrete instances in practical environments, to the limits of automatic enforcement---many challenges remain to be solved before a widespread use and acceptance of smart contracts can be achieved. This thesis proposes a model-driven smart contract management approach to tackle some of these issues. A metamodel and semantics of smart contracts are presented, containing concepts such as legal relations, autonomous and non-autonomous actions, and their interplay. Guided by the metamodel, the notion and a system architecture of a Smart Contract Management System (SCMS) is introduced, which facilitates smart contracts in all phases of their lifecycle. Relying on DApps in heterogeneous multi-chain environments, the SCMS approach is evaluated by a proof-of-concept implementation showing both its feasibility and its limitations. Further, two specific enforceability issues are explored in detail: The performance of fully autonomous tamper-proof behavior with external off-chain dependencies and the evaluation of temporal constraints within DApps, both of which are essential for smart contracts but challenging to support in the restricted transaction-driven and closed environment of blockchain networks. Various strategies of implementing or emulating these capabilities, which are ultimately applicable to all kinds of DApp projects independent of smart contracts, are presented and evaluated. N2 - Teilweise automatisierte und autonom ausgeführte Verträge, sogenannte Smart Contracts, versprechen eine fundamentale Reform des Rechtswesens. Sie minimieren repetitive Büroarbeit sowie Betrugs- und Manipulationspotentiale. Verträge müssen dafür in einer Form verfasst werden, die es Computern erlaubt, die operativen und nichtoperativen Vertragsbestandteile zu lesen und zu verarbeiten. Durch die Nutzung fälschungssicherer Ausführungsumgebungen zusammen mit der bestehenden Rechtsordnung können sie dann durchgesetzt werden. Eine solche Ausführungsumgebung muss sicherstellen, dass ein Smart Contract von keinem Vertragspartner oder Dritten kontrolliert werden kann. Erst in letzter Zeit setzt die aufkommende Blockchain-Technologie hier neue Impulse: Dezentralisierte Anwendungen, sogenannte DApps, deren Quelltext und Zustand auf einer Blockchain gespeichert sind, stellen eine Umgebung bereit, in der Daten und Berechnungen verfälschungssicher gehalten und ausgeführt werden können. Dabei muss kein Vertrauen in eine bestimmte Person oder Instanz aufgebracht werden. Wie genau Smart Contracts effektiv mit DApps erfasst, eingesetzt, und vor allem durchgesetzt werden können ist jedoch noch offen. Von der initialen Erfassung des Vertrags als Smart Contract, über die Verwaltung in praktischen Szenarien, bis hin zu den Grenzen der Automatisierung: Viele Herausforderungen müssen gelöst werden, bevor eine breite Nutzung von Smart Contracts erreicht werden kann. In dieser Arbeit wird ein modellgetriebener Ansatz vorgeschlagen, um Smart Contracts zu verwalten und auszuführen. Es werden ein Metamodell und Semantik präsentiert, welche Konzepte wie rechtliche Beziehungen und autonome und nichtautonome Aktionen sowie deren Zusammenspiel formalisieren. Auf Basis des Metamodells wird eine generische Softwarearchitekture eines Smart Contract Management System (SCMS) aufgebaut, welches alle Phasen im Lebenszyklus eines Smart Contracts unterstützt. Ein besonderes Augenmerk liegt hierbei auf der Ausführungsebene, in der Umgebungen mit mehreren heterogenen Blockchain-Netzwerken zur selben Zeit beachtet werden. Eine prototypische Implementierung zeigt die Realisierbarkeit wichtiger Aspekte des Vorschlags. Desweiteren werden zwei Aspekte im Detail betrachtet, die aufgrund der beschränkten und auf Transaktionen basierenden Ausführungsumgebung der DApps besonders herausfordernd sind: Die Unterstützung vollständig autonomer und fälschungssicherer Logik unter Einbeziehung außerhalb der Blockchain gehaltener Daten, sowie die Auswertung zeitlicher Fristen. Es werden verschiedene Lösungsstrategien, welche auch in anderen Szenarien genutzt werden können, eingeführt und evaluiert. KW - enforceability KW - smart contracts KW - blockchain KW - business process management KW - decentralized applications KW - Blockchain KW - Geschäftsprozessmanagement KW - Dezentrale Applikationen KW - Durchsetzbarkeit KW - Smart Contracts Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-519088 ER - TY - THES A1 - Lazaridou, Konstantina T1 - Revealing hidden patterns in political news and social media with machine learning T1 - Aufdecken versteckter Muster in politischen Nachrichten und sozialen Medien mit Hilfe von maschinellem Lernen N2 - As part of our everyday life we consume breaking news and interpret it based on our own viewpoints and beliefs. We have easy access to online social networking platforms and news media websites, where we inform ourselves about current affairs and often post about our own views, such as in news comments or social media posts. The media ecosystem enables opinions and facts to travel from news sources to news readers, from news article commenters to other readers, from social network users to their followers, etc. The views of the world many of us have depend on the information we receive via online news and social media. Hence, it is essential to maintain accurate, reliable and objective online content to ensure democracy and verity on the Web. To this end, we contribute to a trustworthy media ecosystem by analyzing news and social media in the context of politics to ensure that media serves the public interest. In this thesis, we use text mining, natural language processing and machine learning techniques to reveal underlying patterns in political news articles and political discourse in social networks. Mainstream news sources typically cover a great amount of the same news stories every day, but they often place them in a different context or report them from different perspectives. In this thesis, we are interested in how distinct and predictable newspaper journalists are, in the way they report the news, as a means to understand and identify their different political beliefs. To this end, we propose two models that classify text from news articles to their respective original news source, i.e., reported speech and also news comments. Our goal is to capture systematic quoting and commenting patterns by journalists and news commenters respectively, which can lead us to the newspaper where the quotes and comments are originally published. Predicting news sources can help us understand the potential subjective nature behind news storytelling and the magnitude of this phenomenon. Revealing this hidden knowledge can restore our trust in media by advancing transparency and diversity in the news. Media bias can be expressed in various subtle ways in the text and it is often challenging to identify these bias manifestations correctly, even for humans. However, media experts, e.g., journalists, are a powerful resource that can help us overcome the vague definition of political media bias and they can also assist automatic learners to find the hidden bias in the text. Due to the enormous technological advances in artificial intelligence, we hypothesize that identifying political bias in the news could be achieved through the combination of sophisticated deep learning modelsxi and domain expertise. Therefore, our second contribution is a high-quality and reliable news dataset annotated by journalists for political bias and a state-of-the-art solution for this task based on curriculum learning. Our aim is to discover whether domain expertise is necessary for this task and to provide an automatic solution for this traditionally manually-solved problem. User generated content is fundamentally different from news articles, e.g., messages are shorter, they are often personal and opinionated, they refer to specific topics and persons, etc. Regarding political and socio-economic news, individuals in online communities make use of social networks to keep their peers up-to-date and to share their own views on ongoing affairs. We believe that social media is also an as powerful instrument for information flow as the news sources are, and we use its unique characteristic of rapid news coverage for two applications. We analyze Twitter messages and debate transcripts during live political presidential debates to automatically predict the topics that Twitter users discuss. Our goal is to discover the favoured topics in online communities on the dates of political events as a way to understand the political subjects of public interest. With the up-to-dateness of microblogs, an additional opportunity emerges, namely to use social media posts and leverage the real-time verity about discussed individuals to find their locations. That is, given a person of interest that is mentioned in online discussions, we use the wisdom of the crowd to automatically track her physical locations over time. We evaluate our approach in the context of politics, i.e., we predict the locations of US politicians as a proof of concept for important use cases, such as to track people that are national risks, e.g., warlords and wanted criminals. N2 - Als festen Bestandteil unseres täglichen Lebens konsumieren wir aktuelle Nachrichten und interpretieren sie basierend auf unseren eigenen Ansichten und Überzeugungen. Wir haben einfachen Zugang zu sozialen Netzwerken und Online-Nachrichtenportalen, auf denen wir uns über aktuelle Angelegenheiten informieren und eigene Ansichten teilen, wie zum Beispiel mit Nachrichtenkommentaren oder Social-Media-Posts. Das Medien-Ökosystem ermöglicht es zum Beispiel, dass Meinungen und Fakten von Nachrichtenquellen zu Lesern, von Kommentatoren zu anderen Lesern oder von Nutzern sozialer Netzwerke zu ihren Anhängern gelangen. Die Weltsicht hängt für viele von uns von Informationen ab, die wir über Online-Nachrichten und soziale Medien erhalten. Hierfür ist es wichtig genaue, zuverlässige und objektive Inhalte zuzusichern, um die Demokratie und Wahrheit im Web gewährleisten zu können. Um zu einem vertrauenswürdigen Medien-Ökosystem beizutragen, analysieren wir Nachrichten und soziale Medien im politischen Kontext und stellen sicher, dass die Medien dem öffentlichen Interesse dienen. In dieser Arbeit verwenden wir Techniken der Computerlinguistik, des maschinellen Lernens und des Text Minings, um zugrunde liegende Muster in politischen Nachrichtenartikel und im politischen Diskurs in sozialen Netzwerken aufzudecken. Mainstream-Nachrichtenquellen decken täglich üb­li­cher­wei­se eine große Anzahl derselben Nachrichten ab, aber sie stellen diese oft in einem anderen Kontext dar oder berichten aus unterschiedlichen Sichtweisen. In dieser Arbeit wird untersucht, wie individuell und vorhersehbar Zeitungsjournalisten in der Art der Berichterstattung sind, um die unterschiedlichen politischen Überzeugungen zu identifizieren und zu verstehen. Zu diesem Zweck schlagen wir zwei Modelle vor, die Text aus Nachrichtenartikeln klassifizieren und ihrer jeweiligen ursprünglichen Nachrichtenquelle zuordnen, insbesondere basierend auf Zitaten und Nachrichtenkommentaren. Unser Ziel ist es, systematische Zitierungs- und Kommentierungsmuster von Journalisten bzw. Nachrichtenkommentatoren zu erfassen, was uns zu der Zeitung führen kann, in der die Zitate und Kommentare ursprünglich veröffentlicht wurden. Die Vorhersage von Nachrichtenquellen kann uns helfen, die potenziell subjektive Natur hinter dem “Storytelling” und dem Ausmaß dieses Phänomens zu verstehen. Das enthüllen jenes verborgenen Wissens kann unser Vertrauen in die Medien wiederherstellen, indem es Transparenz und Vielfalt in den Nachrichten fördert. Politische Tendenzen in der Medienberichterstattung können textuell auf verschiedene subtile Arten ausgedrückt werden und es ist selbst für Menschen oft schwierig deren Manifestierung korrekt zu identifizieren. Medienexperten wie Journalisten, sind jedoch eine gute Ressource, die uns helfen kann, die vage Definition der politischen Medien Bias zu überwinden und sie können ebenfalls dabei helfen automatischen Modellen beizubringen, versteckten Bias im Text aufzudecken. Aufgrund der enormen technologischen Fortschritte im Bereich der künstlichen Intelligenz nehmen wir an, dass die Identifizierung politischer Vorurteile in den Nachrichten durch die Kombination aus ausgefeilten Deep-Learning-Modellen und Fachkenntnissen erreicht werden kann. Daher ist unser zweiter Beitrag ein qualitativ hochwertiger und zuverlässiger Nachrichtendatensatz, der von Journalisten in Bezug auf politischen Bias annotiert wurde und ein hochmoderner Algorithmus zur Lösung dieser Aufgabe, der auf dem Prinzip des “curriculum learning” basiert. Unser Ziel ist es herauszufinden, ob Domänenwissen für diese Aufgabe erforderlich ist und eine automatische Lösung für dieses traditionell manuell bearbeitete Problem bereitzustellen. Nutzergenerierte Inhalte unterscheiden sich grundlegend von Nachrichtenartikeln. Zum Beispiel sind Botschaften oft kürzer, persönlich und dogmatisch und sie beziehen sich oft auf spezifische Themen und Personen. In Bezug auf politische und sozioökonomische Nachrichten verwenden Individuen oft soziale Netzwerke, um andere Nutzer in ihrer In­te­r­es­sens­grup­pe auf dem Laufenden zu halten und ihre persönlichen Ansichten über aktuelle Angelegenheiten zu teilen. Wir glauben, dass soziale Medien auch ein gleichermaßen leistungsfähiges Instrument für den Informationsfluss sind wie Online-Zeitungen. Daher verwenden wir ihre einzigartige Eigenschaft der schnellen Berichterstattung für zwei Anwendungen. Wir analysieren Twitter-Nachrichten und Transkripte von politischen Live-Debatten zur Präsidentschaftswahl um Themen zu klassifizieren, die von der Nutzergemeinde diskutiert werden. Unser Ziel ist es die bevorzugten Themen zu identifizieren, die in Online-Gemeinschaften zu den Terminen politischer Ereignisse diskutiert werden um die Themen von öffentlichem Interesse zu verstehen. Durch die Aktualität von Microblogs ergibt sich die zusätzliche Möglichkeit Beiträge aus sozialen Medien zu nutzen um Echtzeit-Informationen über besprochene Personen zu finden und ihre physischen Positionen zu bestimmen. Das heißt, bei einer Person von öffentlichem Interesse, die in Online-Diskussionen erwähnt wird, verwenden wir die Schwarmintelligenz der Nutzerbasis, um ihren Standort im Verlauf der Zeit automatisch zu verfolgen. Wir untersuchen unseren Ansatz im politischen Kontext, indem wir die Standorte von US-Politikern während des Präsidentschaftswahlkampfes voraussagen. Mit diesem Ansatz bieten wir eine Machbarkeitsstudie für andere wichtige Anwendungsfälle, beispielsweise um Menschen zu verfolgen, die ein nationales Risiko darstellen, wie Kriegsherren und gesuchte Kriminelle. KW - media bias KW - news KW - politics KW - machine learning KW - maschinelles Lernen KW - Medien Bias KW - Nachrichten KW - Politik Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-502734 ER - TY - THES A1 - Limberger, Daniel T1 - Concepts and techniques for 3D-embedded treemaps and their application to software visualization T1 - Konzepte und Techniken für 3D-eingebettete Treemaps und ihre Anwendung auf Softwarevisualisierung N2 - This thesis addresses concepts and techniques for interactive visualization of hierarchical data using treemaps. It explores (1) how treemaps can be embedded in 3D space to improve their information content and expressiveness, (2) how the readability of treemaps can be improved using level-of-detail and degree-of-interest techniques, and (3) how to design and implement a software framework for the real-time web-based rendering of treemaps embedded in 3D. With a particular emphasis on their application, use cases from software analytics are taken to test and evaluate the presented concepts and techniques. Concerning the first challenge, this thesis shows that a 3D attribute space offers enhanced possibilities for the visual mapping of data compared to classical 2D treemaps. In particular, embedding in 3D allows for improved implementation of visual variables (e.g., by sketchiness and color weaving), provision of new visual variables (e.g., by physically based materials and in situ templates), and integration of visual metaphors (e.g., by reference surfaces and renderings of natural phenomena) into the three-dimensional representation of treemaps. For the second challenge—the readability of an information visualization—the work shows that the generally higher visual clutter and increased cognitive load typically associated with three-dimensional information representations can be kept low in treemap-based representations of both small and large hierarchical datasets. By introducing an adaptive level-of-detail technique, we cannot only declutter the visualization results, thereby reducing cognitive load and mitigating occlusion problems, but also summarize and highlight relevant data. Furthermore, this approach facilitates automatic labeling, supports the emphasis on data outliers, and allows visual variables to be adjusted via degree-of-interest measures. The third challenge is addressed by developing a real-time rendering framework with WebGL and accumulative multi-frame rendering. The framework removes hardware constraints and graphics API requirements, reduces interaction response times, and simplifies high-quality rendering. At the same time, the implementation effort for a web-based deployment of treemaps is kept reasonable. The presented visualization concepts and techniques are applied and evaluated for use cases in software analysis. In this domain, data about software systems, especially about the state and evolution of the source code, does not have a descriptive appearance or natural geometric mapping, making information visualization a key technology here. In particular, software source code can be visualized with treemap-based approaches because of its inherently hierarchical structure. With treemaps embedded in 3D, we can create interactive software maps that visually map, software metrics, software developer activities, or information about the evolution of software systems alongside their hierarchical module structure. Discussions on remaining challenges and opportunities for future research for 3D-embedded treemaps and their applications conclude the thesis. N2 - Diese Doktorarbeit behandelt Konzepte und Techniken zur interaktiven Visualisierung hierarchischer Daten mit Hilfe von Treemaps. Sie untersucht (1), wie Treemaps im 3D-Raum eingebettet werden können, um ihre Informationsinhalte und Ausdrucksfähigkeit zu verbessern, (2) wie die Lesbarkeit von Treemaps durch Techniken wie Level-of-Detail und Degree-of-Interest verbessert werden kann, und (3) wie man ein Software-Framework für das Echtzeit-Rendering von Treemaps im 3D-Raum entwirft und implementiert. Dabei werden Anwendungsfälle aus der Software-Analyse besonders betont und zur Verprobung und Bewertung der Konzepte und Techniken verwendet. Hinsichtlich der ersten Herausforderung zeigt diese Arbeit, dass ein 3D-Attributraum im Vergleich zu klassischen 2D-Treemaps verbesserte Möglichkeiten für die visuelle Kartierung von Daten bietet. Insbesondere ermöglicht die Einbettung in 3D eine verbesserte Umsetzung von visuellen Variablen (z.B. durch Skizzenhaftigkeit und Farbverwebungen), die Bereitstellung neuer visueller Variablen (z.B. durch physikalisch basierte Materialien und In-situ-Vorlagen) und die Integration visueller Metaphern (z.B. durch Referenzflächen und Darstellungen natürlicher Phänomene) in die dreidimensionale Darstellung von Treemaps. Für die zweite Herausforderung – die Lesbarkeit von Informationsvisualisierungen – zeigt die Arbeit, dass die allgemein höhere visuelle Unübersichtlichkeit und die damit einhergehende, erhöhte kognitive Belastung, die typischerweise mit dreidimensionalen Informationsdarstellungen verbunden sind, in Treemap-basierten Darstellungen sowohl kleiner als auch großer hierarchischer Datensätze niedrig gehalten werden können. Durch die Einführung eines adaptiven Level-of-Detail-Verfahrens lassen sich nicht nur die Visualisierungsergebnisse übersichtlicher gestalten, die kognitive Belastung reduzieren und Verdeckungsprobleme verringern, sondern auch relevante Daten zusammenfassen und hervorheben. Darüber hinaus erleichtert dieser Ansatz eine automatische Beschriftung, unterstützt die Hervorhebung von Daten-Ausreißern und ermöglicht die Anpassung von visuellen Variablen über Degree-of-Interest-Maße. Die dritte Herausforderung wird durch die Entwicklung eines Echtzeit-Rendering-Frameworks mit WebGL und akkumulativem Multi-Frame-Rendering angegangen. Das Framework hebt mehrere Hardwarebeschränkungen und Anforderungen an die Grafik-API auf, verkürzt die Reaktionszeiten auf Interaktionen und vereinfacht qualitativ hochwertiges Rendering. Gleichzeitig wird der Implementierungsaufwand für einen webbasierten Einsatz von Treemaps geringgehalten. Die vorgestellten Visualisierungskonzepte und -techniken werden für Anwendungsfälle in der Softwareanalyse eingesetzt und evaluiert. In diesem Bereich haben Daten über Softwaresysteme, insbesondere über den Zustand und die Evolution des Quellcodes, keine anschauliche Erscheinung oder natürliche geometrische Zuordnung, so dass die Informationsvisualisierung hier eine Schlüsseltechnologie darstellt. Insbesondere Softwarequellcode kann aufgrund seiner inhärenten hierarchischen Struktur mit Hilfe von Treemap-basierten Ansätzen visualisiert werden. Mit in 3D-eingebetteten Treemaps können wir interaktive Softwarelagekarten erstellen, die z.B. Softwaremetriken, Aktivitäten von Softwareentwickler*innen und Informationen über die Evolution von Softwaresystemen in ihrer hierarchischen Modulstruktur abbilden und veranschaulichen. Diskussionen über verbleibende Herausforderungen und Möglichkeiten für zukünftige Forschung zu 3D-eingebetteten Treemaps und deren Anwendungen schließen die Arbeit ab. KW - treemaps KW - software visualization KW - software analytics KW - web-based rendering KW - degree-of-interest techniques KW - labeling KW - 3D-embedding KW - interactive visualization KW - progressive rendering KW - hierarchical data KW - 3D-Einbettung KW - Interessengrad-Techniken KW - hierarchische Daten KW - interaktive Visualisierung KW - Beschriftung KW - progressives Rendering KW - Softwareanalytik KW - Softwarevisualisierung KW - Treemaps KW - Web-basiertes Rendering Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-632014 ER - TY - THES A1 - Lindinger, Jakob T1 - Variational inference for composite Gaussian process models T1 - Variationelle Inferenz für zusammengesetzte Gauß-Prozess Modelle N2 - Most machine learning methods provide only point estimates when being queried to predict on new data. This is problematic when the data is corrupted by noise, e.g. from imperfect measurements, or when the queried data point is very different to the data that the machine learning model has been trained with. Probabilistic modelling in machine learning naturally equips predictions with corresponding uncertainty estimates which allows a practitioner to incorporate information about measurement noise into the modelling process and to know when not to trust the predictions. A well-understood, flexible probabilistic framework is provided by Gaussian processes that are ideal as building blocks of probabilistic models. They lend themself naturally to the problem of regression, i.e., being given a set of inputs and corresponding observations and then predicting likely observations for new unseen inputs, and can also be adapted to many more machine learning tasks. However, exactly inferring the optimal parameters of such a Gaussian process model (in a computationally tractable manner) is only possible for regression tasks in small data regimes. Otherwise, approximate inference methods are needed, the most prominent of which is variational inference. In this dissertation we study models that are composed of Gaussian processes embedded in other models in order to make those more flexible and/or probabilistic. The first example are deep Gaussian processes which can be thought of as a small network of Gaussian processes and which can be employed for flexible regression. The second model class that we study are Gaussian process state-space models. These can be used for time-series modelling, i.e., the task of being given a stream of data ordered by time and then predicting future observations. For both model classes the state-of-the-art approaches offer a trade-off between expressive models and computational properties (e.g. speed or convergence properties) and mostly employ variational inference. Our goal is to improve inference in both models by first getting a deep understanding of the existing methods and then, based on this, to design better inference methods. We achieve this by either exploring the existing trade-offs or by providing general improvements applicable to multiple methods. We first provide an extensive background, introducing Gaussian processes and their sparse (approximate and efficient) variants. We continue with a description of the models under consideration in this thesis, deep Gaussian processes and Gaussian process state-space models, including detailed derivations and a theoretical comparison of existing methods. Then we start analysing deep Gaussian processes more closely: Trading off the properties (good optimisation versus expressivity) of state-of-the-art methods in this field, we propose a new variational inference based approach. We then demonstrate experimentally that our new algorithm leads to better calibrated uncertainty estimates than existing methods. Next, we turn our attention to Gaussian process state-space models, where we closely analyse the theoretical properties of existing methods.The understanding gained in this process leads us to propose a new inference scheme for general Gaussian process state-space models that incorporates effects on multiple time scales. This method is more efficient than previous approaches for long timeseries and outperforms its comparison partners on data sets in which effects on multiple time scales (fast and slowly varying dynamics) are present. Finally, we propose a new inference approach for Gaussian process state-space models that trades off the properties of state-of-the-art methods in this field. By combining variational inference with another approximate inference method, the Laplace approximation, we design an efficient algorithm that outperforms its comparison partners since it achieves better calibrated uncertainties. N2 - Bei Vorhersagen auf bisher ungesehenen Datenpunkten liefern die meisten maschinellen Lernmethoden lediglich Punktprognosen. Dies kann problematisch sein, wenn die Daten durch Rauschen verfälscht sind, z. B. durch unvollkommene Messungen, oder wenn der abgefragte Datenpunkt sich stark von den Daten unterscheidet, mit denen das maschinelle Lernmodell trainiert wurde. Mithilfe probabilistischer Modellierung (einem Teilgebiet des maschinellen Lernens) werden die Vorhersagen der Methoden auf natürliche Weise durch Unsicherheiten ergänzt. Dies erlaubt es, Informationen über Messunsicherheiten in den Modellierungsprozess mit einfließen zu lassen, sowie abzuschätzen, bei welchen Vorhersagen dem Modell vertraut werden kann. Grundlage vieler probabilistischer Modelle bilden Gaußprozesse, die gründlich erforscht und äußerst flexibel sind und daher häufig als Bausteine für größere Modelle dienen. Für Regressionsprobleme, was heißt, von einem Datensatz bestehend aus Eingangsgrößen und zugehörigen Messungen auf wahrscheinliche Messwerte für bisher ungesehene Eingangsgrößen zu schließen, sind Gaußprozesse hervorragend geeignet. Zusätzlich können sie an viele weitere Aufgabenstellungen des maschinellen Lernens angepasst werden. Die Bestimmung der optimalen Parameter eines solchen Gaußprozessmodells (in einer annehmbaren Zeit) ist jedoch nur für Regression auf kleinen Datensätzen möglich. In allen anderen Fällen muss auf approximative Inferenzmethoden zurückgegriffen werden, wobei variationelle Inferenz die bekannteste ist. In dieser Dissertation untersuchen wir Modelle, die Gaußprozesse eingebettet in andere Modelle enthalten, um Letztere flexibler und/oder probabilistisch zu machen. Das erste Beispiel hierbei sind tiefe Gaußprozesse, die man sich als kleines Netzwerk von Gaußprozessen vorstellen kann und die für flexible Regression eingesetzt werden können. Die zweite Modellklasse, die wir genauer analysieren ist die der Gaußprozess-Zustandsraummodelle. Diese können zur Zeitreihenmodellierung verwendet werden, das heißt, um zukünftige Datenpunkte auf Basis eines nach der Zeit geordneten Eingangsdatensatzes vorherzusagen. Für beide genannten Modellklassen bieten die modernsten Ansatze einen Kompromiss zwischen expressiven Modellen und wunschenswerten rechentechnischen Eigenschaften (z. B. Geschwindigkeit oder Konvergenzeigenschaften). Desweiteren wird für die meisten Methoden variationelle Inferenz verwendet. Unser Ziel ist es, die Inferenz für beide Modellklassen zu verbessern, indem wir zunächst ein tieferes Verständnis der bestehenden Ansätze erlangen und darauf aufbauend bessere Inferenzverfahren entwickeln. Indem wir die bestehenden Kompromisse der heutigen Methoden genauer untersuchen, oder dadurch, dass wir generelle Verbesserungen anbieten, die sich auf mehrere Modelle anwenden lassen, erreichen wir dieses Ziel. Wir beginnen die Thesis mit einer umfassender Einführung, die den notwendigen technischen Hintergrund zu Gaußprozessen sowie spärlichen (approximativen und effizienten) Gaußprozessen enthält. Anschließend werden die in dieser Thesis behandelten Modellklassen, tiefe Gaußprozesse und Gaußprozess-Zustandsraummodelle, eingeführt, einschließlich detaillierter Herleitungen und eines theoretischen Vergleichs existierender Methoden. Darauf aufbauend untersuchen wir zuerst tiefe Gaußprozesse genauer und entwickeln dann eine neue Inferenzmethode. Diese basiert darauf, die wünschenswerten Eigenschaften (gute Optimierungseigenschaften gegenüber Expressivität) der modernsten Ansätze gegeneinander abzuwägen. Anschließend zeigen wir experimentell, dass unser neuer Algorithmus zu besser kalibrierten Unsicherheitsabschätzungen als bei bestehenden Methoden führt. Als Nächstes wenden wir uns Gaußprozess-Zustandsraummodelle zu, wo wir zuerst die theoretischen Eigenschaften existierender Ansätze genau analysieren. Wir nutzen das dabei gewonnene Verständnis, um ein neues Inferenzverfahren für Gaußprozess-Zustandsraummodelle einzuführen, welches Effekte auf verschiedenen Zeitskalen berücksichtigt. Für lange Zeitreihen ist diese Methode effizienter als bisherige Ansätze. Darüber hinaus übertrifft sie ihre Vergleichspartner auf Datensätzen, bei denen Effekte auf mehreren Zeitskalen (sich schnell und langsam verändernde Signale) auftreten. Zuletzt schlagen wir ein weiteres neues Inferenzverfahren für Gaußprozess-Zustandsraummodelle vor, das die Eigenschaften der aktuellsten Methoden auf diesem Gebiet gegeneinander abwägt. Indem wir variationelle Inferenz mit einem weiteren approximativen Inferenzverfahren, der Laplace- Approximation, kombinieren, entwerfen wir einen effizienten Algorithmus der seine Vergleichspartner dadurch übertrifft, dass er besser kalibrierte Unsicherheitsvorhersagen erzielt. KW - probabilistic machine learning KW - Gaussian processes KW - variational inference KW - deep Gaussian processes KW - Gaussian process state-space models KW - Gauß-Prozess Zustandsraummodelle KW - Gauß-Prozesse KW - tiefe Gauß-Prozesse KW - probabilistisches maschinelles Lernen KW - variationelle Inferenz Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-604441 ER - TY - THES A1 - Lopes, Pedro T1 - Interactive Systems Based on Electrical Muscle Stimulation N2 - How can interactive devices connect with users in the most immediate and intimate way? This question has driven interactive computing for decades. Throughout the last decades, we witnessed how mobile devices moved computing into users’ pockets, and recently, wearables put computing in constant physical contact with the user’s skin. In both cases moving the devices closer to users allowed devices to sense more of the user, and thus act more personal. The main question that drives our research is: what is the next logical step? Some researchers argue that the next generation of interactive devices will move past the user’s skin and be directly implanted inside the user’s body. This has already happened in that we have pacemakers, insulin pumps, etc. However, we argue that what we see is not devices moving towards the inside of the user’s body, but rather towards the body’s biological “interface” they need to address in order to perform their function. To implement our vision, we created a set of devices that intentionally borrow parts of the user’s body for input and output, rather than adding more technology to the body. In this dissertation we present one specific flavor of such devices, i.e., devices that borrow the user’s muscles. We engineered I/O devices that interact with the user by reading and controlling muscle activity. To achieve the latter, our devices are based on medical-grade signal generators and electrodes attached to the user’s skin that send electrical impulses to the user’s muscles; these impulses then cause the user’s muscles to contract. While electrical muscle stimulation (EMS) devices have been used to regenerate lost motor functions in rehabilitation medicine since the 1960s, in this dissertation, we propose a new perspective: EMS as a means for creating interactive systems. We start by presenting seven prototypes of interactive devices that we have created to illustrate several benefits of EMS. These devices form two main categories: (1) Devices that allow users eyes-free access to information by means of their proprioceptive sense, such as the value of a variable in a computer system, a tool, or a plot; (2) Devices that increase immersion in virtual reality by simulating large forces, such as wind, physical impact, or walls and heavy objects. Then, we analyze the potential of EMS to build interactive systems that miniaturize well and discuss how they leverage our proprioceptive sense as an I/O modality. We proceed by laying out the benefits and disadvantages of both EMS and mechanical haptic devices, such as exoskeletons. We conclude by sketching an outline for future research on EMS by listing open technical, ethical and philosophical questions that we left unanswered. N2 - Wie können interaktive Geräte auf unmittelbare und eng verknüpfte Weise mit dem Nutzer kommunizieren? Diese Frage beschäftigt die Forschung im Bereich Computer Interaktion seit Jahrzehnten. Besonders in den letzten Jahren haben wir miterlebt, wie Nutzer interaktive Geräte dauerhaft bei sich führen, im Falle von sogenannten Wearables sogar als Teil der Kleidung oder als Accessoires. In beiden Fällen sind die Geräte näher an den Nutzer gerückt, wodurch sie mehr Informationen vom Nutzer sammeln können und daher persönlicher erscheinen. Die Hauptfrage, die unsere Forschung antreibt, ist: Was ist der nächste logische Schritt in der Entwicklung interaktiver Geräte? Mache Wissenschaftler argumentieren, dass die Haut nicht mehr die Barriere für die nächste Generation von interaktiven Geräten sein wird, sondern dass diese direkt in den Körper der Nutzer implantiert werden. Zum Teil ist dies auch bereits passiert, wie Herzschrittmacher oder Insulinpumpen zeigen. Wir argumentieren jedoch, dass Geräte sich in Zukunft nicht zwingend innerhalb des Körpers befinden müssen, sondern sich an der richtigen „Schnittstelle“ befinden sollen, um die Funktion des Gerätes zu ermöglichen. Um diese Entwicklung voranzutreiben haben wir Geräte entwickelt, die Teile des Körpers selbst als Ein- und Ausgabe-Schnittstelle verwenden, anstatt weitere Geräte an den Körper anzubringen. In dieser Dissertation zeigen wir eine bestimmte Art dieser Geräte, nämlich solche, die Muskeln verwenden. Wir haben Ein-/Ausgabegeräte gebaut, die mit dem Nutzer interagieren indem sie Muskelaktivität erkennen und kontrollieren. Um Muskelaktivität zu kontrollieren benutzen wir Signalgeber von medizinischer Qualität, die mithilfe von auf die Haut geklebten Elektroden elektrische Signale an die Muskeln des Nutzers senden. Diese Signale bewirken dann eine Kontraktion des Muskels. Geräte zur elektrischen Muskelstimulation (EMS) werden seit den 1960er-Jahren zur Regeneration von motorischen Funktionen verwendet. In dieser Dissertation schlagen wir jedoch einen neuen Ansatz vor: elektrische Muskelstimulation als Kommunikationskanal zwischen Mensch und interaktiven Computersysteme. Zunächst stellen wir unsere sieben interaktiven Prototypen vor, welche die zahlreichen Vorteile von EMS demonstrieren. Diese Geräte können in zwei Hauptkategorien unterteilt werden: (1) Geräte, die Nutzern Zugang zu Information direkt über ihre propriozeptive Wahrnehmung geben ohne einen visuellen Reiz. Diese Informationen können zum Beispiel Variablen, Diagramme oder die Handhabung von Werkzeugen beinhalten. (2) Des Weiteren zeigen wir Geräte, welche die Immersion in virtuelle Umgebungen erhöhen indem sie physikalische Kräfte wie Wind, physischen Kontakt, Wände oder schwere Objekte, simulieren. Wir analysieren in dieser Arbeit außerdem das Potential von EMS für miniaturisierte interaktive Systeme und diskutieren, wie solche EMS Systeme die propriozeptive Wahrnehmung wirksam als Ein-/Ausgabemodalität nutzen können. Dazu stellen wir die Vor- und Nachteile von EMS und mechanisch-haptischen Geräten, wie zum Beispiel Exoskeletten, gegenüber. Zum Abschluss skizzieren wir zukünftige Richtungen in der Erforschung von interaktiven EMS Systemen, indem wir bislang offen gebliebene technische, ethische und philosophische Fragen aufzeigen. KW - electrical muscle stimulation KW - wearables KW - virtual reality KW - Wearable KW - elektrische Muskelstimulation KW - virtuelle Realität Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-421165 ER - TY - THES A1 - Loster, Michael T1 - Knowledge base construction with machine learning methods T1 - Aufbau von Wissensbasen mit Methoden des maschinellen Lernens N2 - Modern knowledge bases contain and organize knowledge from many different topic areas. Apart from specific entity information, they also store information about their relationships amongst each other. Combining this information results in a knowledge graph that can be particularly helpful in cases where relationships are of central importance. Among other applications, modern risk assessment in the financial sector can benefit from the inherent network structure of such knowledge graphs by assessing the consequences and risks of certain events, such as corporate insolvencies or fraudulent behavior, based on the underlying network structure. As public knowledge bases often do not contain the necessary information for the analysis of such scenarios, the need arises to create and maintain dedicated domain-specific knowledge bases. This thesis investigates the process of creating domain-specific knowledge bases from structured and unstructured data sources. In particular, it addresses the topics of named entity recognition (NER), duplicate detection, and knowledge validation, which represent essential steps in the construction of knowledge bases. As such, we present a novel method for duplicate detection based on a Siamese neural network that is able to learn a dataset-specific similarity measure which is used to identify duplicates. Using the specialized network architecture, we design and implement a knowledge transfer between two deduplication networks, which leads to significant performance improvements and a reduction of required training data. Furthermore, we propose a named entity recognition approach that is able to identify company names by integrating external knowledge in the form of dictionaries into the training process of a conditional random field classifier. In this context, we study the effects of different dictionaries on the performance of the NER classifier. We show that both the inclusion of domain knowledge as well as the generation and use of alias names results in significant performance improvements. For the validation of knowledge represented in a knowledge base, we introduce Colt, a framework for knowledge validation based on the interactive quality assessment of logical rules. In its most expressive implementation, we combine Gaussian processes with neural networks to create Colt-GP, an interactive algorithm for learning rule models. Unlike other approaches, Colt-GP uses knowledge graph embeddings and user feedback to cope with data quality issues of knowledge bases. The learned rule model can be used to conditionally apply a rule and assess its quality. Finally, we present CurEx, a prototypical system for building domain-specific knowledge bases from structured and unstructured data sources. Its modular design is based on scalable technologies, which, in addition to processing large datasets, ensures that the modules can be easily exchanged or extended. CurEx offers multiple user interfaces, each tailored to the individual needs of a specific user group and is fully compatible with the Colt framework, which can be used as part of the system. We conduct a wide range of experiments with different datasets to determine the strengths and weaknesses of the proposed methods. To ensure the validity of our results, we compare the proposed methods with competing approaches. N2 - Moderne Wissensbasen enthalten und organisieren das Wissen vieler unterschiedlicher Themengebiete. So speichern sie neben bestimmten Entitätsinformationen auch Informationen über deren Beziehungen untereinander. Kombiniert man diese Informationen, ergibt sich ein Wissensgraph, der besonders in Anwendungsfällen hilfreich sein kann, in denen Entitätsbeziehungen von zentraler Bedeutung sind. Neben anderen Anwendungen, kann die moderne Risikobewertung im Finanzsektor von der inhärenten Netzwerkstruktur solcher Wissensgraphen profitieren, indem Folgen und Risiken bestimmter Ereignisse, wie z.B. Unternehmensinsolvenzen oder betrügerisches Verhalten, auf Grundlage des zugrundeliegenden Netzwerks bewertet werden. Da öffentliche Wissensbasen oft nicht die notwendigen Informationen zur Analyse solcher Szenarien enthalten, entsteht die Notwendigkeit, spezielle domänenspezifische Wissensbasen zu erstellen und zu pflegen. Diese Arbeit untersucht den Erstellungsprozess von domänenspezifischen Wissensdatenbanken aus strukturierten und unstrukturierten Datenquellen. Im speziellen befasst sie sich mit den Bereichen Named Entity Recognition (NER), Duplikaterkennung sowie Wissensvalidierung, die wesentliche Prozessschritte beim Aufbau von Wissensbasen darstellen. Wir stellen eine neuartige Methode zur Duplikaterkennung vor, die auf Siamesischen Neuronalen Netzwerken basiert und in der Lage ist, ein datensatz-spezifisches Ähnlichkeitsmaß zu erlernen, welches wir zur Identifikation von Duplikaten verwenden. Unter Verwendung einer speziellen Netzwerkarchitektur entwerfen und setzen wir einen Wissenstransfer zwischen Deduplizierungsnetzwerken um, der zu erheblichen Leistungsverbesserungen und einer Reduktion der benötigten Trainingsdaten führt. Weiterhin schlagen wir einen Ansatz zur Erkennung benannter Entitäten (Named Entity Recognition (NER)) vor, der in der Lage ist, Firmennamen zu identifizieren, indem externes Wissen in Form von Wörterbüchern in den Trainingsprozess eines Conditional Random Field Klassifizierers integriert wird. In diesem Zusammenhang untersuchen wir die Auswirkungen verschiedener Wörterbücher auf die Leistungsfähigkeit des NER-Klassifikators und zeigen, dass sowohl die Einbeziehung von Domänenwissen als auch die Generierung und Verwendung von Alias-Namen zu einer signifikanten Leistungssteigerung führt. Zur Validierung der in einer Wissensbasis enthaltenen Fakten stellen wir mit COLT ein Framework zur Wissensvalidierung vor, dass auf der interaktiven Qualitätsbewertung von logischen Regeln basiert. In seiner ausdrucksstärksten Implementierung kombinieren wir Gauß'sche Prozesse mit neuronalen Netzen, um so COLT-GP, einen interaktiven Algorithmus zum Erlernen von Regelmodellen, zu erzeugen. Im Gegensatz zu anderen Ansätzen verwendet COLT-GP Knowledge Graph Embeddings und Nutzer-Feedback, um Datenqualitätsprobleme des zugrunde liegenden Wissensgraphen zu behandeln. Das von COLT-GP erlernte Regelmodell kann sowohl zur bedingten Anwendung einer Regel als auch zur Bewertung ihrer Qualität verwendet werden. Schließlich stellen wir mit CurEx, ein prototypisches System zum Aufbau domänenspezifischer Wissensbasen aus strukturierten und unstrukturierten Datenquellen, vor. Sein modularer Aufbau basiert auf skalierbaren Technologien, die neben der Verarbeitung großer Datenmengen auch die einfache Austausch- und Erweiterbarkeit einzelner Module gewährleisten. CurEx bietet mehrere Benutzeroberflächen, die jeweils auf die individuellen Bedürfnisse bestimmter Benutzergruppen zugeschnitten sind. Darüber hinaus ist es vollständig kompatibel zum COLT-Framework, was als Teil des Systems verwendet werden kann. Wir führen eine Vielzahl von Experimenten mit unterschiedlichen Datensätzen durch, um die Stärken und Schwächen der vorgeschlagenen Methoden zu ermitteln. Zudem vergleichen wir die vorgeschlagenen Methoden mit konkurrierenden Ansätzen, um die Validität unserer Ergebnisse sicherzustellen. KW - machine learning KW - deep kernel learning KW - knowledge base construction KW - knowledge base KW - knowledge graph KW - deduplication KW - siamese neural networks KW - duplicate detection KW - entity resolution KW - transfer learning KW - knowledge transfer KW - entity linking KW - knowledge validation KW - logic rules KW - named entity recognition KW - curex KW - Curex KW - Deduplikation KW - Deep Kernel Learning KW - Duplikaterkennung KW - Entitätsverknüpfung KW - Entitätsauflösung KW - Wissensbasis KW - Konstruktion von Wissensbasen KW - Wissensgraph KW - Wissenstransfer KW - Wissensvalidierung KW - logische Regeln KW - maschinelles Lernen KW - named entity recognition KW - Siamesische Neuronale Netzwerke KW - Transferlernen Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-501459 ER - TY - THES A1 - Mandal, Sankalita T1 - Event handling in business processes T1 - Ereignisbehandlung in Geschäftsprozessen BT - flexible event subscription for business process enactment BT - flexibles Ereignisabonnement für die Durchführung von Geschäftsprozessen N2 - Business process management (BPM) deals with modeling, executing, monitoring, analyzing, and improving business processes. During execution, the process communicates with its environment to get relevant contextual information represented as events. Recent development of big data and the Internet of Things (IoT) enables sources like smart devices and sensors to generate tons of events which can be filtered, grouped, and composed to trigger and drive business processes. The industry standard Business Process Model and Notation (BPMN) provides several event constructs to capture the interaction possibilities between a process and its environment, e.g., to instantiate a process, to abort an ongoing activity in an exceptional situation, to take decisions based on the information carried by the events, as well as to choose among the alternative paths for further process execution. The specifications of such interactions are termed as event handling. However, in a distributed setup, the event sources are most often unaware of the status of process execution and therefore, an event is produced irrespective of the process being ready to consume it. BPMN semantics does not support such scenarios and thus increases the chance of processes getting delayed or getting in a deadlock by missing out on event occurrences which might still be relevant. The work in this thesis reviews the challenges and shortcomings of integrating real-world events into business processes, especially the subscription management. The basic integration is achieved with an architecture consisting of a process modeler, a process engine, and an event processing platform. Further, points of subscription and unsubscription along the process execution timeline are defined for different BPMN event constructs. Semantic and temporal dependencies among event subscription, event occurrence, event consumption and event unsubscription are considered. To this end, an event buffer with policies for updating the buffer, retrieving the most suitable event for the current process instance, and reusing the event has been discussed that supports issuing of early subscription. The Petri net mapping of the event handling model provides our approach with a translation of semantics from a business process perspective. Two applications based on this formal foundation are presented to support the significance of different event handling configurations on correct process execution and reachability of a process path. Prototype implementations of the approaches show that realizing flexible event handling is feasible with minor extensions of off-the-shelf process engines and event platforms. N2 - Das Prozessmanagement befasst sich mit der Modellierung, Ausführung, Überwachung, Analyse und Verbesserung von Geschäftsprozessen. Während seiner Ausführung kommuniziert der Prozess mit seiner Umgebung, um relevante Kontextinformationen in Form von Ereignissen zu erhalten. Der jüngste Fortschritt im Bereich Big Data und dem Internet der Dinge ermöglicht Smart Devices und Sensoren eine Vielzahl von Ereignissen zu generieren, welche gefiltert, gruppiert und kombiniert werden können, um Geschäftsprozesse zu triggern und vor anzutreiben. Der Industriestandard Business Process Model and Notation (BPMN) stellt mehrere Ereigniskonstrukte bereit, um die Interaktionsmöglichkeiten eines Prozesses mit seiner Umgebung zu erfassen. Beispielsweise können Prozesse durch Ereignisse gestartet, laufende Aktivitäten in Ausnahmefällen abgebrochen, Entscheidungen auf Basis der Ereignisinformationen getroffen, und alternative Ausführungspfade gewählt werden. Die Spezifikation solcher Interaktionen wird als Event Handling bezeichnet. Allerdings sind sich insbesondere in verteilten Systemen die Ereignisquellen des Zustands des Prozesses unbewusst. Daher werden Ereignisse unabhängig davon produziert, ob der Prozess bereit ist sie zu konsumieren. Die BPMN-Semantik sieht solche Situationen jedoch nicht vor, sodass die Möglichkeit besteht, dass das Auftreten von relevanten Ereignissen versäumt wird. Dies kann zu Verzögerungen oder gar Deadlocks in der Prozessauführung führen. Die vorliegende Dissertation untersucht die Mängel und Herausforderungen der Integration von Ereignissen und Geschäftsprozessen, insbesondere in Bezug auf das Subscription Management. Die grundlegende Integration wird durch eine Architektur erreicht, die aus einer Prozessmodellierungskomponente, einer Ausführungskomponente und einer Ereignisverarbeitungskomponente besteht. Ferner werden Points of Subscription and Unsubscription für verschiedene BPMN-Ereigniskonstrukte entlang der Zeitachse der Prozessausführung definiert. Semantische und temporale Abhängigkeiten zwischen der Subscription, dem Auftreten, dem Konsumieren und der Unsubscription eines Ereignisses werden betrachtet. In dieser Hinsicht wird ein Event Bufferdiskutiert, welcher mit Strategien zum Update des Puffers, zum Abruf der geeigneten Ereignisse für den laufenden Prozess, sowie zur Wiederverwendung von Ereignissen ausgestattet ist. Die Abbildung des Event Handling Modells in ein Petri-Netz versieht den beschriebenen Ansatz mit einer eindeutigen Semantik. Basierend auf diesem Formalismus werden zwei Anwendungen demonstriert, die die Relevanz verschiedener Konfigurationen des Event Handlings für eine korrekte Prozessausführung aufzeigen. Eine prototypische Implementierung des Ansatzes beweist dessen Umsetzbarkeit durch geringe Erweiterungen bestehender Software zur Prozessausführung und Ereignisverarbeitung. KW - business process managament KW - complex event processing KW - BPMN KW - event subscription KW - Geschäftsprozessmanagement KW - komplexe Ereignisverarbeitung KW - BPMN KW - Ereignisabonnement Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-441700 ER - TY - THES A1 - Marwecki, Sebastian T1 - Virtualizing physical space T1 - Virtualisierung von Physischem Raum N2 - The true cost for virtual reality is not the hardware, but the physical space it requires, as a one-to-one mapping of physical space to virtual space allows for the most immersive way of navigating in virtual reality. Such “real-walking” requires physical space to be of the same size and the same shape of the virtual world represented. This generally prevents real-walking applications from running on any space that they were not designed for. To reduce virtual reality’s demand for physical space, creators of such applications let users navigate virtual space by means of a treadmill, altered mappings of physical to virtual space, hand-held controllers, or gesture-based techniques. While all of these solutions succeed at reducing virtual reality’s demand for physical space, none of them reach the same level of immersion that real-walking provides. Our approach is to virtualize physical space: instead of accessing physical space directly, we allow applications to express their need for space in an abstract way, which our software systems then map to the physical space available. We allow real-walking applications to run in spaces of different size, different shape, and in spaces containing different physical objects. We also allow users immersed in different virtual environments to share the same space. Our systems achieve this by using a tracking volume-independent representation of real-walking experiences — a graph structure that expresses the spatial and logical relationships between virtual locations, virtual elements contained within those locations, and user interactions with those elements. When run in a specific physical space, this graph representation is used to define a custom mapping of the elements of the virtual reality application and the physical space by parsing the graph using a constraint solver. To re-use space, our system splits virtual scenes and overlap virtual geometry. The system derives this split by means of hierarchically clustering of our virtual objects as nodes of our bi-partite directed graph that represents the logical ordering of events of the experience. We let applications express their demands for physical space and use pre-emptive scheduling between applications to have them share space. We present several application examples enabled by our system. They all enable real-walking, despite being mapped to physical spaces of different size and shape, containing different physical objects or other users. We see substantial real-world impact in our systems. Today’s commercial virtual reality applications are generally designing to be navigated using less immersive solutions, as this allows them to be operated on any tracking volume. While this is a commercial necessity for the developers, it misses out on the higher immersion offered by real-walking. We let developers overcome this hurdle by allowing experiences to bring real-walking to any tracking volume, thus potentially bringing real-walking to consumers. Die eigentlichen Kosten für Virtual Reality Anwendungen entstehen nicht primär durch die erforderliche Hardware, sondern durch die Nutzung von physischem Raum, da die eins-zu-eins Abbildung von physischem auf virtuellem Raum die immersivste Art von Navigation ermöglicht. Dieses als „Real-Walking“ bezeichnete Erlebnis erfordert hinsichtlich Größe und Form eine Entsprechung von physischem Raum und virtueller Welt. Resultierend daraus können Real-Walking-Anwendungen nicht an Orten angewandt werden, für die sie nicht entwickelt wurden. Um den Bedarf an physischem Raum zu reduzieren, lassen Entwickler von Virtual Reality-Anwendungen ihre Nutzer auf verschiedene Arten navigieren, etwa mit Hilfe eines Laufbandes, verfälschten Abbildungen von physischem zu virtuellem Raum, Handheld-Controllern oder gestenbasierten Techniken. All diese Lösungen reduzieren zwar den Bedarf an physischem Raum, erreichen jedoch nicht denselben Grad an Immersion, den Real-Walking bietet. Unser Ansatz zielt darauf, physischen Raum zu virtualisieren: Anstatt auf den physischen Raum direkt zuzugreifen, lassen wir Anwendungen ihren Raumbedarf auf abstrakte Weise formulieren, den unsere Softwaresysteme anschließend auf den verfügbaren physischen Raum abbilden. Dadurch ermöglichen wir Real-Walking-Anwendungen Räume mit unterschiedlichen Größen und Formen und Räume, die unterschiedliche physische Objekte enthalten, zu nutzen. Wir ermöglichen auch die zeitgleiche Nutzung desselben Raums durch mehrere Nutzer verschiedener Real-Walking-Anwendungen. Unsere Systeme erreichen dieses Resultat durch eine Repräsentation von Real-Walking-Erfahrungen, die unabhängig sind vom gegebenen Trackingvolumen – eine Graphenstruktur, die die räumlichen und logischen Beziehungen zwischen virtuellen Orten, den virtuellen Elementen innerhalb dieser Orte, und Benutzerinteraktionen mit diesen Elementen, ausdrückt. Bei der Instanziierung der Anwendung in einem bestimmten physischen Raum wird diese Graphenstruktur und ein Constraint Solver verwendet, um eine individuelle Abbildung der virtuellen Elemente auf den physischen Raum zu erreichen. Zur mehrmaligen Verwendung des Raumes teilt unser System virtuelle Szenen und überlagert virtuelle Geometrie. Das System leitet diese Aufteilung anhand eines hierarchischen Clusterings unserer virtuellen Objekte ab, die als Knoten unseres bi-partiten, gerichteten Graphen die logische Reihenfolge aller Ereignisse repräsentieren. Wir verwenden präemptives Scheduling zwischen den Anwendungen für die zeitgleiche Nutzung von physischem Raum. Wir stellen mehrere Anwendungsbeispiele vor, die Real-Walking ermöglichen – in physischen Räumen mit unterschiedlicher Größe und Form, die verschiedene physische Objekte oder weitere Nutzer enthalten. Wir sehen in unseren Systemen substantielles Potential. Heutige Virtual Reality-Anwendungen sind bisher zwar so konzipiert, dass sie auf einem beliebigen Trackingvolumen betrieben werden können, aber aus kommerzieller Notwendigkeit kein Real-Walking beinhalten. Damit entgeht Entwicklern die Gelegenheit eine höhere Immersion herzustellen. Indem wir es ermöglichen, Real-Walking auf jedes Trackingvolumen zu bringen, geben wir Entwicklern die Möglichkeit Real-Walking zu ihren Nutzern zu bringen. N2 - Die eigentlichen Kosten für Virtual Reality Anwendungen entstehen nicht primär durch die erforderliche Hardware, sondern durch die Nutzung von physischem Raum, da die eins-zu-eins Abbildung von physischem auf virtuellem Raum die immersivste Art von Navigation ermöglicht. Dieses als „Real-Walking“ bezeichnete Erlebnis erfordert hinsichtlich Größe und Form eine Entsprechung von physischem Raum und virtueller Welt. Resultierend daraus können Real-Walking-Anwendungen nicht an Orten angewandt werden, für die sie nicht entwickelt wurden. Um den Bedarf an physischem Raum zu reduzieren, lassen Entwickler von Virtual Reality-Anwendungen ihre Nutzer auf verschiedene Arten navigieren, etwa mit Hilfe eines Laufbandes, verfälschten Abbildungen von physischem zu virtuellem Raum, Handheld-Controllern oder gestenbasierten Techniken. All diese Lösungen reduzieren zwar den Bedarf an physischem Raum, erreichen jedoch nicht denselben Grad an Immersion, den Real-Walking bietet. Unser Ansatz zielt darauf, physischen Raum zu virtualisieren: Anstatt auf den physischen Raum direkt zuzugreifen, lassen wir Anwendungen ihren Raumbedarf auf abstrakte Weise formulieren, den unsere Softwaresysteme anschließend auf den verfügbaren physischen Raum abbilden. Dadurch ermöglichen wir Real-Walking-Anwendungen Räume mit unterschiedlichen Größen und Formen und Räume, die unterschiedliche physische Objekte enthalten, zu nutzen. Wir ermöglichen auch die zeitgleiche Nutzung desselben Raums durch mehrere Nutzer verschiedener Real-Walking-Anwendungen. Unsere Systeme erreichen dieses Resultat durch eine Repräsentation von Real-Walking-Erfahrungen, die unabhängig sind vom gegebenen Trackingvolumen – eine Graphenstruktur, die die räumlichen und logischen Beziehungen zwischen virtuellen Orten, den virtuellen Elementen innerhalb dieser Orte, und Benutzerinteraktionen mit diesen Elementen, ausdrückt. Bei der Instanziierung der Anwendung in einem bestimmten physischen Raum wird diese Graphenstruktur und ein Constraint Solver verwendet, um eine individuelle Abbildung der virtuellen Elemente auf den physischen Raum zu erreichen. Zur mehrmaligen Verwendung des Raumes teilt unser System virtuelle Szenen und überlagert virtuelle Geometrie. Das System leitet diese Aufteilung anhand eines hierarchischen Clusterings unserer virtuellen Objekte ab, die als Knoten unseres bi-partiten, gerichteten Graphen die logische Reihenfolge aller Ereignisse repräsentieren. Wir verwenden präemptives Scheduling zwischen den Anwendungen für die zeitgleiche Nutzung von physischem Raum. Wir stellen mehrere Anwendungsbeispiele vor, die Real-Walking ermöglichen – in physischen Räumen mit unterschiedlicher Größe und Form, die verschiedene physische Objekte oder weitere Nutzer enthalten. Wir sehen in unseren Systemen substantielles Potential. Heutige Virtual Reality-Anwendungen sind bisher zwar so konzipiert, dass sie auf einem beliebigen Trackingvolumen betrieben werden können, aber aus kommerzieller Notwendigkeit kein Real-Walking beinhalten. Damit entgeht Entwicklern die Gelegenheit eine höhere Immersion herzustellen. Indem wir es ermöglichen, Real-Walking auf jedes Trackingvolumen zu bringen, geben wir Entwicklern die Möglichkeit Real-Walking zu ihren Nutzern zu bringen. KW - Human Computer Interaction KW - Mixed Reality KW - Walking KW - Real Walking KW - Motion Mapping KW - Storytelling KW - Mensch Computer Interaktion KW - Mixed Reality KW - Walking KW - Real Walking KW - Motion Mapping KW - Storytelling Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-520332 ER -