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 - 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 - 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 - 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 - 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 - CHAP T1 - Proceedings of the 3rd International Workshop on Polyhedral Compilation Techniques N2 - IMPACT 2013 in Berlin, Germany (in conjuction with HiPEAC 2013) is the third workshop in a series of international workshops on polyhedral compilation techniques. The previous workshops were held in Chamonix, France (2011) in conjuction with CGO 2011 and Paris, France (2012) in conjuction with HiPEAC 2012. KW - Optimierender Compiler KW - polyhedral compilation KW - polyhedral optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26930 ER - TY - THES A1 - Kunze, Kai T1 - Compensating for On-Body Placement Effects in Activity Recognition T1 - Kompensation positionsbezogener Artefakte in Aktivitätserkennung N2 - This thesis investigates, how placement variations of electronic devices influence the possibility of using sensors integrated in those devices for context recognition. The vast majority of context recognition research assumes well defined, fixed sen- sor locations. Although this might be acceptable for some application domains (e.g. in an industrial setting), users, in general, will have a hard time coping with these limitations. If one needs to remember to carry dedicated sensors and to adjust their orientation from time to time, the activity recognition system is more distracting than helpful. How can we deal with device location and orientation changes to make context sensing mainstream? This thesis presents a systematic evaluation of device placement effects in context recognition. We first deal with detecting if a device is carried on the body or placed somewhere in the environ- ment. If the device is placed on the body, it is useful to know on which body part. We also address how to deal with sensors changing their position and their orientation during use. For each of these topics some highlights are given in the following. Regarding environmental placement, we introduce an active sampling ap- proach to infer symbolic object location. This approach requires only simple sensors (acceleration, sound) and no infrastructure setup. The method works for specific placements such as "on the couch", "in the desk drawer" as well as for general location classes, such as "closed wood compartment" or "open iron sur- face". In the experimental evaluation we reach a recognition accuracy of 90% and above over a total of over 1200 measurements from 35 specific locations (taken from 3 different rooms) and 12 abstract location classes. To derive the coarse device placement on the body, we present a method solely based on rotation and acceleration signals from the device. It works independent of the device orientation. The on-body placement recognition rate is around 80% over 4 min. of unconstrained motion data for the worst scenario and up to 90% over a 2 min. interval for the best scenario. We use over 30 hours of motion data for the analysis. Two special issues of device placement are orientation and displacement. This thesis proposes a set of heuristics that significantly increase the robustness of motion sensor-based activity recognition with respect to sen- sor displacement. We show how, within certain limits and with modest quality degradation, motion sensor-based activity recognition can be implemented in a displacement tolerant way. We evaluate our heuristics first on a set of synthetic lower arm motions which are well suited to illustrate the strengths and limits of our approach, then on an extended modes of locomotion problem (sensors on the upper leg) and finally on a set of exercises performed on various gym machines (sensors placed on the lower arm). In this example our heuristic raises the dis- placed recognition rate from 24% for a displaced accelerometer, which had 96% recognition when not displaced, to 82%. KW - Kontextbezogenes System KW - Mustererkennung KW - Aktivitätserkennung KW - positionsbezogener Effekte KW - sensor displacement KW - on-body KW - context recognition Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26114 ER - TY - THES A1 - Capco, Jose T1 - Real Closed * Rings T1 - Reelle abgeschlossene * Ringe N2 - In this dissertation I examine a definition of real closure of commutative unitary reduced rings. I also give a characterization of rings that are real closed in this context and how one is able to arrive to such a real closure. There are sufficient examples to help the reader get a feel for real closed * rings and the real closure * of commutative unitary rings. KW - real closed rings KW - real closure Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-25915 ER - TY - INPR A1 - Kreitmeier, Wolfgang A1 - Linder, Tamas T1 - Entropy Density and Mismatch in High-Rate Scalar Quantization with Rényi Entropy Constraint N2 - Properties of scalar quantization with $r$th power distortion and constrained R\'enyi entropy of order $\alpha\in (0,1)$ are investigated. For an asymptotically (high-rate) optimal sequence of quantizers, the contribution to the R\'enyi entropy due to source values in a fixed interval is identified in terms of the "entropy density" of the quantizer sequence. This extends results related to the well-known point density concept in optimal fixed-rate quantization. A dual of the entropy density result quantifies the distortion contribution of a given interval to the overall distortion. The distortion loss resulting from a mismatch of source densities in the design of an asymptotically optimal sequence of quantizers is also determined. This extends Bucklew's fixed-rate ($\alpha=0$) and Gray \emph{et al.}'s variable-rate ($\alpha=1$)mismatch results to general values of the entropy order parameter $\alpha$ KW - Maßtheorie KW - Quantisierung KW - Entropie KW - Asymptotic quantization theory KW - distortion density KW - entropy density KW - quantizer mismatch KW - Rényi-entropy Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26132 N1 - This is a preprint of an article accepted for publication in the IEEE Transactions on Information Theory Journal, ISSN: 0018-9448. The original publication is available at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 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 - 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 - Radde, Sven T1 - A Layered Conversational Recommender System N2 - In this thesis a new approach to building product recommender systems is introduced. By using a customer-centric dialogue, the customers' preferences are elicited. These are the basis for inferring utility estimations about the desired technical properties of the products in question. Systems built this way can both operate autonomously, e.g., in an online store, and support a salesperson directly at the point-of-sale. The core of the approach is formed by a layered domain description that models customer stereotypes and needs, product attributes, the products themselves, and the causal interrelations between customer and product properties. Maintenance of the domain description, i.e., keeping the model up-to-date in face of frequent changes, is facilitated by the clear separation of concerns provided by the layered structure. In fact, the most frequently used class of updates can be handled in an entirely automated way if some constraints are satisfied. On a high level of abstraction, the system behavior is described by State Charts that are parameterized according to the domain description. Those parts of the system description where State Charts would be too imprecise are implemented by separate components realizing the required complex semantics. From the domain description, a Bayesian network is generated that forms the core of the inference engine of the recommender system. The network essentially controls the system-initiated dialogue flow and the recommendation process. Due to the characteristics of Bayesian networks, it is possible to respond to user-initiated dialogue steps in a natural way. Moreover, an explanation of the current recommendation can be generated without having to explicitly encode additional information in the modeling layer. Finally, a database structure and the SQL queries necessary to obtain recommendations can be inferred from the corresponding parts of the domain description. Instantiation of the system to a specific business domain is supported by a dedicated maintenance application that hides the complexities of the underlying algorithms. Thus, day-to-day system updates by non-technical domain experts, e.g., product managers, are facilitated. The developed concepts were implemented in cooperation with a local industry partner who intends to apply the recommender system in the field of mobile communications. N2 - In dieser Dissertation wird ein neuer Ansatz zur Konstruktion von Produkt-Beratungssystemen vorgestellt, die mit den Kunden einen bedürfnisorientierten Dialog führen und dann aus den gegebenen Antworten Abschätzungen über die jeweilige Nützlichkeit verschiedener charakteristischer Attribute der zu empfehlenden Produkte gewinnen. Die so erstellten Systeme können sowohl autonom, beispielsweise in einem Onlineshop, als auch zur Unterstützung von Verkäufern direkt im Ladengeschäft eingesetzt werden. Eine Domänenbeschreibung, die auf mehreren Ebenen Kundenstereotypen, -bedürfnisse, Produktattribute, sowie die Beziehungen zwischen Kunden- und Produkteigenschaften und die Produkte selbst modelliert, bildet den Kern des Ansatzes. Die Pflege der Domänenbeschreibung wird durch die Unterteilung in mehrere Ebenen deutlich unterstützt. Tatsächlich kann unter gewissen Bedingungen die häufigste Klasse von Aktualisierungen vollautomatisch vom System selbst gehandhabt werden. Mit Elementen der Domänenbeschreibung parametrisierte State Charts beschreiben das Systemverhalten auf abstrakter Ebene, während domänenspezifische Teile, welche durch State Charts nicht ausreichend präzise modelliert werden können, durch separate Komponenten implementiert werden, die die erforderlichen Funktionen realisieren. Aus der Domänenbeschreibung wird ein Bayesnetz generiert, das den Kern der Inferenzmaschine des Beratungssystems bildet und zur Steuerung des Beratungsdialogs und des Empfehlungsprozesses genutzt wird. Die Eigenschaften von Bayesnetzen ermöglichen es unter anderem, Nutzer-initiierte Dialogschritte auf natürliche Weise in den Beratungsprozess zu integrieren. Darüber hinaus können verständliche Erklärungen für die erzeugten Produktempfehlungen generiert werden, ohne dass dazu zusätzliche Informationen explizit in die Modellierung eingebracht werden müssen. Desweiteren können die vom System zu verwendende Datenbankstruktur und die zur Empfehlungsgenerierung benötigten SQL-Abfragen aus den entsprechenden Teilen der Domänenbeschreibung erzeugt werden. Die Instanziierung des Systems für ein konkretes Geschäftsfeld erfolgt über eine dedizierte Pflegeanwendung, die die mathematische Komplexität der eingesetzten Algorithmen verbirgt und so die Aktualisierung des Systems auch durch Domänenexperten ohne technische Ausbildung, wie z.B. Produktmanager, ermöglicht. Eine praktische Implementierung erfolgte im Rahmen eines gemeinsamen Projekts mit einem Industriepartner aus der Region, der das Beratungssystem u.a. im Bereich des Vertriebs von Mobilfunkprodukten einsetzen möchte. KW - Empfehlungssystem KW - Inferenz KW - Bayes-Inferenz KW - Relationale Datenbank KW - Recommender Systems KW - Artificial Intelligence KW - Bayesian Networks KW - Relational Databases Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27031 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Asymptotic optimality of scalar Gersho quantizers N2 - In his famous paper Gersho stressed that the codecells of optimal quantizers asymptotically make an equal contribution to the distortion of the quantizer. Motivated by this fact, we investigate in this paper quantizers in the scalar case, where each codecell contributes with exactly the same portion to the quantization error. We show that such quantizers of Gersho type - or Gersho quantizers for short - exist for non-atomic scalar distributions. As a main result we prove that Gersho quantizers are asymptotically optimal. KW - Maßtheorie KW - Informationstheorie KW - Signaltheorie KW - Approximation KW - Kodierung KW - Quantisierung KW - Asymptotically optimal quantization KW - Quantization error KW - Scalar quantization KW - Gersho quantizer KW - High rate quantization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27080 N1 - This is a preprint of an article accepted for publication in Constructive Approximation, ISSN: 0176-4276 (print version) ISSN: 1432-0940 (electronic version) Copyright (c) by Springer. The final publication is available at link.springer.com URL: http://dx.doi.org/10.1007/s00365-013-9214-2 ER - TY - THES A1 - Brunner, Wolfgang T1 - Cyclic Level Drawings of Directed Graphs T1 - Zyklische Levelzeichnungen gerichteter Graphen N2 - The Sugiyama framework proposed in the seminal paper of 1981 is one of the most important algorithms in graph drawing and is widely used for visualizing directed graphs. In its common version, it draws graphs hierarchically and, hence, maps the topological direction to a geometric direction. However, such a hierarchical layout is not possible if the graph contains cycles, which have to be destroyed in a preceding step. In certain application and problem settings, e.g., bio sciences or periodic scheduling problems, it is important that the cyclic structure of the input graph is preserved and clearly visible in drawings. Sugiyama et al. also suggested apart from the nowadays standard horizontal algorithm a cyclic version they called recurrent hierarchies. However, this cyclic drawing style has not received much attention since. In this thesis we consider such cyclic drawings and investigate the Sugiyama framework for this new scenario. As our goal is to visualize cycles directly, the first phase of the Sugiyama framework, which is concerned with removing such cycles, can be neglected. The cyclic structure of the graph leads to new problems in the remaining phases, however, for which solutions are proposed in this thesis. The aim is a complete adaption of the Sugiyama framework for cyclic drawings. To complement our adaption of the Sugiyama framework, we also treat the problem of cyclic level planarity and present a linear time cyclic level planarity testing and embedding algorithm for strongly connected graphs. KW - Graphenzeichnen KW - Gerichteter Graph KW - Kreis KW - Planarer Graph KW - Ebenenzeichnung KW - zyklisch KW - graph drawing KW - directed graph KW - cyclic level drawing KW - cyclic level planarity Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-17962 ER - TY - THES A1 - Bachl, Walter T1 - Interaktives orthogonales Zeichnen von planaren Graphen N2 - Die Arbeit beschäftigt sich mit dem automatischen Zeichnen von Graphen. Hier wird ein interaktiver Ansatz untersucht, bei dem der Graph mit einer Menge von Operationen Schritt für Schritt aufgebaut wird. Der Zielgraph und die Einfügereihenfolge sind dabei nicht fest vorgegeben, sondern werden vom Benutzer bestimmt. In der Arbeit wird vor allem ein Szenario für zweifach zusammenhängende Graphen untersucht und ein für diese Zwecke passendes Zeichenmodell entwickelt. Dieser Ansatz wird dann um verschiedene Varianten erweitert. Außerdem wird gezeigt, dass das flächenminimale Zeichnen in dem neu entwickelten Zeichenmodell NP-vollständig ist. KW - Graphenzeichnen KW - Graphalgorithmen KW - Flächenminimales Zeichnen Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-392 ER - TY - THES A1 - Krinke, Jens T1 - Advanced Slicing of Sequential and Concurrent Programs N2 - Program slicing is a technique to identify statements that may influence the computations in other statements. Despite the ongoing research of almost 25 years, program slicing still has problems that prevent a widespread use: Sometimes, slices are too big to understand and too expensive and complicated to be computed for real-life programs. This thesis presents solutions to these problems: It contains various approaches which help the user to understand a slice more easily by making it more focused on the user's problem. All of these approaches have been implemented in the VALSOFT system and thorough evaluations of the proposed algorithms are presented. The underlying data structures used for slicing are program dependence graphs. They can also be used for different purposes: A new approach to clone detection based on identifying similar subgraphs in program dependence graphs is presented; it is able to detect modified clones better than other tools. In the theoretical part, this thesis presents a high-precision approach to slice concurrent procedural programs despite that optimal slicing is known to be undecidable. It is the first approach to slice concurrent programs that does not rely on inlining of called procedures. N2 - Program Slicing ist eine Technik zur Identifikation von Anweisungen, die andere Anweisungen beeinflussen können. Trotz seit nunmehr 25 Jahren anhaltender Forschung hat Program Slicing immer noch Probleme, die eine verbreitete Benutzung verhindern: Slices können zu groß oder zu unverständlich werden, oder ihre Berechnung kann zu teuer oder zu kompliziert für echte Programme sein. Diese Dissertation präsentiert Lösungen und Auswege aus diesen Problemen. Sie enthält einerseits eine Reihe von Slicing-Verfahren unterschiedlicher Präzision und Geschwindigkeit. Andererseits enthält sie verschiedenste Verfahren, die dem Benutzer helfen, Slices leichter zu verstehen indem die berechneten Slices mehr auf seine Bedürfnisse fokussiert werden. Alle vorgestellten Verfahren wurden im VALSOFT-System implementiert und gründlich evaluiert. Die dem Slicing zugrunde liegende Datenstruktur sind Programmabhängigkeitsgraphen. Diese können auch für andere Anwendungen benutzt werden: Ein neues Verfahren zur Entdeckung von dupliziertem Code identifiziert ähnliche Teilgraphen in Programmabhängigkeitsgraphen. Dieses Verfahren kann modifizierte Duplikate besser erkennen als andere Verfahren. Auf der theoretischen Seite präsentiert diese Dissertation ein hochpräzises Verfahren zum Slicing nebenläufiger prozeduraler Programme, wobei optimales Slicing bekannterweise nicht entscheidbar ist. Dieses Verfahren ist das erste zum Slicen nebenläufiger Programme, das nicht auf Inlining aufgerufener Prozeduren zurückgreift. KW - Programmanalyse KW - Programmtransformation KW - Software Engineering KW - Reengineering / Software KW - Softwarewartung KW - program analysis KW - program slicing KW - software reengineering Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-375 ER - TY - THES A1 - Wiesner, Christian T1 - Query Evaluation Techniques for Data Integration Systems T1 - Auswertungstechniken für Datenintegrationssysteme N2 - In this work we present novel query evaluation techniques for data integration systems in different environments, ranging from a central data-warehouse approach, over distributed virtual market places, to peer-to-peer (P2P) systems. Based on a new distributed evaluation technique, the so-called HyperQueries, we present a reference architecture for distributed virtual market places. These HyperQueries enable us to dynamically construct query evaluation plans by referencing sub-plans in the Internet. Furthermore, the process of data integration is structured. Subsequently, we investigate P2P data integration systems without central instances. We introduce so-called Super-Peers which structure a P2P network. Using this Super-Peer based network we "unroll" queries. This allows us to execute even user-defined operators nearby the data sources. Finally, we propose novel, efficient join algorithms for decision support queries in central data-warehouse systems. The proposed order-preserving hashjoins and generalized hashteams are based on early sorting and early partitioning of the inputs and can speed up the query evaluation up to orders of magnitutes. N2 - In dieser Arbeit werden neue Auswertungstechniken für Anfragen in unterschiedlichen Datenintegrationsumgebungen gezeigt, angefangen vom zentralen Data-Warehouse-Ansatz, über verteilte virtuelle Marktplätze bis hin zu Peer-To-Peer (P2P) Systemen. Basierend auf einer neuen verteilten Auswertungstechnik, den sog. HyperQueries, wird eine Referenzarchitektur für verteilte virtuelle Marktplätze gezeigt. Diese HyperQueries ermöglichen den dynamischen Aufbau von Auswertungsplänen durch die Referenzierung von Teilplänen im Internet und eine Strukturierung des Datenintegrationsprozesses. Daran anschließend werden P2P Datenintegrationssysteme ohne zentrale Instanzen näher betrachtet. Dazu wird ein P2P Netzwerk durch den Einsatz von Super-Peers strukturiert und es werden Anfragepläne über das Netzwerk hin "abgerollt". Das ermöglicht es, auch benutzerdefinierte Operatoren nahe an den Datenquellen auszuführen. Den Abschluss bilden neue, effiziente Join Methoden für Decision Support Anfragen in zentralen Data-Warehouse-Systemen. Die vorgestellten ordnungserhaltenden Hashjoins und verallgemeinerten Hashteams basieren auf früher Sortierung und früher Partitionierung der Eingaben und können die Anfragebearbeitung um Grössenordnungen beschleunigen. KW - Abfrageverarbeitung KW - Electronic Commerce KW - Datenintegration KW - Anfrageauswertung KW - Java KW - verteilte Datenbanken KW - Anfrageoptimierung KW - Skalierbarkeit KW - query processing KW - Java KW - distributed databases KW - query optimization KW - scalability Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-406 ER - TY - THES A1 - Bachmaier, Christian T1 - Circle Planarity of Level Graphs T1 - Kreisplanarität von Level-Graphen N2 - In this dissertation we generalise the notion of level planar graphs in two directions: track planarity and radial planarity. Our main results are linear time algorithms both for the planarity test and for the computation of an embedding, and thus a drawing. Our algorithms use and generalise PQ-trees, which are a data structure for efficient planarity tests. N2 - In dieser Arbeit wird der Begriff Level-Planarität von Graphen auf zwei Arten erweitert: Spur-Planarität und radiale Level-Planarität. Die Hauptergebnisse sind Linearzeitalgorithmen zum Testen dieser Arten von Planarität und zur Erstellung einer entsprechenden Einbettung und somit einer Zeichnung. Die Algorithmen verwenden und generalisieren PQ-Bäume, eine bei effizienten Planaritätstests verwendete Datenstruktur. KW - Graphentheorie KW - Graphenklasse KW - Graphenzeichnen KW - Graph KW - radial level panarity KW - track planarity Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-385 ER - 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 -