TY - JOUR A1 - Petit, Albin A1 - Cerqueus, Thomas A1 - Boutet, Antoine A1 - Ben Mokhtar, Sonia A1 - Coquil, David A1 - Brunie, Lionel A1 - Kosch, Harald T1 - SimAttack: private web search under fire JF - Journal of Internet Services and Applications N2 - Web Search engines have become an indispensable online service to retrieve content on the Internet. However, using search engines raises serious privacy issues as the latter gather large amounts of data about individuals through their search queries. Two main techniques have been proposed to privately query search engines. A first category of approaches, called unlinkability, aims at disassociating the query and the identity of its requester. A second category of approaches, called indistinguishability, aims at hiding user’s queries or user’s interests by either obfuscating user’s queries, or forging new fake queries. This paper presents a study of the level of protection offered by three popular solutions: Tor-based, TrackMeNot, and GooPIR. For this purpose, we present an efficient and scalable attack – SimAttack – leveraging a similarity metric to capture the distance between preliminary information about the users (i.e., history of query) and a new query. SimAttack de-anonymizes up to 36.7 % of queries protected by an unlinkability solution (i.e., Tor-based), and identifies up to 45.3 and 51.6 % of queries protected by indistinguishability solutions (i.e., TrackMeNot and GooPIR, respectively). In addition, SimAttack de-anonymizes 6.7 % more queries than state-of-the-art attacks and dramatically improves the performance of the attack on TrackMeNot by 23.6 %, while retaining an execution time faster by two orders of magnitude. KW - Privacy KW - Web search KW - Unlinkability KW - Indistinguishability Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-3574 SN - 1869-0238 PB - SpringerOpen ER - TY - THES A1 - Stegmaier, Florian T1 - Unified Retrieval in Distributed and Heterogeneous Multimedia Information Systems T1 - Vereinheitlichte Anfrageverarbeitung in heterogenen und verteilten Multimediadatenbanken N2 - Multimedia retrieval is an essential part of today's world. This situation is observable in industrial domains, e.g., medical imaging, as well as in the private sector, visible by activities in manifold Social Media platforms. This trend led to the creation of a huge environment of multimedia information retrieval services offering multimedia resources for almost any user requests. Indeed, the encompassed data is in general retrievable by (proprietary) APIs and query languages, but unfortunately a unified access is not given due to arising interoperability issues between those services. In this regard, this thesis focuses on two application scenarios, namely a medical retrieval system supporting a radiologist's workflow, as well as an interoperable image retrieval service interconnecting diverse data silos. The scientific contribution of this dissertation is split in three different parts: the first part of this thesis improves the metadata interoperability issue. Here, major contributions to a community-driven, international standardization have been proposed leading to the specification of an API and ontology to enable a unified annotation and retrieval of media resources. The second part issues a metasearch engine especially designed for unified retrieval in distributed and heterogeneous multimedia retrieval environments. This metasearch engine is capable of being operated in a federated as well as autonomous manner inside the aforementioned application scenarios. The remaining third part ensures an efficient retrieval due to the integration of optimization techniques for multimedia retrieval in the overall query execution process of the metasearch engine. N2 - Egal ob im industriellen Bereich oder auch im Social Media - multimediale Daten nehmen eine immer zentralere Rolle ein. Aus diesem fortlaufendem Entwicklungsprozess entwickelten sich umfangreiche Informationssysteme, die Daten für zahlreiche Bedürfnisse anbieten. Allerdings ist ein einheitlicher Zugriff auf jene verteilte und heterogene Landschaft von Informationssystemen in der Praxis nicht gewährleistet. Und dies, obwohl die Datenbestände meist über Schnittstellen abrufbar sind. Im Detail widmet sich diese Arbeit mit der Bearbeitung zweier Anwendungsszenarien. Erstens, einem medizinischen System zur Diagnoseunterstützung und zweitens einer interoperablen, verteilten Bildersuche. Der wissenschaftliche Teil der vorliegenden Dissertation gliedert sich in drei Teile: Teil eins befasst sich mit dem Problem der Interoperabilität zwischen verschiedenen Metadatenformaten. In diesem Bereich wurden maßgebliche Beiträge für ein internationales Standardisierungsverfahren entwickelt. Ziel war es, einer Ontologie, sowie einer Programmierschnittstelle einen vereinheitlichten Zugriff auf multimediale Informationen zu ermöglichen. In Teil zwei wird eine externe Metasuchmaschine vorgestellt, die eine einheitliche Anfrageverarbeitung in heterogenen und verteilten Multimediadatenbanken ermöglicht. In den Anwendungsszenarien wird zum einen auf eine föderative, als auch autonome Anfrageverarbeitung eingegangen. Abschließend werden in Teil drei Techniken zur Optimierung von verteilten multimedialen Anfragen präsentiert. KW - Distributed multimedia retrieval KW - query optimization KW - multimedia annotation KW - interoperability KW - Abfrage KW - Information Retrieval KW - Interoperabilität KW - Metasuchmaschine KW - Verteiltes Datenbanksystem KW - Bildgebendes Verfahren Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27317 ER - TY - THES A1 - EL-Khoury, Vanessa T1 - Semantic Protection and Personalization of Video Content. PIAF: MPEG Compliant Adaptation Framework Preserving the User Perceived Quality T1 - Semantischer Schutz und Personalisierung von Videoinhalten. PIAF: MPEG-kompatibles Multimedia-Adaptierungs-Framework zur Bewahrung der vom Nutzer wahrgenommenen Qualität. N2 - UME is the notion that a user should receive informative adapted content anytime and anywhere. Personalization of videos, which adapts their content according to user preferences, is a vital aspect of achieving the UME vision. User preferences can be translated into several types of constraints that must be considered by the adaptation process, including semantic constraints directly related to the content of the video. To deal with these semantic constraints, a fine-grained adaptation, which can go down to the level of video objects, is necessary. The overall goal of this adaptation process is to provide users with adapted content that maximizes their Quality of Experience (QoE). This QoE depends at the same time on the level of the user's satisfaction in perceiving the adapted content, the amount of knowledge assimilated by the user, and the adaptation execution time. In video adaptation frameworks, the Adaptation Decision Taking Engine (ADTE), which can be considered as the "brain" of the adaptation engine, is responsible for achieving this goal. The task of the ADTE is challenging as many adaptation operations can satisfy the same semantic constraint, and thus arising in several feasible adaptation plans. Indeed, for each entity undergoing the adaptation process, the ADTE must decide on the adequate adaptation operator that satisfies the user's preferences while maximizing his/her quality of experience. The first challenge to achieve in this is to objectively measure the quality of the adapted video, taking into consideration the multiple aspects of the QoE. The second challenge is to assess beforehand this quality in order to choose the most appropriate adaptation plan among all possible plans. The third challenge is to resolve conflicting or overlapping semantic constraints, in particular conflicts arising from constraints expressed by owner's intellectual property rights about the modification of the content. In this thesis, we tackled the aforementioned challenges by proposing a Utility Function (UF), which integrates semantic concerns with user's perceptual considerations. This UF models the relationships among adaptation operations, user preferences, and the quality of the video content. We integrated this UF into an ADTE. This ADTE performs a multi-level piecewise reasoning to choose the adaptation plan that maximizes the user-perceived quality. Furthermore, we included intellectual property rights in the adaptation process. Thereby, we modeled content owner constraints. We dealt with the problem of conflicting user and owner constraints by mapping it to a known optimization problem. Moreover, we developed the SVCAT, which produces structural and high-level semantic annotation according to an original object-based video content model. We modeled as well the user's preferences proposing extensions to MPEG-7 and MPEG-21. All the developed contributions were carried out as part of a coherent framework called PIAF. PIAF is a complete modular MPEG standard compliant framework that covers the whole process of semantic video adaptation. We validated this research with qualitative and quantitative evaluations, which assess the performance and the efficiency of the proposed adaptation decision-taking engine within PIAF. The experimental results show that the proposed UF has a high correlation with subjective video quality evaluation. N2 - Der Begriff "Universal Multimedia Experience" (UME) beschreibt die Vision, dass ein Nutzer nach seinen individuellen Vorlieben zugeschnittene Videoinhalte konsumieren kann. In dieser Dissertation werden im UME nun auch semantische Constraints berücksichtigt, welche direkt mit der Konsumierung der Videoinhalte verbunden sind. Dabei soll die Qualität der Videoerfahrung für den Nutzer maximiert werden. Diese Qualität ist in der Dissertation durch die Benutzerzufriedenheit bei der Wahrnehmung der Veränderung der Videos repräsentiert. Die Veränderung der Videos wird durch eine Videoadaptierung erzeugt, z.B. durch die Löschung oder Veränderung von Szenen, Objekten, welche einem semantischen Constraints nicht entsprechen. Kern der Videoadaptierung ist die "Adaptation Decision Taking Engine" (ADTE). Sie bestimmt die Operatoren, welche die semantischen Constraints auflösen, und berechnet dann mögliche Adaptierungspläne, die auf dem Video angewandt werden sollen. Weiterhin muss die ADTE für jeden Adaptierungsschritt anhand der Operatoren bestimmen, wie die Vorlieben des Nutzers berücksichtigt werden können. Die zweite Herausforderung ist die Beurteilung und Maximierung der Qualität eines adaptierten Videos. Die dritte Herausforderung ist die Berücksichtigung sich widersprechender semantischer Constraints. Dies betrifft insbesondere solche, die mit Urheberrechten in Verbindung stehen. In dieser Dissertation werden die oben genannten Herausforderungen mit Hilfe eines "Personalized video Adaptation Framework" (PIAF) gelöst, welche auf den "Moving Picture Expert Group" (MPEG)-Standard MPEG-7 und MPEG-21 basieren. PIAF ist ein Framework, welches den gesamten Prozess der Videoadaptierung umfasst. Es modelliert den Zusammenhang zwischen den Adaptierungsoperatoren, den Vorlieben der Nutzer und der Qualität der Videos. Weiterhin wird das Problem der optimalen Auswahl eines Adaptierungsplans für die maximale Qualität der Videos untersucht. Dafür wird eine Utility Funktion (UF) definiert und in der ADTE eingesetzt, welche die semantischen Constraints mit den vom Nutzer ausgedrückten Vorlieben vereint. Weiterhin ist das "Semantic Video Content Annotation Tool" (SVCAT) entwickelt worden, um strukturelle und semantische Annotationen durchzuführen. Ebenso sind die Vorlieben der Nutzer mit MPEG-7 und MPEG-21 Deskriptoren berücksichtigt worden. Die Entwicklung dieser Software-Werkzeuge und Algorithmen ist notwendig, um ein vollständiges und modulares Framework zu erhalten. Dadurch deckt PIAF den kompletten Bereich der semantischen Videoadaptierung ab. Das ADTE ist in qualitativen und quantitativen Evaluationen validiert worden. Die Ergebnisse der Evaluation zeigen unter anderem, dass die UF im Bereich Qualität eine hohe Korrelation mit der subjektiven Wahrnehmung von ausgewählten Nutzern aufweist. KW - MPEG-Standard KW - Multimedia KW - Wahrnehmung KW - Personalisierung von Videos KW - semantische Adaptierung KW - Inhaltsadaptierung KW - Quality of Experience KW - Universal Multimedia Experience KW - Personalization of Videos KW - Semantic Content Adaptation KW - Quality of Experience KW - User Perception KW - Utility Functon Model Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27360 ER - TY - THES A1 - Mousselly Sergieh, Hatem T1 - Search-based Automatic Image Annotation Using Geotagged Community Photos T1 - Suchbasierte automatische Bildannotation anhand geokodierter Community-Fotos N2 - In the Web 2.0 era, platforms for sharing and collaboratively annotating images with keywords, called tags, became very popular. Tags are a powerful means for organizing and retrieving photos. However, manual tagging is time consuming. Recently, the sheer amount of user-tagged photos available on the Web encouraged researchers to explore new techniques for automatic image annotation. The idea is to annotate an unlabeled image by propagating the labels of community photos that are visually similar to it. Most recently, an ever increasing amount of community photos is also associated with location information, i.e., geotagged. In this thesis, we aim at exploiting the location context and propose an approach for automatically annotating geotagged photos. Our objective is to address the main limitations of state-of-the-art approaches in terms of the quality of the produced tags and the speed of the complete annotation process. To achieve these goals, we, first, deal with the problem of collecting images with the associated metadata from online repositories. Accordingly, we introduce a strategy for data crawling that takes advantage of location information and the social relationships among the contributors of the photos. To improve the quality of the collected user-tags, we present a method for resolving their ambiguity based on tag relatedness information. In this respect, we propose an approach for representing tags as probability distributions based on the algorithm of Laplacian score feature selection. Furthermore, we propose a new metric for calculating the distance between tag probability distributions by extending Jensen-Shannon Divergence to account for statistical fluctuations. To efficiently identify the visual neighbors, the thesis introduces two extensions to the state-of-the-art image matching algorithm, known as Speeded Up Robust Features (SURF). To speed up the matching, we present a solution for reducing the number of compared SURF descriptors based on classification techniques, while the accuracy of SURF is improved through an efficient method for iterative image matching. Furthermore, we propose a statistical model for ranking the mined annotations according to their relevance to the target image. This is achieved by combining multi-modal information in a statistical framework based on Bayes' rule. Finally, the effectiveness of each of mentioned contributions as well as the complete automatic annotation process are evaluated experimentally. N2 - Seit der Einführung von Web 2.0 steigt die Popularität von Plattformen, auf denen Bilder geteilt und durch die Gemeinschaft mit Schlagwörtern, sogenannten Tags, annotiert werden. Mit Tags lassen sich Fotos leichter organisieren und auffinden. Manuelles Taggen ist allerdings sehr zeitintensiv. Animiert von der schieren Menge an im Web zugänglichen, von Usern getaggten Fotos, erforschen Wissenschaftler derzeit neue Techniken der automatischen Bildannotation. Dahinter steht die Idee, ein noch nicht beschriftetes Bild auf der Grundlage visuell ähnlicher, bereits beschrifteter Community-Fotos zu annotieren. Unlängst wurde eine immer größere Menge an Community-Fotos mit geographischen Koordinaten versehen (geottagged). Die Arbeit macht sich diesen geographischen Kontext zunutze und präsentiert einen Ansatz zur automatischen Annotation geogetaggter Fotos. Ziel ist es, die wesentlichen Grenzen der bisher bekannten Ansätze in Hinsicht auf die Qualität der produzierten Tags und die Geschwindigkeit des gesamten Annotationsprozesses aufzuzeigen. Um dieses Ziel zu erreichen, wurden zunächst Bilder mit entsprechenden Metadaten aus den Online-Quellen gesammelt. Darauf basierend, wird eine Strategie zur Datensammlung eingeführt, die sich sowohl der geographischen Informationen als auch der sozialen Verbindungen zwischen denjenigen, die die Fotos zur Verfügung stellen, bedient. Um die Qualität der gesammelten User-Tags zu verbessern, wird eine Methode zur Auflösung ihrer Ambiguität vorgestellt, die auf der Information der Tag-Ähnlichkeiten basiert. In diesem Zusammenhang wird ein Ansatz zur Darstellung von Tags als Wahrscheinlichkeitsverteilungen vorgeschlagen, der auf den Algorithmus der sogenannten Laplacian Score (LS) aufbaut. Des Weiteren wird eine Erweiterung der Jensen-Shannon-Divergence (JSD) vorgestellt, die statistische Fluktuationen berücksichtigt. Zur effizienten Identifikation der visuellen Nachbarn werden in der Arbeit zwei Erweiterungen des Speeded Up Robust Features (SURF)-Algorithmus vorgestellt. Zur Beschleunigung des Abgleichs wird eine Lösung auf der Basis von Klassifikationstechniken präsentiert, die die Anzahl der miteinander verglichenen SURF-Deskriptoren minimiert, während die SURF-Genauigkeit durch eine effiziente Methode des schrittweisen Bildabgleichs verbessert wird. Des Weiteren wird ein statistisches Modell basierend auf der Baye'schen Regel vorgeschlagen, um die erlangten Annotationen entsprechend ihrer Relevanz in Bezug auf das Zielbild zu ranken. Schließlich wird die Effizienz jedes einzelnen, erwähnten Beitrags experimentell evaluiert. Darüber hinaus wird die Performanz des vorgeschlagenen automatischen Annotationsansatzes durch umfassende experimentelle Studien als Ganzes demonstriert. KW - Social Tagging KW - Flickr KW - Annotation KW - Image Annotation KW - Flickr KW - Social Tagging KW - Jensen-Shannon Divergence KW - Folksonomy Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27387 ER - TY - THES A1 - Auer, Christopher T1 - Planar Graphs and their Duals on Cylinder Surfaces T1 - Planare Graphen und ihre Dualgraphen auf Zylinderoberflächen N2 - In this thesis, we investigates plane drawings of undirected and directed graphs on cylinder surfaces. In the case of undirected graphs, the vertices are positioned on a line that is parallel to the cylinder’s axis and the edge curves must not intersect this line. We show that a plane drawing is possible if and only if the graph is a double-ended queue (deque) graph, i. e., the vertices of the graph can be processed according to a linear order and the edges correspond to items in the deque inserted and removed at their end vertices. A surprising consequence resulting from these observations is that the deque characterizes planar graphs with a Hamiltonian path. This result extends the known characterization of planar graphs with a Hamiltonian cycle by two stacks. By these insights, we also obtain a new characterization of queue graphs and their duals. We also consider the complexity of deciding whether a graph is a deque graph and prove that it is NP-complete. By introducing a split operation, we obtain the splittable deque and show that it characterizes planarity. For the proof, we devise an algorithm that uses the splittable deque to test whether a rotation system is planar. In the case of directed graphs, we study upward plane drawings where the edge curves follow the direction of the cylinder’s axis (standing upward planarity; SUP) or they wind around the axis (rolling upward planarity; RUP). We characterize RUP graphs by means of their duals and show that RUP and SUP swap their roles when considering a graph and its dual. There is a physical interpretation underlying this characterization: A SUP graph is to its RUP dual graph as electric current passing through a conductor to the magnetic field surrounding the conductor. Whereas testing whether a graph is RUP is NP-hard in general [Bra14], for directed graphs without sources and sink, we develop a linear-time recognition algorithm that is based on our dual graph characterization of RUP graphs. N2 - Die Arbeit beschäftigt sich mit planaren Zeichnungen ungerichteter und gerichteter Graphen auf Zylinderoberflächen. Im ungerichteten Fall werden Zeichnungen betrachtet, bei denen die Knoten auf einer Linie parallel zur Zylinderachse positioniert werden und die Kanten diese Linie nicht schneiden dürfen. Es kann gezeigt werden, dass eine planare Zeichnung genau dann möglich ist, wenn die Kanten des Graphen in einer double-ended queue (Deque) verarbeitet werden können. Ebenso lassen sich dadurch Queue, Stack und Doppelstack charakterisieren. Eine überraschende Konsequenz aus diesen Erkenntnissen ist, dass die Deque genau die planaren Graphen mit Hamiltonpfad charakterisiert. Dies erweitert die bereits bekannte Charakterisierung planarer Graphen mit Hamiltonkreis durch den Doppelstack. Im gerichteten Fall müssen die Kantenkurven entweder in Richtung der Zylinderachse verlaufen (SUP-Graphen) oder sich um die Achse herumbewegen (RUP-Graphen). Die Arbeit charakterisiert RUP-Graphen und zeigt, dass RUP und SUP ihre Rollen tauschen, wenn man Graph und Dualgraph betrachtet. Der SUP-Graph verhält sich dabei zum RUP-Graphen wie elektrischer Strom durch einen Leiter zum induzierten Magnetfeld. Ausgehend von dieser Charakterisierung ist es möglich einen Linearzeit-Algorithmus zu entwickeln, der entscheidet ob ein gerichteter Graph ohne Quellen und Senken ein RUP-Graph ist, während der allgemeine Fall NP-hart ist [Bra14]. KW - Planarer Graph KW - Azyklischer gerichteter Graph KW - Dualer Graph KW - Graphentheorie KW - Graph KW - Graphenzeichnen KW - SPQR-Baum KW - Warteschlange KW - Zylinder KW - zyklische darstellung KW - radiale darstellung KW - cylinder KW - graph drawing KW - radial drawing KW - cyclic drawing KW - deque layout Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27430 ER - TY - THES A1 - Meixner, Britta T1 - Annotated Interactive Non-linear Video - Software Suite, Download and Cache Management T1 - Annotierte interaktive nichtlineare Videos - Software Suite, Download- und Cache-Management N2 - Modern Web technology makes the dream of fully interactive and enriched video come true. Nowadays it is possible to organize videos in a non-linear way playing in a sequence unknown in advance. Furthermore, additional information can be added to the video, ranging from short descriptions to animated images and further videos. This affords an easy and efficient to use authoring tool which is capable of the management of the single media objects, as well as a clear arrangement of the links between the parts. Tools of this kind can be found rarely and do mostly not provide the full range of needed functions. While providing an interactive experience to the viewer in the Web player, parallel plot sequences and additional information lead to an increased download volume. This may cause pauses during playback while elements have to be downloaded which are displayed with the video. A good quality of experience for these videos with small waiting times and a playback without interruptions is desired. This work presents the SIVA Suite to create the previously described annotated interactive non-linear videos. We propose a video model for interactivity, non-linearity, and annotations, which is implemented in an XML format, an authoring tool, and a player. Video is the main medium, whereby different scenes are linked to a scene graph. Time controlled additional content called annotations, like text, images, audio files, or videos, is added to the scenes. The user is able to navigate in the scene graph by selecting a button at a button panel. Furthermore, other navigational elements like a table of contents or a keyword search are provided. Besides the SIVA Suite, this thesis presents algorithms and strategies for download and cache management to provide a good quality of experience while watching the annotated interactive non-linear videos. Therefor, we implemented a standard-independent player framework. Integrated into a simulation environment, the framework allows to evaluate algorithms and strategies for the calculation of start-up times, and the selection of elements to pre-fetch into and delete from the cache. Their interaction during the playback of non-linear video contents can be analyzed. The algorithms and strategies can be used to minimize interruptions in the video flow after user interactions. Our extensive evaluation showed that our techniques result in faster start-up times and lesser interruptions in the video flow than those of other players. Knowledge of the structure of an interactive non-linear video can be used to minimize the start-up time at the beginning of a video while minimizing an increase in the overall download volume. N2 - Moderne Web-Technologien lassen den Traum von voll interaktiven und bereicherten Videos wahr werden. Heutzutage ist es möglich, Videos in nicht-linearer Art und Weise zu organisieren, welche dann in einer vorher unbekannten Reihenfolge abgespielt werden können. Weiterhin können den Videos Zusatzinformationen in Form von kurzen Beschreibungen über animierte Bilder bis hin zu weiteren Videos hinzugefügt werden. Dies erfordert ein einfach und effizient zu bedienendes Autorenwerkzeug, das in der Lage ist, sowohl einzelne Medien-Objekte zu verwalten, als auch die Verbindungen zwischen den einzelnen Teilen klar darzustellen. Tools dieser Art sind selten und bieten meist nicht den vollen benötigten Funktionsumfang. Während dem Betrachter dieses interaktive Erlebnis im Web Player zur Verfügung gestellt wird, führen parallele Handlungsstränge und zusätzliche Inhalte zu einem erhöhten Download-Volumen. Dies kann zu Pausen während der Wiedergabe führen, in denen Elemente vom Server geladen werden müssen, welche mit dem Video angezeigt werden sollen. Ein gutes Benutzungserlebnis für solche Videos kann durch geringe Wartezeiten und eine unterbrechungsfreie Wiedergabe erreicht werden. Diese Arbeit stellt die SIVA Suite vor, mit der die zuvor beschriebenen annotierten interaktiven nicht-linearen Videos erstellt werden können. Wir bilden Interaktivität, Nichtlinearität und Annotationen in einem Video-Model ab. Dieses wird in unserem XML-Format, Autorentool und Player umgesetzt. Als Leitmedium werden hierbei Videos verwendet, welche aufgeteilt in Szenen zu einer Graphstruktur zusammengefügt werden können. Zeitlich gesteuerte zusätzliche Inhalte, sogenannte Annotationen, wie Texte, Bilder, Audio-Dateien und Videos, werden den Szenen hinzugefügt. Der Betrachter kann im Szenengraph navigieren, indem er in einem bereitgestellten Button-Panel eine Nachfolgeszene auswählt. Andere Navigationselemente sind ein Inhaltsverzeichnis sowie eine Suchfunktion. Neben der SIVA Suite beschreibt diese Arbeit Algorithmen und Strategien für Download und Cache Management, um eine gute Nutzungserfahrung während der Betrachtung der annotierten interaktiven nicht-linearen Videos zu bieten. Ein Webstandard-unabhängiges Playerframework erlaubt es, das Zusammenspiel von Algorithmen und Strategien zu evaluieren, welche für die Berechnung der Start-Zeitpunkte für die Wiedergabe, sowie die Auswahl von vorauszuladenden sowie zu löschenden Elemente verwendet werden. Ziel ist es, Unterbrechungen zu minimieren, wenn der Ablauf des Videos durch Benutzerinteraktion beeinflusst wird. Unsere umfassende Evaluation zeigte, dass es möglich ist, kürzere Startup-Zeiten und weniger Unterbrechungen mit unseren Strategien zu erreichen, als bei der Verwendung der Strategien anderer Player. Die Kenntnis der Struktur des interaktiven nicht-linearen Videos kann dazu verwendet werden, die Startzeit am Anfang der Szenen zu minimieren, während das Download-Volumen nicht erhöht wird. KW - Interaktivität KW - Nichtlinearität KW - Hypervideo KW - Cache Management KW - Download Managment KW - Interactivity KW - Non-linearity KW - Hypervideo KW - Cache Management KW - Download Managment KW - Nichtlineares Phänomen KW - Hypervideo Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27403 ER - TY - THES A1 - Wüchner, Patrick T1 - Energy-Efficient and Timely Event Reporting Using Wireless Sensor Networks T1 - Energieeffiziente und rechtzeitige Ereignismeldung mittels drahtloser Sensornetze N2 - This thesis investigates the suitability of state-of-the-art protocols for large-scale and long-term environmental event monitoring using wireless sensor networks based on the application scenario of early forest fire detection. By suitable combination of energy-efficient protocol mechanisms a novel communication protocol, referred to as cross-layer message-merging protocol (XLMMP), is developed. Qualitative and quantitative protocol analyses are carried out to confirm that XLMMP is particularly suitable for this application area. The quantitative analysis is mainly based on finite-source retrial queues with multiple unreliable servers. While this queueing model is widely applicable in various research areas even beyond communication networks, this thesis is the first to determine the distribution of the response time in this model. The model evaluation is mainly carried out using Markovian analysis and the method of phases. The obtained quantitative results show that XLMMP is a feasible basis to design scalable wireless sensor networks that (1) may comprise hundreds of thousands of tiny sensor nodes with reduced node complexity, (2) are suitable to monitor an area of tens of square kilometers, (3) achieve a lifetime of several years. The deduced quantifiable relationships between key network parameters — e.g., node size, node density, size of the monitored area, aspired lifetime, and the maximum end-to-end communication delay — enable application-specific optimization of the protocol. KW - Drahtloses Sensorsystem KW - Netzwerk KW - Elektronische Kommunikation KW - Protokoll KW - Kommunikationsprotokoll KW - Markov-Kette KW - Wireless sensor network KW - Energy efficiency KW - Communication protocol KW - Mathematical modeling KW - Continuous-time Markov chain KW - Finite-source retrial queue Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27159 ER - TY - THES A1 - Limbeck, Jan T1 - Computation of Approximate Border Bases and Applications T1 - Berechnung und Anwendungen Approximativer Randbasen N2 - This thesis addresses some of the algorithmic and numerical challenges associated with the computation of approximate border bases, a generalisation of border bases, in the context of the oil and gas industry. The concept of approximate border bases was introduced by D. Heldt, M. Kreuzer, S. Pokutta and H. Poulisse in "Approximate computation of zero-dimensional polynomial ideals" as an effective mean to derive physically relevant polynomial models from measured data. The main advantages of this approach compared to alternative techniques currently in use in the (hydrocarbon) industry are its power to derive polynomial models without additional a priori knowledge about the underlying physical system and its robustness with respect to noise in the measured input data. The so-called Approximate Vanishing Ideal (AVI) algorithm which can be used to compute approximate border bases and which was also introduced by D. Heldt et al. in the paper mentioned above served as a starting point for the research which is conducted in this thesis. A central aim of this work is to broaden the applicability of the AVI algorithm to additional areas in the oil and gas industry, like seismic imaging and the compact representation of unconventional geological structures. For this purpose several new algorithms are developed, among others the so-called Approximate Buchberger Möller (ABM) algorithm and the Extended-ABM algorithm. The numerical aspects and the runtime of the methods are analysed in detail - based on a solid foundation of the underlying mathematical and algorithmic concepts that are also provided in this thesis. It is shown that the worst case runtime of the ABM algorithm is cubic in the number of input points, which is a significant improvement over the biquadratic worst case runtime of the AVI algorithm. Furthermore, we show that the ABM algorithm allows us to exercise more direct control over the essential properties of the computed approximate border basis than the AVI algorithm. The improved runtime and the additional control turn out to be the key enablers for the new industrial applications that are proposed here. As a conclusion to the work on the computation of approximate border bases, a detailed comparison between the approach in this thesis and some other state of the art algorithms is given. Furthermore, this work also addresses one important shortcoming of approximate border bases, namely that central concepts from exact algebra such as syzygies could so far not be translated to the setting of approximate border bases. One way to mitigate this problem is to construct a "close by" exact border bases for a given approximate one. Here we present and discuss two new algorithmic approaches that allow us to compute such close by exact border bases. In the first one, we establish a link between this task, referred to as the rational recovery problem, and the problem of simultaneously quasi-diagonalising a set of complex matrices. As simultaneous quasi-diagonalisation is not a standard topic in numerical linear algebra there are hardly any off-the-shelf algorithms and implementations available that are both fast and numerically adequate for our purposes. To bridge this gap we introduce and study a new algorithm that is based on a variant of the classical Jacobi eigenvalue algorithm, which also works for non-symmetric matrices. As a second solution of the rational recovery problem, we motivate and discuss how to compute a close by exact border basis via the minimisation of a sum of squares expression, that is formed from the polynomials in the given approximate border basis. Finally, several applications of the newly developed algorithms are presented. Those include production modelling of oil and gas fields, reconstruction of the subsurface velocities for simple subsurface geometries, the compact representation of unconventional oil and gas bodies via algebraic surfaces and the stable numerical approximation of the roots of zero-dimensional polynomial ideals. KW - Computeralgebra KW - Numerische Mathematik KW - Erdöl KW - Diagonalisierung KW - Modellierung KW - Simultane Quasi-Diagonalisierung KW - Approximative Randbasen KW - Öl und Gas Industrie KW - Data Driven Modelling KW - Buchberger-Möller Algorithmus KW - simultaneous quasi-diagonalization KW - approximate border bases KW - oil and gas industry KW - data driven modelling KW - Buchberger-Moeller algorithm Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27197 ER - TY - THES A1 - Mayer, Tobias Rene T1 - Achieving Collaboration In Distributed Systems Deployed Over Selfish Peers - An Illustrative Case Study With Publish/Subscribe T1 - Erreichen der Kooperation von egoistischen Peers in in verteilten Systemen - Eine Studie mit Publish/Subscribe N2 - Up to a few years ago, the typical operation of a distributed architecture was modelled as the enactment of a collaborative protocol by networked nodes. In this context, all nodes were under the system designer’s control, faithfully executing the programmed behaviour. However, today’s networks are often characterized by a free aggregation of nodes. Thus, the possibility increases that a selfish party operates a node, which may violate the collaborative protocol in order to increase a personal benefit. If such violations differ from the system goals they can even be considered as attack. Current fault-tolerance techniques may weaken the harmful impact to some degree but they cannot necessarily prevent them. Furthermore, the several architectures differ in their fault-tolerance capabilities. This emphasizes the need for a systematic approach to achieve collaboration in distributed systems. In this PhD thesis we consider the problem of attaining a targeted level of collaboration in a distributed architecture deployed over rational selfish-driven nodes, which have interest in deviating from the communication protocol to increase a personal benefit. In order to reach this goal and to cover a broad spectrum of systems, we do not modify the architecture or communication protocol itself. Instead, we add a monitoring logic to inspect a node’s behaviour in terms of the correct interaction with the system. With this approach, the system designer needs to contrast several aspects such as the specific environmental circumstances, the inspection effort or the node’s individual preferences. Furthermore, he should consider the fact that each agent could be aware of the other agents’ preferences and selfishness, and perform strategic choices consequently. The natural frame for modelling such complex, interdependent and possibly interactive decision landscape is Game Theory (GT). In this context, the monitoring setup proposed in this thesis corresponds to a class of GT models known as Inspection Games (IG). Such games were introduced 1962 in their simplest formulation by Dresher in the context of non-proliferation treatises and arm control. They model the general situation where one inspector verifies through inspections the correct behaviour of another party, called inspectee. However, inspections are costly and the inspector’s resources are limited. Hence, a complete surveillance is not possible and an inspector will try to minimize the inspections. Finally, a game strategy combination (violating/inspecting or not) that is considered optimal by the parties represents a Nash equilibrium for the game. In this thesis, the initial IG model is enriched by the possibility of false negatives, i.e. the probability that a violation is not detected during an inspection. Both the initial and the enriched model remain abstract and can thus easily find interdisciplinary application. However, as solution approach in this thesis considering the context of distributed systems, it models the network participants’ strategy choice. As outcome, the IG model enables to calculate system parameters in order to shift the Nash equilibrium to the desired target collaboration. The approach is designed as framework. It can be therefore applied to any architecture considering, any selfish goal and any reliability technique. For sake of concreteness, we will discuss the IG approach by means of the illustrative case of a Publish/Subscribe (pub/sub) architecture. In this way messages over the communication infrastructure will have a specific associated semantics. The Inspection Game approach of this thesis secures the whole collaborative protocol in order to attain a correctly working system up to a specific degree (in the sense of collaboration). This represents a completely new way in terms of reliability mechanisms. Hence, this thesis can be considered as fundamental research. In order to enable a broad application, the generality of this approach is supported by further contributions. This is among others the software library RCourse for practical robustness evaluations of overlay networks and a simulation environment for further research of the abstract IG model. All developments will finally be published as open source software. N2 - Bis vor ein paar Jahren konnten verteilte Systeme durch die Anwendung eines gemeinsamen kollaborativen Protokolls realisiert werden. Die Netzwerkknoten (Software/Hardware eines Systemteilnehmers) standen unter der vollständigen Kontrolle eines Systemadministrators. Heutige Netzwerke wie z.B. Peer-to-Peer (P2P) Systeme bilden sich jedoch häufig aus einem dynamischen und freien Zusammenschluss von Netzwerkteilnehmern. Dabei steigt die Wahrscheinlichkeit deutlich, dass ein Knoten von egoistischen Individuen betrieben wird, welche bewusst das Protokoll verletzen um ein persönliches Ziel zu verfolgen. Ein Beispiel ist die Verringerung des eigenen Ressourcen-Verbrauchs durch die Nicht-Weiterleitung von Nachrichten anderer Netzwerkteilnehmer. Ein solches Verhalten kann nicht nur als schädlich sondern auch als Angriff betrachtet werden. Die Fehlertoleranz aktueller Systeme kann die negativen Auswirkungen abschwächen jedoch nicht vollständig verhindern. Weiterhin unterscheiden sich die Systeme in diesem Punkt zum Teil dramatisch. Dies verdeutlicht den Bedarf von Systemen, die aktiv eine Befolgung kollaborativen Protokolls aufrechterhalten und damit die korrekte Funktion eines verteilten Systems. In dieser Dissertation betrachten wir daher das Problem ein bestimmtes Kollaborationsniveau in einem verteilten System zu erreichen, in dem egoistische Knoten agieren. Für eine möglichst hohe Anwendbarkeit wird dazu weder die Architektur noch das kollaborative Protokoll selbst verändert. Stattdessen überwacht ein Monitoring-Ansatz das Verhalten der einzelnen Netzwerkteilnehmer und induziert bei Bedarf Kooperationsanreize. Aufgrund begrenzter Ressourcen erfolgt dies nicht für alle Operationen sondern nur stichprobenartig in Form von Inspektionen. Mit dem Monitoring-Ansatz muss ein Systemdesigner diverse Aspekte abwägen wie zum Beispiel den aktuellen Systemzustand, Inspektionsaufwand oder individuelle Ziele eines egoistischen Knotens. Dies führt zu einer komplexen, gegenseitigen und möglicherweise interaktiven Entscheidungslandschaft für die Monitoring-Logik und Knoten. Ein typisches Werkzeug zur Modellierung solcher Situationen ist Spieltheorie. In der Tat entspricht der Monitoring-Ansatz einer Klasse der Spieltheorie, Inspection Games (IG), erstmals vorgestellt 1962 von Dresher im Kontext der Einhaltung von Rüstungsabkommen durch Inspektionen an Grenzposten. IGs modellieren die generelle Situation wo ein inspector durch Inspektionen das korrekte Verhalten eines anderen Individuums, dem inspectee, überprüft, welches vom vorgegebenen Protokoll abweichen möchte um einen individuellen Nutzen zu erhöhen. Inspektionen sind jedoch aufwändig; der Inspektor versucht daher dessen Anzahl zu reduzieren. Eine für die Individuen optimale Strategiekombination (Abweichen bzw. Inspizieren oder nicht) repräsentiert schließlich das Nash Equilibrium. In der Dissertation wurde der IG Ansatz als Lösungsvorschlag für das gegebene Problem auf verteilte Systeme adaptiert. Dazu wurde der initiale IG Modell zunächst durch false negatives erweitert, d.h. die Möglichkeit, dass Protokollverstöße während einer Inspektion nicht entdeckt werden. Es wurden weiterhin Generalisierungen für mehrere Individuen sowie deren Lösungen (Nash Equilibria) erarbeitet um als Basis für weitere (auch interdisziplinäre) Arbeiten zu dienen. Bei der konkreten Adaption auf verteilte Systeme erlaubt der IG Ansatz die Modellierung des Kollaborationsverhaltens, d.h. die Strategiewahl der einzelnen Individuen (Protokollverletzung bzw. Inspektion oder nicht). Als Ergebnis ermöglicht der IG Ansatz die Berechnung von Systemparametern um das Nash Equilibrium zur einer Strategiekombination zu verschieben die dem anvisierten Kooperationsniveau entspricht. Der gesamte Ansatz ist als Framework konzipiert. Er kann daher individuellen Bedürfnissen angepasst werden; dies umfasst insbesondere die Systemarchitektur, das individuelle Ziel und verwendete Techniken. Die gesamte Thematik wird in der Dissertation anhand eines konkreten Anwendungsbeispiels mit Publish/Subscribe Systemen diskutiert. Der Inspection Game Ansatz der Dissertation hat das Ziel der Absicherung des gesamten Kollaborations-protokolls selbst. Dies ist ein vollständig neues Konzept zum Erreichen der Zuverlässigkeit und der korrekten Funktion eines verteilten Systems (im Sinne der Kollaboration). Es kann daher als Grundlagenforschung betrachtet werden und erlaubt eine Vielzahl fortführender Forschungsarbeiten. Diese werden durch weitere Beiträge der Dissertation sollen unterstützt. Beispiele sind unter anderem die Softwarebibliothek RCourse für simulative Evaluierungen der Robustheit von verteilten Systemen sowie eine Simulationsumgebung für Untersuchungen des IG Modells. Alle Entwicklungen werden weiterhin als Open Source Software veröffentlicht. KW - Zuverlässigkeit KW - Verfügbarkeit KW - Sicherheit KW - Netzwerkverwaltung KW - Netzwerkanalyse KW - Modellierung KW - Spieltheorie KW - Inspection Games KW - reliability KW - modeling of distributed systems KW - game theory KW - inspection games Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27118 ER - TY - THES A1 - Schönberg, Christian T1 - Semantic Processing of Digital Documents T1 - Semantische Verarbeitung von digitalen Dokumenten N2 - Precise, content-rich and well-structured document models are required for applications like verifying the consistency of documents. Creating such models for common documents is currently an expensive and error-prone process. In this thesis we present a novel approach to modelling and processing digital documents that uses semantic technologies. In contrast to other modelling approaches, we model the structure of documents as indicated by the content, not as defined by technical attributes like the file format. Additionally, our meta-model can be applied to a wide range of different documents, not just to a small set of documents with a predefined set of features. The models include semantic data and content relationships, which can be further extended with domain knowledge. Our new separation of technical and semantic document models fuels a standardised method for obtaining semantic models. This method is effective, suitable for live processing, and easily transferable to other document types and other domains. As it is makes extensive use of background knowledge, we also present techniques for obtaining such knowledge, and for representing complex forms of knowledge with multiple meta-layers. A flexible technique for obtaining relevant data from our document models completes the approach. This includes the ability to obtain various verification models, suitable for different types of consistency criteria and for different validation formalisms. We conclude this thesis with an evaluation that shows the viability and effectiveness of the proposed approach. We present runtime results for an implementation based on RDF/OWL and the rule language JBoss Drools that are adequate for live processing. We also provide and successfully apply techniques for measuring the quality of both document models and background knowledge. N2 - Für Anwendungen wie die Verifikation von Konsistenzkriterien für Dokumente werden präzise, inhaltlich reichhaltige, und wohlstrukturierte Dokumentmodelle benötigt. Solche formalen Modelle aus gewöhnlichen Dokumenten zu gewinnen ist bislang mit großem Aufwand verbunden und anfällig für Fehler. In dieser Dissertation wird ein neuer Ansatz zur Modellierung und zur weiteren Verarbeitung von digitalen Dokumenten beschrieben, der dieses Problem unter Verwendung von semantischen Technologien löst. Das entwickelte Meta-Modell ist unabhängig von der technischen Dokumentstruktur (dem Dokumentformat) und kann daher für eine Vielzahl unterschiedlicher Dokumente und Dokumentformate verwendet werden. Die Modelle enthalten semantische Daten und inhaltliche Zusammenhänge, die mithilfe von Domänenwissen noch erweitert werden können. Aus der strikt umgesetzten Trennung von technischen und semantischen Dokumentmodellen wird eine standardisierte Methode zur Gewinnung von semantischen Modellen hergeleitet. Diese Methode ist effektiv und kann leicht auf andere Dokumenttypen und andere Domänen übertragen werden. Da sie Hintergrundwissen verwendet, werden in der Arbeit außerdem Verfahren zur Gewinnung solchen Wissens vorgestellt, sowie Methoden zur Repräsentation komplexen Wissens mit mehreren Meta-Ebenen. Eine flexible Methode zur Gewinnung relevanter Daten aus den semantischen Modellen rundet den Ansatz ab. Dies schließt die Möglichkeit ein, unterschiedliche Verifikationsmodelle für verschiedene Konsistenzkriterien und für verschiedene Verifikationsformalismen zu gewinnen. Eine abschließende Evaluation zeigt die Machbarkeit und Effektivität des vorgeschlagenen Ansatzes. Laufzeitergebnisse einer auf RDF/OWL und der Regelsprache JBoss Drools basierenden Umsetzung des Ansatzes zeigen die Eignung für den Live-Einsatz. Schließlich werden Methoden zur Messung der Qualität von Dokumentmodellen und Hintergrundwissen vorgestellt und angewandt, und so die hohe Qualität der gewonnenen Modelle gezeigt. KW - Dokument KW - Semantik KW - Verifikation KW - Modellierung KW - Verarbeitung KW - Document KW - Semantics KW - Verification KW - Modelling KW - Processing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27635 ER -