TY - THES A1 - Ullah, Ehsan T1 - New Techniques for Polynomial System Solving N2 - Since any encryption map may be viewed as a polynomial map between finite dimensional vector spaces over finite fields, the security of a cryptosystem can be examined by studying the difficulty of solving large systems of multivariate polynomial equations. Therefore, algebraic attacks lead to the task of solving polynomial systems over finite fields. In this thesis, we study several new algebraic techniques for polynomial system solving over finite fields, especially over the finite field with two elements. Instead of using traditional Gröbner basis techniques we focus on highly developed methods from several other areas like linear algebra, discrete optimization, numerical analysis and number theory. We study some techniques from combinatorial optimization to transform a polynomial system solving problem into a (sparse) linear algebra problem. We highlight two new kinds of hybrid techniques. The first kind combines the concept of transforming combinatorial infeasibility proofs to large systems of linear equations and the concept of mutants (finding special lower degree polynomials). The second kind uses the concept of mutants to optimize the Border Basis Algorithm. We study recent suggestions of transferring a system of polynomial equations over the finite field with two elements into a system of polynomial equalities and inequalities over the set of integers (respectively over the set of reals). In particular, we develop several techniques and strategies for converting the polynomial system of equations over the field with two elements to a polynomial system of equalities and inequalities over the reals (respectively over the set of integers). This enables us to make use of several algorithms in the field of discrete optimization and number theory. Furthermore, this also enables us to investigate the use of numerical analysis techniques such as the homotopy continuation methods and Newton's method. In each case several conversion techniques have been developed, optimized and implemented. Finally, the efficiency of the developed techniques and strategies is examined using standard cryptographic examples such as CTC and HFE. Our experimental results show that most of the techniques developed are highly competitive to state-of-the-art algebraic techniques. KW - Polynomlösung KW - Algebra KW - Lineare Algebra KW - Algorithmus KW - polynomial system solving KW - techniques KW - linear algebra KW - border bases KW - mutant strategies Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26815 ER - TY - THES A1 - Xiu, Xingqiang T1 - Non-commutative Gröbner Bases and Applications N2 - Commutative Gröbner bases have a lot of applications in theory and practice, because they have many nice properties, they are computable, and there exist many efficient improvements of their computations. Non-commutative Gröbner bases also have many useful properties. However, applications of non-commutative Gröbner bases are rarely considered due to high complexity of computations. The purpose of this study was to improve the computation of non-commutative Gröbner bases and investigate the applications of non-commutative Gröbner bases. Gröbner basis theory in free monoid rings was carefully revised and Gröbner bases were precisely characterized in great detail. For the computations of Gröbner bases, the Buchberger Procedure was formulated. Three methods, say interreduction on obstructions, Gebauer-Möller criteria, and detecting redundant generators, were developed for efficiently improving the Buchberger Procedure. Further, the same approach was applied to study Gröbner basis theory in free bimodules over free monoid rings. The Buchberger Procedure was also formulated and improved in this setting. Moreover, J.-C. Faugere's F4 algorithm was generalized to this setting. Finally, many meaningful applications of non-commutative Gröbner bases were developed. Enumerating procedures were proposed to semi-decide some interesting undecidable problems. All the examples in the thesis were computed using the package gbmr of the computer algebra system ApCoCoA. The package was developed by the author. It contains dozens of functions for Gröbner basis computations and many concrete applications. The package gbmr and a collection of interesting examples are available at http://www.apcocoa.org/. KW - Gröbner-Basis KW - Assoziativer Ring KW - Endlich erzeugter Modul KW - Gruppentheorie KW - non-commutative polynomial KW - non-commutative Gröbner basis KW - applications KW - Gebauer-Möller KW - optimization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26827 ER - TY - THES A1 - Größlinger, Armin T1 - The Challenges of Non-linear Parameters and Variables in Automatic Loop Parallelisation T1 - Die Herausforderungen nichtlinearer Parameter und Variablen in automatischer Schleifenparallelisierung N2 - With the rise of manycore processors, parallelism is becoming a mainstream necessity. Unfortunately, parallel programming is inherently more difficult than sequential programming; therefore, techniques for automatic parallelisation will become indispensable. We aim at extending the well-known polyhedron model, which promises this automation, beyond some of its current restrictions. Up to now, loop bounds and array subscripts in the modelled codes must be expressions linear in both the variables and the parameters. We lift this restriction and allow certain polynomial expressions instead of linear ones. With our extensions, we are able to handle more programs in all phases of the parallelisation process (dependence analysis, transformation of the program model, code generation). We extend Banerjee's classical dependence analysis to handle one non-linear parameter p, i.e., we are able to determine precisely the solutions of the system of conflict equalities for input programs with non-linear array accesses like A[p*i] in dependence of the residue class of p. We make contributions to three transformations desirable in automatic parallelisation. First, we show that using a generalised Simplex algorithm, which we have developed, schedules with non-linear parameters like theta(i)=floor(i/n) can be computed. In addition, such schedules can be expressed easily as a quantifier elimination problem but this approach turns out to be computationally less efficient with the available implementation. As a second transformation, we study parametric tiling which is used to adapt a parallelised program to the number of available processors at run time. Third, we present a localisation technique to exploit scratchpad memories on architectures on which data caching has to be handled by software. We transform a given code such that it keeps values which are reused in successive iterations of a sequential loop in the scratchpad. An access to a value written in an earlier iteration is served from the scratchpad to accelerate the access. In general, this transformation introduces non-linear loop bounds in the transformed model. Finally, we present an algorithm for generating code for arbitrary semi-algebraic iteration sets, i.e., for iteration sets described by polynomial inequalities in the variables and parameters. This is a vast generalisation of existing polyhedral code generation techniques. Although our algorithm is less efficient than polyhedral code generators, this paves the way for a code generator that can handle arbitrary parametric tilings and other transformations which introduce non-linear parameters (like non-linear schedules and the localisation we present) or even non-linear variables. KW - Automatische Parallelisierung KW - Codegenerierung KW - Optimierender Compiler KW - Schleifentransformation KW - Codegenerierung für nicht-polyedrische Iterationsräume KW - Polyedermodell KW - automatic parallelization KW - loop transformations KW - code generation for non-polyhedral domains KW - polyhedron model KW - optimizing compilers Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-17893 ER - TY - THES A1 - Faber, Peter T1 - Code Optimization in the Polyhedron Model - Improving the Efficiency of Parallel Loop Nests T1 - Code-Optimierung im Polyedermodell - Effizienzsteigerung von parallelen Schleifensätzen N2 - A safe basis for automatic loop parallelization is the polyhedron model which represents the iteration domain of a loop nest as a polyhedron in $\mathbb{Z}^n$. However, turning the parallel loop program in the model to efficient code meets with several obstacles, due to which performance may deteriorate seriously -- especially on distributed memory architectures. We introduce a fine-grained model of the computation performed and show how this model can be applied to create efficient code. KW - Polyeder KW - High Performance Fortran KW - Codegenerierung KW - Compiler KW - Nebenläufigkeit KW - Polyedermodell KW - Schleifenparallelisierung KW - OpenMP KW - automatische Parallelisierung KW - optimierende Compiler KW - polyhedron model KW - loop parallelization KW - OpenMP KW - automatic parallelization KW - optimizing compilers Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12512 ER - TY - THES A1 - Rehn-Sonigo, Veronika T1 - Multi-criteria Mapping and Scheduling of Workflow Applications onto Heterogeneous Platforms T1 - Multi-kritäres Mapping und Scheduling von Workflow-Anwendungen auf heterogenen Plattformen N2 - The results summarized in this thesis deal with the mapping and scheduling of workflow applications on heterogeneous platforms. In this context, we focus on three different types of streaming applications: * Replica placement in tree networks * In this kind of application, clients are issuing requests to some servers and the question is where to place replicas in the network such that all requests can be processed. We discuss and compare several policies to place replicas in tree networks, subject to server capacity, Quality of Service (QoS) and bandwidth constraints. The client requests are known beforehand, while the number and location of the servers have to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. One major contribution of this work is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. We establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. * Pipeline workflow applications * We consider workflow applications that can be expressed as linear pipeline graphs. An example for this application type is digital image processing, where images are treated in steady-state mode. Several antagonist criteria should be optimized, such as throughput and latency (or a combination) as well as latency and reliability (i.e., the probability that the computation will be successful) of the application. While simple polynomial algorithms can be found for fully homogeneous platforms, the problem becomes NP-hard when tackling heterogeneous platforms. We present an integer linear programming formulation for this latter problem. Furthermore, we provide several efficient polynomial bi-criteria heuristics, whose relative performances are evaluated through extensive simulation. As a case-study, we provide simulations and MPI experimental results for the JPEG encoder application pipeline on a cluster of workstations. * Complex streaming applications * We consider the execution of applications structured as trees of operators, i.e., the application of one or several trees of operators in steady-state to multiple data objects that are continuously updated at various locations in a network. A first goal is to provide the user with a set of processors that should be bought or rented in order to ensure that the application achieves a minimum steady-state throughput, and with the objective of minimizing platform cost. We then extend our model to multiple applications: several concurrent applications are executed at the same time in a network, and one has to ensure that all applications can reach their application throughput. Another contribution of this work is to provide complexity results for different instances of the basic problem, as well as integer linear program formulations of various problem instances. The third contribution is the design of several polynomial-time heuristics, for both application models. One of the primary objectives of the heuristics for concurrent applications is to reuse intermediate results shared by multiple applications. N2 - In meiner Dissertation beschäftige ich mich mit dem Scheduling von Workflow-Anwendungen in heterogenen Plattformen. In diesem Zusammenhang konzentriere ich mich auf drei verschiene Anwendungstypen.: * Platzierung von Replikaten in Baumnetzwerken * Dieses erste Schedulingproblem behan-delt die Platzierung von Replikaten in Baumnetzwerken. Ein Beispiel hierfür ist die Platzierung von Replikaten in verteilten Datenbanksystemen, deren Verbindungsstruktur baumartig organi-siert ist. Die Platzierung soll dabei unter mehreren Constraints (Serverkapazitäten, sowie Dienstgüte und Bandbreitenbeschränkungen) durchgeführt werden. In diesem Anwendungstyp stellen Clients Anfragen an verschiedene Server. Diese Client-Anfragen sind im Voraus bekannt, während Anzahl und Platzierung der Server erst ermittelt werden müssen. Die in der Literatur gängige Strategie fordert, dass alle Anfragen eines Clients vom nächstgelegenen Server im Baum behandelt werden. Es werden zwei neue Verfahrensweisen vorgestellt und untersucht. Ein wichtiges Teilergebnis dieser Studie bewertet die Auswirkung der beiden neuen Strategien auf die globalen Replikationskosten. Ausserdem wird der Einfluss von Heterogenität aus theore-tischer und praktischer Sicht untersucht. Es werden verschiedene Komplexitätsergebnisse erar-beitet und mehrere effiziente Polynomialzeit-Heuristiken für NP-vollständige Instanzen des Problems vorgestellt. * Lineare Workflow-Anwendungen * Als nächstes werden Workflow-Anwendungen untersucht, die als lineare Graphen dargestellt werden können. Ein Beispiel dieses Applikationstyps ist die digitale Bildverarbeitung, in der Bilder mittels einer Pipeline verarbeitet werden. Es sollen ver-schie¬dene gegensätzliche Kriterien optimiert werden, wie zum Beispiel Durchsatz und Latenz-zeit, beziehungsweise eine Kombination der beiden, aber auch Latenzzeit und Ausfallsicherheit der Anwendung. Während für vollhomogene Plattformen polynomiale Algorithmen gefunden werden können, wird das Problem NP-hart, sobald heterogene Plattformen angestrebt werden. Diese Arbeit beinhaltet eine vollständige Komplexitätsanalyse. Für die bisher unbekannten polynomialen Varianten des Problems werden optimale Algorithmen vorgeschlagen. Ein ganz-zahliges lineares Programm für das bekannte „chains-on-chains“ Problem für heterogene Plattformen wird vorgestellt. Des weiteren werden verschiedene effiziente polynomiale bi-kritäre Heuristiken präsentiert, deren relative Effizienz durch umfangreiche Simulationen eruiert werden. Eine Fallstudie beschäftigt sich mit der JPEG-Encoder-Pipeline. Hierbei werden Simulationen und MPI-basierte Auswertungen auf einem Rechen-Cluster erstellt. * Komplexe Streaming-Anwendungen * Als letztes wird die Ausführung von Anwendungen, die als Operator-Bäume strukturiert sind, untersucht. Konkret bedeutet dies, dass ein oder mehrere Operator-Bäume in stationärem Zustand auf mannigfaltige Datenobjekte angewendet werden, welche fortlaufend an verschiedenen Stellen im Netzwerk aktualisiert werden. Ein erstes Ziel ist, dem Benutzer eine Gruppe von Rechnern vorzuschlagen, die gekauft oder gemietet werden sollen, so dass die Anwendung einen minimalen stationären Durchsatz erzielt und gleichzeitig Plattformkosten minimiert werden können. Anschließend wird das Modell auf mehrere Anwendungen erweitert: verschiedene nebenläufige Anwendungen werden zeitgleich in einem Netzwerk ausgeführt und es muss sichergestellt werden, dass alle Anwendungen ihren Durchsatz erreichen können. Beide Modelle werden aus theoretischer Sicht untersucht und eine Komplexitäts-analyse für unterschiedliche Instanzen des Grundproblems, sowie Formulierungen als lineare Programme erstellt. Für beide Anwendungsmodelle werden verschiedene Polynomialzeit-Heuristiken präsentiert und charakterisiert. Ein Hauptziel der Heuristiken für nebenläufige Anwendungen ist die Wiederverwertung von Zwischenergebnissen, welche von mehreren Anwedungen geteilt werden. KW - Replica placement KW - operator mapping KW - in-network stream processing KW - multi-criteria optimization KW - complexity Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-22249 ER - TY - THES A1 - Käbisch, Sebastian T1 - Resource Optimization of SOA-Technologies in Embedded Networks T1 - Ressourcen Optimierung von SOA-Technologien in eingebetteten Netzwerken N2 - Embedded networks are fundamental infrastructures of many different kinds of domains, such as home or industrial automation, the automotive industry, and future smart grids. Yet they can be very heterogeneous, containing wired and wireless nodes with different kinds of resources and service capabilities, such as sensing, acting, and processing. Driven by new opportunities and business models, embedded networks will play an ever more important role in the future, interconnecting more and more devices, even from other network domains. Realizing applications for such types of networks, however, is a highly challenging task, since various aspects have to be considered, including communication between a diverse assortment of resource-constrained nodes, such as microcontrollers, as well as flexible node infrastructure. Service Oriented Architecture (SOA) with Web services would perfectly meet these unique characteristics of embedded networks and ease the development of applications. Standardized Web services, however, are based on plain-text XML, which is not suitable for microcontroller-based devices with their very limited resources due to XML's verbosity, its memory and bandwidth usage, as well as its associated significant processing overhead. This thesis presents methods and strategies for realizing efficient XML-based Web service communication in embedded networks by means of binary XML using EXI format. We present a code generation approach to create optimized and dedicated service applications in resource-constrained embedded networks. In so doing, we demonstrate how EXI grammar can be optimally constructed and applied to the Web service and service requester context. In addition, so as to realize an optimized service interaction in embedded networks, we design and develop an optimized filter-enabled service data dissemination that takes into account the individual resource capabilities of the nodes and the connection quality within embedded networks. We show different approaches for efficiently evaluating binary XML data and applying it to resource constrained devices, such as microcontrollers. Furthermore, we will present the effectful placement of binary XML filters in embedded networks with the aim of reducing both, the computational load of constrained nodes and the network traffic. Various evaluation results of V2G applications prove the efficiency of our approach as compared to existing solutions and they also prove the seamless and successful applicability of SOA-based technologies in the microcontroller-based environment. KW - Web Services KW - Mikrocontroller KW - Skalierung KW - Effizienzsteigerung KW - World-Wide Web Consortium KW - XPath KW - Binäres XML KW - EXI KW - Eingebettete Netzwerke KW - Web Servics KW - Binary XML KW - EXI KW - Embedded Networks KW - XPath Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27338 ER - TY - THES A1 - Seedorf, Jan T1 - Security for Decentralised Service Location - Exemplified with Real-Time Communication Session Establishment N2 - Decentralised Service Location, i.e. finding an application communication endpoint based on a Distributed Hash Table (DHT), is a fairly new concept. The precise security implications of this approach have not been studied in detail. More importantly, a detailed analysis regarding the applicability of existing security solutions to this concept has not been conducted. In many cases existing client-server approaches to security may not be feasible. In addition, to understand the necessity for such an analysis, it is key to acknowledge that Decentralised Service Location has some unique security requirements compared to other P2P applications such as filesharing or live streaming. This thesis concerns the security challenges for Decentralised Service Location. The goals of our work are on the one hand to precisely understand the security requirements and research challenges for Decentralised Service Location, and on the other hand to develop and evaluate corresponding security mechanisms. The thesis is organised as follows. First, fundamentals are explained and the scope of the thesis is defined. Decentralised Service Location is defined and P2PSIP is explained technically as a prototypical example. Then, a security analysis for P2PSIP is presented. Based on this security analysis, security requirements for Decentralised Service Location and the corresponding research challenges -- i.e. security concerns not suitably mitigated by existing solutions -- are derived. Second, several decentralised solutions are presented and evaluated to tackle the security challenges for Decentralised Service Location. We present decentralised algorithms to enable availability of the DHTs lookup service in the presence of adversary nodes. These algorithms are evaluated via simulation and compared to analytical bounds. Further, a cryptographic approach based on self-certifying identities is illustrated and discussed. This approach enables decentralised integrity protection of location-bindings. Finally, a decentralised approach to assess unknown identities is introduced. The approach is based on a Web-of-Trust model. It is evaluated via prototypical implementation. Finally, the thesis closes with a summary of the main contributions and a discussion of open issues. KW - Security KW - P2P Systems KW - Peer-to-Peer-Netz KW - Verteilte Hash-Tabelle Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27147 ER - TY - THES A1 - Stadler, Bernhard T1 - Ein graphbasierter Formalismus zur Programmmanipulation T1 - A Graph-Based Formalism for Program Manipulation N2 - In dieser Arbeit wird ein Formalismus zur implementierungs-, sprach- und repräsentationsunabhängigen Beschreibung von Programmmanipulationen wie beispielsweise Merge, Featurekomposition und Interaktionsanalyse entwickelt. Dieser soll insbesondere der anwendungsnahen und wiederverwendbaren Definition von Programmanipulationen dienen. Programmmanipulationen werden auf repräsentationsunabhängige, deklarative Art mit Mitteln der Kategorientheorie beschrieben. Auf Grundlage einer Analyse des Text-To-Model-Frameworks EMFText werden Graphvarianten aus der algebraischen Graphtransformationstheorie zur Programmrepräsentation ausgewählt. Diese Graphvarianten werden anhand ihrer charakteristischen Merkmale in Graphfeatures aufgespalten. Auf Grundlage von Sketches, einer graphbasierten und kategorientheoretischen Art der algebraischen Spezifikation, wird eine Vorgehensweise für die formale Definition von Graphfeatures entwickelt. Diese Graphfeatures kann man auf flexible Weise zu sprachübergreifenden graphbasierten Programmrepräsentationen kombinieren. Als Anwendungen des Formalismus wurden der Merge und die Featurekomposition beschrieben. N2 - This work develops a formalism for the implementation-, language- and representation-independent description of program manipulations like, e.g., merge, feature composition and interaction analysis. This is meant to serve especially the application-directed and reusable definition of program manipulations. Program manipulations are being described by means of category theory declaratively and independently of the representation. Based on an analysis of the text-to-model framework EMFText, graph variants from algebraic graph transformation theory are being chosen for program representation. These graph variants are split up into graph features representing their individual characteristics. Based on sketches, a graph-based and category-theoretic way of algebraic specification, an approach to the formal definition of graph features is being developed. These graph features can be flexibly combined to language-independent, graph-based program representations. The application of the formalism is demonstrated on merge and feature composition KW - Informatik KW - Software Engineering KW - Kategorientheorie KW - Softwarespezifikation KW - Programmtransformation KW - Formalisierung KW - Mathematische Logik KW - Graphen KW - Algebraische Graphtransformationstheorie KW - Graphvarianten KW - Graphfeatures KW - Sketches KW - Typisierte Graphen mit Containment KW - Algebraic Graph Transformation Theory KW - Graph variants KW - Graph features KW - Sketches KW - Typed Graphs with Containment Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27128 ER - TY - THES A1 - Vilsmaier, Christian T1 - Contextualized Access To Distributed And Heterogeneous Multimedia Data Sources T1 - Kontextabhängiger Zugriff auf Verteilte und Heterogene Multimedial Daten Quellen N2 - Making multimedia data available online becomes less expensive and more convenient on a daily basis. This development promotes web phenomenons such as Facebook, Twitter, and Flickr. These phenomena and their increased acceptance in society in turn leads to a multiplication of the amount of available images online. This vast amount of, frequently public and therefore searchable, images already exceeds the zettabyte bound. Executing a similarity search on the magnitude of images that are publicly available in the Internet, and receiving a top quality result is a challenge that the scientific community has recently attempted to rise to. One approach to cope with this problem assumes the use of distributed heterogeneous Content Based Image Retrieval system (CBIRs). Following from this anticipation, the problems that emerge from a distributed query scenario must be dealt with. For example the involved CBIRs’ usage of distinct metadata formats for describing their content, as well as their unequal technical and structural information. An addition issue is the individual metrics that are used by the CBIRs to calculate the similarity between pictures, as well as their specific way of being combined. Overall, receiving good results in this environment is a very labor intensive task which has been scientifically but not yet comprehensively explored. The problem primarily addressed in this work is the collection of pictures from CBIRs, that are similar to a given picture, as a response to a distributed multimedia query. The main contribution of this thesis is the construction of a network of Content Based Image Retrieval systems that are able to extract and exploit the information about an input image’s semantic concept. This so called semantic CBIRn is mainly composed of CBIRs that are configured by the semantic CBIRn itself. Complementarily, there is a possibility that allows the integration of specialized external sources. The semantic CBIRn is able to collect and merge results of all of these attached CBIRs. In order to be able to integrate external sources that are willing to join the network, but are not willing to disclose their configuration, an algorithm was developed that approximates these configurations. By categorizing existing - as well as external - CBIRs and analyzing incoming queries, image queries are exclusively forwarded to the most suitable CBIRs. In this way, images that are not of any use for the user can be omitted beforehand. The hereafter returned images are rendered comparable in order to be able to merge them to one single result list of images, that are similar to the input image. The feasibility of the approach and the hereby obtained improvement of the search process is demonstrated by a prototypical implementation and its evaluation using classified images of ImageNet. Using this prototypical implementation an augmentation of the number of returned images that are of the same semantic concept as the input images is achieved by a factor of 4.75 with respect to a predefined non-semantic CBIRn. N2 - Multimedia Daten im Internet bereitzustellen wird von Tag zu Tag kostengünstiger und bequemer. Diese Entwicklung fördert Netz-Phänomene wie Facebook, Twitter und Flickr. Dies wiederum führt zu einer Multiplikation der im Internet verfügbaren Bilder. Diese Menge von häufig öffentlichen und darum suchbaren Bildern übersteigt schon heute die Zettabyte-Grenze. Eine ähnlichkeits-Suche auf diese Masse von Bildern, die öffentlich im Internet verfügbar sind, auszuführenundeinhochwertigesResultatzuerzielenisteineHerausforderungdersichdie wissenschaftliche Gemeinschaft heutzutage stellt. Um beispielsweise dieses Problem mit Inhaltsbasierten Bilder Suchsystemen (CBIRs) zu lösen müssen Probleme, die durch ein verteiltes Anfrageszenario entstehen, behandelt werden. Damit sind u.a. die Verwendung von unter- schiedlichen Ausprägungen von Metadaten Formaten involvierter CBIRs um ihre Bilder zu beschreiben, so wie ihre ungleiche technischen und strukturellen Informationen gemeint. Oder die individuellen Metriken, die von den CBIRs verwendet werden um die Ähnlichkeit der Bilder zu berechnen, wie auch ihre spezielle Art diese zu kombinieren. Im Großen und Ganzen besteht eine sehr arbeitsintensive Aufgabe darin, unter diesen Umständen gute Resultate zu erzielen. Diese Aufgabe wurde von wissenschaftlicher Seite noch nicht umfassend erforscht. Das Problem das hauptsächlich in dieser Arbeit thematisiert wird, ist das Sammeln von Bildern die einem vorgegebenen Bild ähnlich sind, als Antwort auf eine verteilte Multimedia Anfrage. Der Hauptbeitrag dieser Dissertation ist der Aufbau eines Netzwerks von CBIRs, das die semantischen Konzepte der Anfragebilder nutzen kann, genannt semantisches CBIRn. Das semantische CBIRn ist in der Lage, Ergebnisse von CBIRs zu sammeln und zusammenzufügen, die vom semantischen CBIRn selbst angelegt wurden, und CBIRs, die von spezialisierten externen Quellen integriert wurden. Um in der Lage zu sein, externe Quellen zu integrieren die dem Netzwerk beitreten möchten, jedoch nicht ihre Konfigurationen preis geben möchten, wurde ein Algorithmus entwickelt der diese Konfiguration berechnet. Durch die Kategorisierung der angelegten - wie auch der externen - CBIRs und durch die Analyse einkommender Anfragen, werden inhaltsbasierte Suchanfragen ausschließlich zu den geeignetsten CBIRs weitergeleitet. DieanschließendzurückgegebenenBilderwerdenvergleichbargemachtumimstandezusein, sie zu fusionieren und eine Ergebnisliste zurückzugeben, die dem Eingabebild ähnlich sind. Die Machbarkeit des Ansatzes und die gewonnenen Verbesserungen des Suchprozesses wird durch eine prototypische Umsetzung und einer Auswertung von Tests mit klassifizierten Bilder von ImageNet durchgeführt. Hierbei wurde im Vergleich mit einer vordefinierten nicht-semantischen CBIRn eine Steigerung der Anzahl der rückgegebenen Bilder die dem selben semantischen Konzepts wie das das Eingabebild entsprechen, um den Faktor 4.75, erreicht. KW - Multimedia KW - Inhalt KW - Verschmelzung KW - Bild KW - Suche KW - System KW - Multimedia Datenbanken KW - Inhaltsbasierte Bilder Suche KW - Inhaltsbasierte Bilder Suchsysteme KW - Daten Fusion KW - Daten Verschmelzung KW - Bilder Suche KW - MultimediaDatabases KW - ContentBasedImageRetrieval KW - CBIRs KW - DataFusion KW - Data Merging KW - Image Retrieval Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27374 ER - TY - THES A1 - Peintner, Daniel T1 - Efficient Exchange and Processing of Semi-structured Data in the Embedded Domain T1 - Effizienter Austausch and Verarbeitung von semistrukturierten Daten in eingebetteten Systemen N2 - The Internet is a global system of interconnected computers and computer networks where semi-structured data has been successfully applied for exchanging information. In nowadays Internet the huge range of actors, the large diversity of the associated device classes and domains, and the enormous amount of resource-restricted controllers in this system created new requirements and coined also a new term. Internet of Things (IoT), in this regard, refers to identifiable objects (things) and their virtual representations in an Internet-like structure. The fundamental question the thesis tries to answer is whether and how the same semi-structured data can be also applied to the IoT and the embedded domain in spite of resource-limited controllers. In order to discuss this question properties and requirements of embedded networks with regard to the IoT domain have been collected and evaluated. Thereafter the omnipresent semi-structured data exchange format in the Web, the Extensible Markup Language (XML), has been validated. The result was a list of missing requirements such as a compact representation, a representation that can be generated and consumed fast and also allows a small footprint implementation. To address the compiled requirements a binary representation of XML which nowadays is known as W3Cs Efficient XML Interchange (EXI) format has been accomplished which simultaneously optimizes performance and the utilization of computational resources and is designed to be compatible with XML. Moreover, in this work the format has been practically validated and tested. Addressing the needs of the embedded domain one result of this analyzes were optimizations to constrain runtime memory usage and to predict memory growth at runtime. A concept introduced in this thesis is LazyDOM which reduces memory requirements when processing and querying data. By means of a newly proposed code generation technique processing of EXI on ultra-constrained device classes has been enabled and resulting format modifications have been adopted by the W3C standardization. The research work described in this thesis on efficiently exchanging and processing semi-structured data on constrained embedded devices has not only triggered modifications in the W3C EXI format but even is already adopted in domain specific application standards and implementations. The above mentioned optimizations such as predictably limit the memory growth at runtime have been contributed, discussed and evaluated by the W3C experts and become a core part of the EXI specification. Even more significantly from the IoT perspective these optimizations provide the basis for the adoption of this technology in ISO and IEC standardization which is the first time for automotive and power industry to use IoT in the control plane. The implementation of EXI to conduct the evaluation as part of this thesis has become the de-facto open source reference implementation of EXI and became the basis of a number of other reference implementations such as the OpenV2G project that provides the reference implementation of the communication interface in ISO/IEC 15118. In summary the conducted research work has evaluated the options to adapt semi-structured data for the constrained embedded domain, proposed modifications and evaluated those under realistic conditions. This made it relevant for the technology as well as for application standardization despite the short period of this work. As such the research can now be taken as a basis for further challenges in the IoT field namely adopting concepts of the Semantic Web and adapting those to stimulate the quickly expanding eco-system of embedded devices. KW - Mikrocontroller KW - XML KW - Strukturierte Daten KW - Effizienzsteigerung KW - World-Wide Web Consortium KW - Binäres XML KW - EXI KW - Efficient XML Interchange KW - Eingebettete Systeme KW - Binary XML KW - EXI KW - Efficient XML Interchange KW - Embedded Networks Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27610 ER -