TY - JOUR A1 - Boll, Susanne A1 - Meinhardt, Rolf A1 - Gronewold, Sabine A1 - Krekeler, Larissa T1 - Informatik für Migratinnen und Migranten Einführung eines neuen Studienprogramms an der Universität Oldenburg JF - Commentarii informaticae didacticae : (CID) N2 - Für die Integration und den Bedarf der hochqualifizierten Migranten auf dem Arbeitsmarkt in Deutschland gibt es viele Überlegungen, aber noch keine ausreichenden Lösungen. Dieser Artikel beschreibt eine praktische Lösung über die Umsetzung des Konzepts für die Qualifizierung der akademischen Migranten am Beispiel eines Studienprogramms in Informatik an der Universität Oldenburg. Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64370 SN - 1868-0844 SN - 2191-1940 IS - 4 SP - 79 EP - 86 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Laroque, Christoph A1 - Schulte, Jonas A1 - Urban, Diana T1 - KoProV BT - ein Lehransatz zur koordinierten Projektvorlesung auf Basis von Wissensmodulen JF - Commentarii informaticae didacticae : (CID) N2 - In der universitären Lehre ändert sich der Leitgedanke von einer qualifikationsorientierten hin zu einer kompetenzorientierten Ausbildung. Der Begriff Kompetenz lässt sich dabei grob in die fachlichen und die überfachlichen Kompetenzen unterteilen. Insbesondere die Vermittlung von Schlüsselqualifikationen hat in der Lehre von naturwissenschaftlichen Fachrichtungen nur unzureichend Einzug erhalten. Während der klassische Vorlesungsbetrieb auf den Erwerb von Fachkompetenz zielt, stoßen ausschließlich projektorientierte Veranstaltungen schnell an ihre Grenzen hinsichtlich der Teilnehmergröße oder Umfang der Lerninhalte. Um auf geeignete Art und Weise den Erwerb von überfachlichen Kompetenzen zu ermöglichen, bedarf es neuer didaktischer Konzepte, die eine engere Verknüpfung von klassischen Vorlesungen und dem projektorientierten Lernen vorsehen. In diesem Sinne versucht der skizzierte Ansatz der koordinierten Projektvorlesung(KoProV) Wissensvermittlung im Rahmen von Vorlesungseinheiten mit koordinierten Praxisphasen in Teilgruppen zu verbinden. Für eine erfolgreiche Durchführung und Erarbeitung des begleitenden Praxisprojektes durch mehrere Teilgruppen sind organisatorische und technische Randbedingungen zu beachten. Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64445 SN - 1868-0844 SN - 2191-1940 IS - 4 SP - 99 EP - 105 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Kiss, Gábor T1 - Analyse der Studienleistungen von Studierenden an der Universität Óbuda und deren Implikationen für die Informatikausbildung JF - Commentarii informaticae didacticae : (CID) N2 - In der letzten Jahren ist die Zahl der erfolgreichen Prüfungen von Studierenden im Informatikkurs des ersten Studienjahres für verschiedene Studiengänge an der Universität Óbuda stark gesunken. Dies betrifft Prüfungen in den Teilgebieten Rechnerarchitektur, Betrieb von Peripheriegeräten, Binäre Codierung und logische Operationen, Computerviren, Computernetze und das Internet, Steganographie und Kryptographie, Betriebsysteme. Mehr als der Hälfte der Studenten konnte die Prüfungen der ersten Semester nicht erfolgreich absolvieren. Die hier vorgelegte Analyse der Studienleistungen zielt darauf ab, Gründe für diese Entwicklung zu identifizieren, die Zahl der Abbrecher zu reduzieren und die Leistungen der Studenten zu verbessern. Die Analyse zeigt, dass die Studenten die erforderlichen Lehrmaterialen erst ein bis zwei Tage vor oder sogar erst am Tag der Klausuren vom Server downloaden, so dass sie nicht mehr hinreichend Zeit zum Lernen haben. Diese Tendenz zeigt sich bei allen Teilgebieten des Studiengangs. Ein Mangel an kontinuierlicher Mitarbeit scheint einer der Gründe für ein frühes Scheitern zu sein. Ferner zeigt sich die Notwendigkeit, dass bei den Lehrangeboten in Informatik auf eine kontinuierliche Kommunikation mit den Studierenden und Rückmeldung zu aktuellen Unterrichtsinhalten zu achten ist. Dies kann durch motivierende Maßnahmen zur Teilnahme an den Übungen oder durch kleine wöchentliche schriftliche Tests geschehen. Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64364 SN - 1868-0844 SN - 2191-1940 IS - 4 SP - 71 EP - 77 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - THES A1 - Seibel, Andreas T1 - Traceability and model management with executable and dynamic hierarchical megamodels T1 - Traceability und Modell Management mit ausführbaren und dynamischen Megamodellen N2 - Nowadays, model-driven engineering (MDE) promises to ease software development by decreasing the inherent complexity of classical software development. In order to deliver on this promise, MDE increases the level of abstraction and automation, through a consideration of domain-specific models (DSMs) and model operations (e.g. model transformations or code generations). DSMs conform to domain-specific modeling languages (DSMLs), which increase the level of abstraction, and model operations are first-class entities of software development because they increase the level of automation. Nevertheless, MDE has to deal with at least two new dimensions of complexity, which are basically caused by the increased linguistic and technological heterogeneity. The first dimension of complexity is setting up an MDE environment, an activity comprised of the implementation or selection of DSMLs and model operations. Setting up an MDE environment is both time-consuming and error-prone because of the implementation or adaptation of model operations. The second dimension of complexity is concerned with applying MDE for actual software development. Applying MDE is challenging because a collection of DSMs, which conform to potentially heterogeneous DSMLs, are required to completely specify a complex software system. A single DSML can only be used to describe a specific aspect of a software system at a certain level of abstraction and from a certain perspective. Additionally, DSMs are usually not independent but instead have inherent interdependencies, reflecting (partial) similar aspects of a software system at different levels of abstraction or from different perspectives. A subset of these dependencies are applications of various model operations, which are necessary to keep the degree of automation high. This becomes even worse when addressing the first dimension of complexity. Due to continuous changes, all kinds of dependencies, including the applications of model operations, must also be managed continuously. This comprises maintaining the existence of these dependencies and the appropriate (re-)application of model operations. The contribution of this thesis is an approach that combines traceability and model management to address the aforementioned challenges of configuring and applying MDE for software development. The approach is considered as a traceability approach because it supports capturing and automatically maintaining dependencies between DSMs. The approach is considered as a model management approach because it supports managing the automated (re-)application of heterogeneous model operations. In addition, the approach is considered as a comprehensive model management. Since the decomposition of model operations is encouraged to alleviate the first dimension of complexity, the subsequent composition of model operations is required to counteract their fragmentation. A significant portion of this thesis concerns itself with providing a method for the specification of decoupled yet still highly cohesive complex compositions of heterogeneous model operations. The approach supports two different kinds of compositions - data-flow compositions and context compositions. Data-flow composition is used to define a network of heterogeneous model operations coupled by sharing input and output DSMs alone. Context composition is related to a concept used in declarative model transformation approaches to compose individual model transformation rules (units) at any level of detail. In this thesis, context composition provides the ability to use a collection of dependencies as context for the composition of other dependencies, including model operations. In addition, the actual implementation of model operations, which are going to be composed, do not need to implement any composition concerns. The approach is realized by means of a formalism called an executable and dynamic hierarchical megamodel, based on the original idea of megamodels. This formalism supports specifying compositions of dependencies (traceability and model operations). On top of this formalism, traceability is realized by means of a localization concept, and model management by means of an execution concept. N2 - Die modellgetriebene Softwareentwicklung (MDE) verspricht heutzutage, durch das Verringern der inhärenten Komplexität der klassischen Softwareentwicklung, das Entwickeln von Software zu vereinfachen. Um dies zu erreichen, erhöht MDE das Abstraktions- und Automationsniveau durch die Einbindung domänenspezifischer Modelle (DSMs) und Modelloperationen (z.B. Modelltransformationen oder Codegenerierungen). DSMs sind konform zu domänenspezifischen Modellierungssprachen (DSMLs), die dazu dienen das Abstraktionsniveau der Softwareentwicklung zu erhöhen. Modelloperationen sind essentiell für die Softwareentwicklung da diese den Grad der Automatisierung erhöhen. Dennoch muss MDE mit Komplexitätsdimensionen umgehen die sich grundsätzlich aus der erhöhten sprachlichen und technologischen Heterogenität ergeben. Die erste Komplexitätsdimension ist das Konfigurieren einer Umgebung für MDE. Diese Aktivität setzt sich aus der Implementierung und Selektion von DSMLs sowie Modelloperationen zusammen. Eine solche Aktivität ist gerade durch die Implementierung und Anpassung von Modelloperationen zeitintensiv sowie fehleranfällig. Die zweite Komplexitätsdimension hängt mit der Anwendung von MDE für die eigentliche Softwareentwicklung zusammen. Das Anwenden von MDE ist eine Herausforderung weil eine Menge von heterogenen DSMs, die unterschiedlichen DSMLs unterliegen, erforderlich sind um ein komplexes Softwaresystem zu spezifizieren. Individuelle DSMLs werden verwendet um spezifische Aspekte eines Softwaresystems auf bestimmten Abstraktionsniveaus und aus bestimmten Perspektiven zu beschreiben. Hinzu kommt, dass DSMs sowie DSMLs grundsätzlich nicht unabhängig sind, sondern inhärente Abhängigkeiten besitzen. Diese Abhängigkeiten reflektieren äquivalente Aspekte eines Softwaresystems. Eine Teilmenge dieser Abhängigkeiten reflektieren Anwendungen diverser Modelloperationen, die notwendig sind um den Grad der Automatisierung hoch zu halten. Dies wird erschwert wenn man die erste Komplexitätsdimension hinzuzieht. Aufgrund kontinuierlicher Änderungen der DSMs, müssen alle Arten von Abhängigkeiten, inklusive die Anwendung von Modelloperationen, kontinuierlich verwaltet werden. Dies beinhaltet die Wartung dieser Abhängigkeiten und das sachgerechte (wiederholte) Anwenden von Modelloperationen. Der Beitrag dieser Arbeit ist ein Ansatz, der die Bereiche Traceability und Model Management vereint. Das Erfassen und die automatische Verwaltung von Abhängigkeiten zwischen DSMs unterstützt Traceability, während das (automatische) wiederholte Anwenden von heterogenen Modelloperationen Model Management ermöglicht. Dadurch werden die zuvor erwähnten Herausforderungen der Konfiguration und Anwendung von MDE überwunden. Die negativen Auswirkungen der ersten Komplexitätsdimension können gelindert werden indem Modelloperationen in atomare Einheiten zerlegt werden. Um der implizierten Fragmentierung entgegenzuwirken, erfordert dies allerdings eine nachfolgende Komposition der Modelloperationen. Der Ansatz wird als erweitertes Model Management betrachtet, da ein signifikanter Anteil dieser Arbeit die Kompositionen von heterogenen Modelloperationen behandelt. Unterstützt werden zwei unterschiedliche Arten von Kompositionen. Datenfluss-Kompositionen werden verwendet, um Netzwerke von heterogenen Modelloperationen zu beschreiben, die nur durch das Teilen von Ein- und Ausgabe DSMs komponiert werden. Kontext-Kompositionen bedienen sich eines Konzepts, das von deklarativen Modelltransformationen bekannt ist. Dies ermöglicht die Komposition von unabhängigen Transformationsregeln auf unterschiedlichsten Detailebenen. Die in dieser Arbeit eingeführten Kontext-Kompositionen bieten die Möglichkeit eine Menge von unterschiedlichsten Abhängigkeiten als Kontext für eine Komposition zu verwenden -- unabhängig davon ob diese Abhängigkeit eine Modelloperation repräsentiert. Zusätzlich müssen die Modelloperationen, die komponiert werden, selber keine Kompositionsaspekte implementieren, was deren Wiederverwendbarkeit erhöht. Realisiert wird dieser Ansatz durch einen Formalismus der Executable and Dynamic Hierarchical Megamodel genannt wird und auf der originalen Idee der Megamodelle basiert. Auf Basis dieses Formalismus' sind die Konzepte Traceability (hier Localization) und Model Management (hier Execution) umgesetzt. KW - Traceability KW - Modell Management KW - Megamodell KW - Modellgetriebene Entwicklung KW - Komposition KW - Traceability KW - Model Management KW - Megamodel KW - Model-Driven Engineering KW - Composition Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64222 ER - TY - BOOK A1 - Schwalb, David A1 - Krüger, Jens A1 - Plattner, Hasso T1 - Cache conscious column organization in in-memory column stores N2 - Cost models are an essential part of database systems, as they are the basis of query performance optimization. Based on predictions made by cost models, the fastest query execution plan can be chosen and executed or algorithms can be tuned and optimised. In-memory databases shifts the focus from disk to main memory accesses and CPU costs, compared to disk based systems where input and output costs dominate the overall costs and other processing costs are often neglected. However, modelling memory accesses is fundamentally different and common models do not apply anymore. This work presents a detailed parameter evaluation for the plan operators scan with equality selection, scan with range selection, positional lookup and insert in in-memory column stores. Based on this evaluation, a cost model based on cache misses for estimating the runtime of the considered plan operators using different data structures is developed. Considered are uncompressed columns, bit compressed and dictionary encoded columns with sorted and unsorted dictionaries. Furthermore, tree indices on the columns and dictionaries are discussed. Finally, partitioned columns consisting of one partition with a sorted and one with an unsorted dictionary are investigated. New values are inserted in the unsorted dictionary partition and moved periodically by a merge process to the sorted partition. An efficient attribute merge algorithm is described, supporting the update performance required to run enterprise applications on read-optimised databases. Further, a memory traffic based cost model for the merge process is provided. N2 - Kostenmodelle sind ein essentieller Teil von Datenbanksystemen und bilden die Basis für Optimierungen von Ausführungsplänen. Durch Abschätzungen der Kosten können die entsprechend schnellsten Operatoren und Algorithmen zur Abarbeitung einer Anfrage ausgewählt und ausgeführt werden. Hauptspeicherresidente Datenbanken verschieben den Fokus von I/O Operationen hin zu Zugriffen auf den Hauptspeicher und CPU Kosten, verglichen zu Datenbanken deren primäre Kopie der Daten auf Sekundärspeicher liegt und deren Kostenmodelle sich in der Regel auf die kostendominierenden Zugriffe auf das Sekundärmedium beschränken. Kostenmodelle für Zugriffe auf Hauptspeicher unterscheiden sich jedoch fundamental von Kostenmodellen für Systeme basierend auf Festplatten, so dass alte Modelle nicht mehr greifen. Diese Arbeit präsentiert eine detaillierte Parameterdiskussion, sowie ein Kostenmodell basierend auf Cache-Zugriffen zum Abschätzen der Laufzeit von Datenbankoperatoren in spaltenorientierten und hauptspeicherresidenten Datenbanken wie das Selektieren von Werten einer Spalte mittels einer Gleichheitsbedingung oder eines Wertebereichs, das Nachschlagen der Werte einzelner Positionen oder dem Hinzufügen neuer Werte. Dabei werden Kostenfunktionen für die Operatoren erstellt, welche auf unkomprimierten Spalten, mittels Substitutionskompression komprimierten Spalten sowie bit-komprimierten Spalten operieren. Des Weiteren werden Baumstrukturen als Index Strukturen auf Spalten und Wörterbüchern in die Betrachtung gezogen. Abschließend werden partitionierte Spalten eingeführt, welche aus einer lese- und einer schreib-optimierten Partition bestehen. Neu Werte werden in die schreiboptimierte Partition eingefügt und periodisch von einem Attribut-Merge-Prozess mit der leseoptimierten Partition zusammengeführt. Beschrieben wird eine Effiziente Implementierung für den Attribut-Merge-Prozess und ein Hauptspeicher-bandbreitenbasiertes Kostenmodell aufgestellt. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 67 KW - Hauptspeicherdatenbank KW - Datenbank-Kostenmodell KW - Attribut-Merge-Prozess KW - In-Memory Database KW - Database Cost Model KW - Attribute Merge Process Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-63890 SN - 978-3-86956-228-5 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - BOOK A1 - Vogel, Thomas A1 - Giese, Holger T1 - Model-driven engineering of adaptation engines for self-adaptive software : executable runtime megamodels N2 - The development of self-adaptive software requires the engineering of an adaptation engine that controls and adapts the underlying adaptable software by means of feedback loops. The adaptation engine often describes the adaptation by using runtime models representing relevant aspects of the adaptable software and particular activities such as analysis and planning that operate on these runtime models. To systematically address the interplay between runtime models and adaptation activities in adaptation engines, runtime megamodels have been proposed for self-adaptive software. A runtime megamodel is a specific runtime model whose elements are runtime models and adaptation activities. Thus, a megamodel captures the interplay between multiple models and between models and activities as well as the activation of the activities. In this article, we go one step further and present a modeling language for ExecUtable RuntimE MegAmodels (EUREMA) that considerably eases the development of adaptation engines by following a model-driven engineering approach. We provide a domain-specific modeling language and a runtime interpreter for adaptation engines, in particular for feedback loops. Megamodels are kept explicit and alive at runtime and by interpreting them, they are directly executed to run feedback loops. Additionally, they can be dynamically adjusted to adapt feedback loops. Thus, EUREMA supports development by making feedback loops, their runtime models, and adaptation activities explicit at a higher level of abstraction. Moreover, it enables complex solutions where multiple feedback loops interact or even operate on top of each other. Finally, it leverages the co-existence of self-adaptation and off-line adaptation for evolution. N2 - Die Entwicklung selbst-adaptiver Software erfordert die Konstruktion einer sogenannten "Adaptation Engine", die mittels Feedbackschleifen die unterliegende Software steuert und anpasst. Die Anpassung selbst wird häufig mittels Laufzeitmodellen, die die laufende Software repräsentieren, und Aktivitäten wie beispielsweise Analyse und Planung, die diese Laufzeitmodelle nutzen, beschrieben. Um das Zusammenspiel zwischen Laufzeitmodellen und Aktivitäten systematisch zu erfassen, wurden Megamodelle zur Laufzeit für selbst-adaptive Software vorgeschlagen. Ein Megamodell zur Laufzeit ist ein spezielles Laufzeitmodell, dessen Elemente Aktivitäten und andere Laufzeitmodelle sind. Folglich erfasst ein Megamodell das Zusammenspiel zwischen verschiedenen Laufzeitmodellen und zwischen Aktivitäten und Laufzeitmodellen als auch die Aktivierung und Ausführung der Aktivitäten. Darauf aufbauend präsentieren wir in diesem Artikel eine Modellierungssprache für ausführbare Megamodelle zur Laufzeit, EUREMA genannt, die aufgrund eines modellgetriebenen Ansatzes die Entwicklung selbst-adaptiver Software erleichtert. Der Ansatz umfasst eine domänen-spezifische Modellierungssprache und einen Laufzeit-Interpreter für Adaptation Engines, insbesondere für Feedbackschleifen. EUREMA Megamodelle werden über die Spezifikationsphase hinaus explizit zur Laufzeit genutzt, um mittels Interpreter Feedbackschleifen direkt auszuführen. Zusätzlich können Megamodelle zur Laufzeit dynamisch geändert werden, um Feedbackschleifen anzupassen. Daher unterstützt EUREMA die Entwicklung selbst-adaptiver Software durch die explizite Spezifikation von Feedbackschleifen, der verwendeten Laufzeitmodelle, und Adaptionsaktivitäten auf einer höheren Abstraktionsebene. Darüber hinaus ermöglicht EUREMA komplexe Lösungskonzepte, die mehrere Feedbackschleifen und deren Interaktion wie auch die hierarchische Komposition von Feedbackschleifen umfassen. Dies unterstützt schließlich das integrierte Zusammenspiel von Selbst-Adaption und Wartung für die Evolution der Software. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 66 KW - Modellgetriebene Softwareentwicklung KW - Modellierungssprachen KW - Modellierung KW - Laufzeitmodelle KW - Megamodell KW - Ausführung von Modellen KW - Model-Driven Engineering KW - Modeling Languages KW - Modeling KW - Models at Runtime KW - Megamodels KW - Model Execution KW - Self-Adaptive Software Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-63825 SN - 978-3-86956-227-8 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Heinisch, Isabelle A1 - Romeike, Ralf T1 - Outcome-orientierte Neuausrichtung in der Hochschullehre Informatik BT - Konzeption, Umsetzung und Erfahrungen JF - Commentarii informaticae didacticae : (CID) N2 - Die Orientierung am Outcome eines Lernprozesses stellt einen wichtigen Pfeiler einer kompetenzorientierten Informatiklehre dar. Im Beitrag werden Konzeption und Erfahrungen eines Projekts zur outcome-orientierten Neuausrichtung der Informatiklehre unter Berücksichtigung der Theorie des Constructive Alignment beschrieben. Nach der theoretischen Fundierung der Kompetenzproblematik wird anhand eines Formulierungsmodells ein Prozess zur Erarbeitung beobachtbarer Lernergebnisse dargestellt. Die Diskussion der Projektziele und Erfahrungen in der Umsetzung und Evaluierung unterstreichen die Chancen und Herausforderungen für eine Steigerung der Studienqualität. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64831 SN - 1868-0844 SN - 2191-1940 IS - 5 SP - 9 EP - 20 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Holz, Jan A1 - Berger, Nadine A1 - Schroeder, Ulrike T1 - Anwendungsorientierte Gestaltung eines Informatik-Vorkurses als Studienmotivator JF - Commentarii informaticae didacticae : (CID) N2 - Zur Unterstützung von Studierenden in der Studieneingangsphase wurde an der RWTH Aachen ein neuartiger und motivierender Einstieg in den Vorkurs Informatik entwickelt und zum Wintersemester 2011/12 erprobt. Dabei wurde die grafische Programmierung mittels App Inventor eingeführt, die zur Umsetzung anwendungsbezogener Projekte genutzt wurde. In diesem Beitrag werden die Motivation für die Neugestaltung, das Konzept und die Evaluation des Testlaufs beschrieben. Diese dienen als Grundlage für eine vollständige Neukonzeption des Vorkurses für das Wintersemester 2012/2013. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64871 SN - 1868-0844 SN - 2191-1940 IS - 5 SP - 56 EP - 66 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - BOOK A1 - Beyhl, Thomas A1 - Blouin, Dominique A1 - Giese, Holger A1 - Lambers, Leen T1 - On the operationalization of graph queries with generalized discrimination networks N2 - Graph queries have lately gained increased interest due to application areas such as social networks, biological networks, or model queries. For the relational database case the relational algebra and generalized discrimination networks have been studied to find appropriate decompositions into subqueries and ordering of these subqueries for query evaluation or incremental updates of query results. For graph database queries however there is no formal underpinning yet that allows us to find such suitable operationalizations. Consequently, we suggest a simple operational concept for the decomposition of arbitrary complex queries into simpler subqueries and the ordering of these subqueries in form of generalized discrimination networks for graph queries inspired by the relational case. The approach employs graph transformation rules for the nodes of the network and thus we can employ the underlying theory. We further show that the proposed generalized discrimination networks have the same expressive power as nested graph conditions. N2 - Graph-basierte Suchanfragen erfahren in jüngster Zeit ein zunehmendes Interesse durch Anwendungsdomänen wie zum Beispiel Soziale Netzwerke, biologische Netzwerke und Softwaremodelle. Für relationale Datenbanken wurden die relationale Algebra und sogenannte generalisierte Discrimination Networks bereits studiert um Suchanfragen angemessen in kleinere Suchanfragen für die inkrementelle Auswertung zu zerlegen und zu ordnen. Allerdings gibt es für Graphdatenbanken derzeit keine formale Grundlage, die es erlaubt solche Zerlegungen zu finden. Daher schlagen wir ein Konzept für die Zerlegung und Ordnung von komplexen Suchanfragen vor. Das Konzept basiert auf generalisierten Discrimination Networks, die aus relationalen Datenbanken bekannt sind. Der Ansatz verwendet Graphtransformationsregeln für Knoten in diesen Netzwerken, sodass die Theorie von Graphen und Graphtransformationen angewendet werden kann. Darüber hinaus zeigen wir auf, dass diese Discrimination Networks die gleiche Ausdrucksstärke besitzen wie Nested Graph Conditions. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 106 KW - graph queries KW - discrimination networks KW - incremental graph pattern matching KW - nested graph conditions KW - Graph-basierte Suche KW - Discrimination Networks KW - Inkrementelle Graphmustersuche KW - Nested Graph Conditions Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-96279 SN - 978-3-86956-372-5 SN - 1613-5652 SN - 2191-1665 IS - 106 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - INPR A1 - Grapentin, Andreas A1 - Heidler, Kirstin A1 - Korsch, Dimitri A1 - Kumar Sah, Rakesh A1 - Kunzmann, Nicco A1 - Henning, Johannes A1 - Mattis, Toni A1 - Rein, Patrick A1 - Seckler, Eric A1 - Groneberg, Björn A1 - Zimmermann, Florian ED - Hentschel, Uwe ED - Richter, Daniel ED - Polze, Andreas T1 - Embedded operating system projects N2 - In today’s life, embedded systems are ubiquitous. But they differ from traditional desktop systems in many aspects – these include predictable timing behavior (real-time), the management of scarce resources (memory, network), reliable communication protocols, energy management, special purpose user-interfaces (headless operation), system configuration, programming languages (to support software/hardware co-design), and modeling techniques. Within this technical report, authors present results from the lecture “Operating Systems for Embedded Computing” that has been offered by the “Operating Systems and Middleware” group at HPI in Winter term 2013/14. Focus of the lecture and accompanying projects was on principles of real-time computing. Students had the chance to gather practical experience with a number of different OSes and applications and present experiences with near-hardware programming. Projects address the entire spectrum, from bare-metal programming to harnessing a real-time OS to exercising the full software/hardware co-design cycle. Three outstanding projects are at the heart of this technical report. Project 1 focuses on the development of a bare-metal operating system for LEGO Mindstorms EV3. While still a toy, it comes with a powerful ARM processor, 64 MB of main memory, standard interfaces, such as Bluetooth and network protocol stacks. EV3 runs a version of 1 1 Introduction Linux. Sources are available from Lego’s web site. However, many devices and their driver software are proprietary and not well documented. Developing a new, bare-metal OS for the EV3 requires an understanding of the EV3 boot process. Since no standard input/output devices are available, initial debugging steps are tedious. After managing these initial steps, the project was able to adapt device drivers for a few Lego devices to an extent that a demonstrator (the Segway application) could be successfully run on the new OS. Project 2 looks at the EV3 from a different angle. The EV3 is running a pretty decent version of Linux- in principle, the RT_PREEMPT patch can turn any Linux system into a real-time OS by modifying the behavior of a number of synchronization constructs at the heart of the OS. Priority inversion is a problem that is solved by protocols such as priority inheritance or priority ceiling. Real-time OSes implement at least one of the protocols. The central idea of the project was the comparison of non-real-time and real-time variants of Linux on the EV3 hardware. A task set that showed effects of priority inversion on standard EV3 Linux would operate flawlessly on the Linux version with the RT_PREEMPT-patch applied. If only patching Lego’s version of Linux was that easy... Project 3 takes the notion of real-time computing more seriously. The application scenario was centered around our Carrera Digital 132 racetrack. Obtaining position information from the track, controlling individual cars, detecting and modifying the Carrera Digital protocol required design and implementation of custom controller hardware. What to implement in hardware, firmware, and what to implement in application software – this was the central question addressed by the project. N2 - Heutzutage sind eingebettete Systeme allgegenwärtig. Allerdings unterscheiden sie sich in vielen Aspekten von traditionellen Desktop-System – dazu gehören vorhersagbares Zeitverhalten („Echtzeit“), die Verwaltung von knappen Ressourcen (Speicher, Netzwerk), zuverlässige Kommunikationsprotokolle, Energiemanagement, spezialisierte Benutzungsschnittstellen („headless“), Systemkonfiguration, Programmiersprachen (zur Unterstützung von Software-Hardware-Co-Design) und Modellierungstechniken. In diesem technischen Bericht präsentieren die Autoren Ergebnisse aus der Vorlesung „Betriebssysteme für Embedded Computing“, die von der Fachgruppe „Betriebssysteme und Middleware“ am HPI in Wintersemester 2013/14 angeboten wurde. Schwerpunkte der Vorlesung und der begleitenden Projekte waren Prinzipien von Echtzeit-Computing. Die Studenten hatten die Möglichkeit, praktische Erfahrungen mit einer Reihe von verschiedenen Betriebssystemen und Anwendungen zu sammeln und präsentieren ihre Erfahrungen mit hardwarenaher Programmierung. Die Projekte adressieren das gesamte Spektrum von der Bare-Metal-Programmierung über die Nutzung eines Echtzeitbetriebssystem bis zur Anwendung des vollen Software-Hardware-Co-Design-Zyklus‘. Drei herausragende Projekte sind das Herzstück dieses technischen Berichts. Projekt 1 konzentriert sich auf die Entwicklung eines Bare-Metal-Betriebssystems für LEGO Mindstorms EV3. Obwohl es ein Spielzeug ist, kommt es mit einem leistungsstarken ARM-Prozessor, 64 MB Hauptspeicher und Standardschnittstellen wie Bluetooth und einem Netzwerkprotokollstapel. Auf dem EV3 läuft spezielle Linux-Version – die Quellen sind auf der Lego-Website verfügbar. Allerdings sind viele Geräte und deren Treiber-Software urheberrechtlich geschützt und nicht gut dokumentiert. Die Entwicklung eines neuen Bare-Metal-Betriebssystem für den EV3 erfordert ein Verständnis des EV3-Bootvorgangs. Da keine Standard-Ein-/Ausgabegeräte zur Verfügung stehen, sind anfängliche Debug-Schritte mühsam. Nach dem Absolvieren dieser ersten Schritte war das Projekt in der Lage, Gerätetreiber für einige Lego-Geräte anzupassen um einen Demonstrator (die Segway-Anwendung) erfolgreich auf dem neuen Betriebssystem laufen zu lassen. Projekt 2 befasst sich mit dem EV3 aus einer anderen Perspektive. Der EV3 wird mit einer üblichen EV3 Linux-Version betrieben – im Prinzip kann der RT_PREEMPT-Patch jedes Linux-System in ein Echtzeitbetriebssystem verwandeln, indem er das Verhalten einer Anzahl von Synchronisationskonstrukten im Herzen des Betriebssystems anpasst. Priority Inversion ist ein Problem, das durch Protokolle wie Prioritätsvererbung oder Priority Ceiling gelöst wird. Heutige Echtzeit-Betriebssysteme implementieren mindestens eines dieser Protokolle. Die zentrale Idee des Projekts war der Vergleich der Nicht-Echtzeit und Echtzeit-Varianten von Linux auf der EV3-Hardware. Ein Task-Set, das die Auswirkungen der Prioritätsumkehr auf Standard-EV3 Linux zeigt, würde ohne Probleme auf der Linux-Version mit dem RT_PREEMPT-Patch betrieben werden können. Wenn nur das Patchen Lego-Version von Linux war so einfach wäre... Projekt 3 nimmt den Begriff des Echtzeit-Computing ernst. Das Anwendungsszenario wurde um unsere Carrera Digital 132 Bahn angeordnet. Das Sammeln von Positionsinformationen, die Steuerung einzelner Fahrzeuge, die Erfassung und Änderung des Carrera Digital-Protokolls erfordert die Konzeption und Umsetzung von spezialisierter Controller-Hardware. Die zentrale Fragestellung dieses Projekts war, was in Hardware, in Firmware oder in der Anwendungssoftware zu implementieren ist. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 90 KW - Echtzeit KW - eingebettete Systeme KW - Betriebssysteme KW - Erfahrungsbericht KW - LEGO Mindstorms EV3 KW - RT_PREEMT-Patch KW - Carrera Digital D132 KW - real-time KW - embedded systems KW - operating systems KW - experience report KW - LEGO Mindstorms EV3 KW - RT_PREEMT patch KW - Carrera Digital D132 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-69154 SN - 978-3-86956-296-4 SN - 1613-5652 SN - 2191-1665 IS - 90 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - THES A1 - Polyvyanyy, Artem T1 - Structuring process models T1 - Strukturierung von Prozessmodellen N2 - One can fairly adopt the ideas of Donald E. Knuth to conclude that process modeling is both a science and an art. Process modeling does have an aesthetic sense. Similar to composing an opera or writing a novel, process modeling is carried out by humans who undergo creative practices when engineering a process model. Therefore, the very same process can be modeled in a myriad number of ways. Once modeled, processes can be analyzed by employing scientific methods. Usually, process models are formalized as directed graphs, with nodes representing tasks and decisions, and directed arcs describing temporal constraints between the nodes. Common process definition languages, such as Business Process Model and Notation (BPMN) and Event-driven Process Chain (EPC) allow process analysts to define models with arbitrary complex topologies. The absence of structural constraints supports creativity and productivity, as there is no need to force ideas into a limited amount of available structural patterns. Nevertheless, it is often preferable that models follow certain structural rules. A well-known structural property of process models is (well-)structuredness. A process model is (well-)structured if and only if every node with multiple outgoing arcs (a split) has a corresponding node with multiple incoming arcs (a join), and vice versa, such that the set of nodes between the split and the join induces a single-entry-single-exit (SESE) region; otherwise the process model is unstructured. The motivations for well-structured process models are manifold: (i) Well-structured process models are easier to layout for visual representation as their formalizations are planar graphs. (ii) Well-structured process models are easier to comprehend by humans. (iii) Well-structured process models tend to have fewer errors than unstructured ones and it is less probable to introduce new errors when modifying a well-structured process model. (iv) Well-structured process models are better suited for analysis with many existing formal techniques applicable only for well-structured process models. (v) Well-structured process models are better suited for efficient execution and optimization, e.g., when discovering independent regions of a process model that can be executed concurrently. Consequently, there are process modeling languages that encourage well-structured modeling, e.g., Business Process Execution Language (BPEL) and ADEPT. However, the well-structured process modeling implies some limitations: (i) There exist processes that cannot be formalized as well-structured process models. (ii) There exist processes that when formalized as well-structured process models require a considerable duplication of modeling constructs. Rather than expecting well-structured modeling from start, we advocate for the absence of structural constraints when modeling. Afterwards, automated methods can suggest, upon request and whenever possible, alternative formalizations that are "better" structured, preferably well-structured. In this thesis, we study the problem of automatically transforming process models into equivalent well-structured models. The developed transformations are performed under a strong notion of behavioral equivalence which preserves concurrency. The findings are implemented in a tool, which is publicly available. N2 - Im Sinne der Ideen von Donald E. Knuth ist die Prozessmodellierung sowohl Wissenschaft als auch Kunst. Prozessmodellierung hat immer auch eine ästhetische Dimension. Wie das Komponieren einer Oper oder das Schreiben eines Romans, so stellt auch die Prozessmodellierung einen kreativen Akt eines Individuums dar. Somit kann ein Prozess auf unterschiedlichste Weise modelliert werden. Prozessmodelle können anschließend mit wissenschaftlichen Methoden untersucht werden. Prozessmodelle liegen im Regelfall als gerichtete Graphen vor. Knoten stellen Aktivitäten und Entscheidungspunkte dar, während gerichtete Kanten die temporalen Abhängigkeiten zwischen den Knoten beschreiben. Gängige Prozessmodellierungssprachen, zum Beispiel die Business Process Model and Notation (BPMN) und Ereignisgesteuerte Prozessketten (EPK), ermöglichen die Erstellung von Modellen mit einer beliebig komplexen Topologie. Es gibt keine strukturellen Einschränkungen, welche die Kreativität oder Produktivität durch eine begrenzte Anzahl von Modellierungsalternativen einschränken würden. Nichtsdestotrotz ist es oft wünschenswert, dass Modelle bestimmte strukturelle Eigenschaften haben. Ein bekanntes strukturelles Merkmal für Prozessmodelle ist Wohlstrukturiertheit. Ein Prozessmodell ist wohlstrukturiert genau dann, wenn jeder Knoten mit mehreren ausgehenden Kanten (ein Split) einen entsprechenden Knoten mit mehreren eingehenden Kanten (einen Join) hat, und umgekehrt, so dass die Knoten welche zwischen dem Split und dem Join liegen eine single-entry-single-exit (SESE) Region bilden. Ist dies nicht der Fall, so ist das Modell unstrukturiert. Wohlstrukturiertheit ist aufgrund einer Vielzahl von Gründen wünschenswert: (i) Wohlstrukturierte Modelle sind einfacher auszurichten, wenn sie visualisiert werden, da sie planaren Graphen entsprechen. (ii) Wohlstrukturierte Modelle zeichnen sich durch eine höhere Verständlichkeit aus. (iii) Wohlstrukturierte Modelle haben oft weniger Fehler als unstrukturierte Modelle. Auch ist die Wahrscheinlichkeit fehlerhafter Änderungen größer, wenn Modelle unstrukturiert sind. (iv) Wohlstrukturierte Modelle eignen sich besser für die formale Analyse, da viele Techniken nur für wohlstrukturierte Modelle anwendbar sind. (v) Wohlstrukturierte Modelle sind eher für die effiziente Ausführung und Optimierung geeignet, z.B. wenn unabhängige Regionen eines Prozesses für die parallele Ausführung identifiziert werden. Folglich gibt es eine Reihe von Prozessmodellierungssprachen, z.B. die Business Process Execution Language (BPEL) und ADEPT, welche den Modellierer anhalten nur wohlstrukturierte Modelle zu erstellen. Solch wohlstrukturiertes Modellieren impliziert jedoch gewisse Einschränkungen: (i) Es gibt Prozesse, welche nicht mittels wohlstrukturierten Prozessmodellen dargestellt werden können. (ii) Es gibt Prozesse, für welche die wohlstrukturierte Modellierung mit einer erheblichen Vervielfältigung von Modellierungs-konstrukten einhergeht. Aus diesem Grund vertritt diese Arbeit den Standpunkt, dass ohne strukturelle Einschränkungen modelliert werden sollte, anstatt Wohlstrukturiertheit von Beginn an zu verlangen. Anschließend können, sofern gewünscht und wo immer es möglich ist, automatische Methoden Modellierungsalternativen vorschlagen, welche "besser" strukturiert sind, im Idealfall sogar wohlstrukturiert. Die vorliegende Arbeit widmet sich dem Problem der automatischen Transformation von Prozessmodellen in verhaltensäquivalente wohlstrukturierte Prozessmodelle. Die vorgestellten Transformationen erhalten ein strenges Verhaltensequivalenzkriterium, welches die Parallelität wahrt. Die Resultate sind in einem frei verfügbaren Forschungsprototyp implementiert worden. KW - Strukturierung KW - Wohlstrukturiertheit KW - Prozesse KW - Verhalten KW - Modellierung KW - Structuring KW - Well-structuredness KW - Process KW - Behavior KW - Modeling Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-59024 ER - TY - THES A1 - Meier, Sebastian T1 - Personal Big Data T1 - Personal Big Data BT - a privacy-centred selective cloud computing approach to progressive user modelling on mobile devices BT - ein mit dem Schwerpunkt auf Privatsphäre entwickelter selektiver Cloud-Computing Ansatz zur fortschreitenden Modellierung von Nutzerverhalten auf mobilen Endgeräten N2 - Many users of cloud-based services are concerned about questions of data privacy. At the same time, they want to benefit from smart data-driven services, which require insight into a person’s individual behaviour. The modus operandi of user modelling is that data is sent to a remote server where the model is constructed and merged with other users’ data. This thesis proposes selective cloud computing, an alternative approach, in which the user model is constructed on the client-side and only an abstracted generalised version of the model is shared with the remote services. In order to demonstrate the applicability of this approach, the thesis builds an exemplary client-side user modelling technique. As this thesis is carried out in the area of Geoinformatics and spatio-temporal data is particularly sensitive, the application domain for this experiment is the analysis and prediction of a user’s spatio-temporal behaviour. The user modelling technique is grounded in an innovative conceptual model, which builds upon spatial network theory combined with time-geography. The spatio-temporal constraints of time-geography are applied to the network structure in order to create individual spatio-temporal action spaces. This concept is translated into a novel algorithmic user modelling approach which is solely driven by the user’s own spatio-temporal trajectory data that is generated by the user’s smartphone. While modern smartphones offer a rich variety of sensory data, this thesis only makes use of spatio-temporal trajectory data, enriched by activity classification, as the input and foundation for the algorithmic model. The algorithmic model consists of three basal components: locations (vertices), trips (edges), and clusters (neighbourhoods). After preprocessing the incoming trajectory data in order to identify locations, user feedback is used to train an artificial neural network to learn temporal patterns for certain location types (e.g. work, home, bus stop, etc.). This Artificial Neural Network (ANN) is used to automatically detect future location types by their spatio-temporal patterns. The same is done in order to predict the duration of stay at a certain location. Experiments revealed that neural nets were the most successful statistical and machine learning tool to detect those patterns. The location type identification algorithm reached an accuracy of 87.69%, the duration prediction on binned data was less successful and deviated by an average of 0.69 bins. A challenge for the location type classification, as well as for the subsequent components, was the imbalance of trips and connections as well as the low accuracy of the trajectory data. The imbalance is grounded in the fact that most users exhibit strong habitual patterns (e.g. home > work), while other patterns are rather rare by comparison. The accuracy problem derives from the energy-saving location sampling mode, which creates less accurate results. Those locations are then used to build a network that represents the user’s spatio-temporal behaviour. An initial untrained ANN to predict movement on the network only reached 46% average accuracy. Only lowering the number of included edges, focusing on more common trips, increased the performance. In order to further improve the algorithm, the spatial trajectories were introduced into the predictions. To overcome the accuracy problem, trips between locations were clustered into so-called spatial corridors, which were intersected with the user’s current trajectory. The resulting intersected trips were ranked through a k-nearest-neighbour algorithm. This increased the performance to 56%. In a final step, a combination of a network and spatial clustering algorithm was built in order to create clusters, therein reducing the variety of possible trips. By only predicting the destination cluster instead of the exact location, it is possible to increase the performance to 75% including all classes. A final set of components shows in two exemplary ways how to deduce additional inferences from the underlying spatio-temporal data. The first example presents a novel concept for predicting the ‘potential memorisation index’ for a certain location. The index is based on a cognitive model which derives the index from the user’s activity data in that area. The second example embeds each location in its urban fabric and thereby enriches its cluster’s metadata by further describing the temporal-semantic activity in an area (e.g. going to restaurants at noon). The success of the client-side classification and prediction approach, despite the challenges of inaccurate and imbalanced data, supports the claimed benefits of the client-side modelling concept. Since modern data-driven services at some point do need to receive user data, the thesis’ computational model concludes with a concept for applying generalisation to semantic, temporal, and spatial data before sharing it with the remote service in order to comply with the overall goal to improve data privacy. In this context, the potentials of ensemble training (in regards to ANNs) are discussed in order to highlight the potential of only sharing the trained ANN instead of the raw input data. While the results of our evaluation support the assets of the proposed framework, there are two important downsides of our approach compared to server-side modelling. First, both of these server-side advantages are rooted in the server’s access to multiple users’ data. This allows a remote service to predict spatio-in the user-specific data, which represents the second downside. While minor classes will likely be minor classes in a bigger dataset as well, for each class, there will still be more variety than in the user-specific dataset. The author emphasises that the approach presented in this work holds the potential to change the privacy paradigm in modern data-driven services. Finding combinations of client- and server-side modelling could prove a promising new path for data-driven innovation. Beyond the technological perspective, throughout the thesis the author also offers a critical view on the data- and technology-driven development of this work. By introducing the client-side modelling with user-specific artificial neural networks, users generate their own algorithm. Those user-specific algorithms are influenced less by generalised biases or developers’ prejudices. Therefore, the user develops a more diverse and individual perspective through his or her user model. This concept picks up the idea of critical cartography, which questions the status quo of how space is perceived and represented. N2 - Die Nutzung von modernen digitalen Diensten und Cloud-Services geht häufig einher mit einer Besorgtheit um die Sicherheit der eigenen Privatsphäre. Gleichzeitig zeigt sich, dass die Nutzung eben dieser Dienste nicht rückläufig ist. Dieses Phänomen wird in der Wissenschaft auch als Privacy-Paradox bezeichnet (Barnes, 2006). Viele digitale Dienste bauen einen Großteil ihrer Funktionalitäten auf NutzerInnendaten auf. Der Modus Operandi bei diesen Diensten ist bisher, die Daten der NutzerInnen an einen Server zu schicken, wo diese verarbeitet, analysiert und gespeichert werden. Die vorliegende Doktorarbeit schlägt ein alternatives Konzept vor: Selective Cloud Computing. Kern dieses Konzeptes ist die Verlagerung der NutzerInnen-Modellierung auf die privaten Endgeräte, wodurch für weitere Services nur ein abstrahiertes Daten- und NutzerInnenmodel mit den externen Diensten geteilt wird. Um dieses Konzept auf seine Machbarkeit und Performanz zu überprüfen wird im Rahmen dieser Arbeit ein beispielhafter Prozess für die nutzerInnenseitige Modellierung von raumzeitlichen Informationen entwickelt. Da raumzeitliche Informationen mit zu den sensibelsten persönlichen Daten gehören, bietet die Verortung der vorliegende Arbeit im Bereich der Geoinformatik für das Anwendungsfeld der NutzerInnen-Modellierung einen passenden disziplinären Rahmen. Die NutzerInnen-Modellierung fußt auf einem innovativen konzeptuellen Modell, welches Theorien zu räumlichen Netzwerken und Hägerstrands Theorie der Zeitgeographie miteinander kombiniert (Hägerstrand, 1970). Hierbei werden die von Hägerstrand entwickelten raumzeitlichen Einschränkungen (Constraints) auf das Netzwerkmodel übertragen, wodurch individuelle Aktionsräume konstituiert werden. Dieses Model wird schließlich in ein algorithmisches Computermodel übersetzt, dessen Operationen ausschließlich die Daten verarbeiten und nutzen, die auf den Smartphones der NutzerInnen generiert werden. Moderne Smartphones bieten für die Datengenerierung gute Voraussetzungen, da sie den Zugriff auf eine ganze Bandbreite an Sensoren und anderen Datenquellen ermöglich. Die vorliegende Arbeit beschränkt sich dabei jedoch auf die raumzeitlichen Informationen, welche über die Ortungsfunktionen des Geräts produziert werden (Trajectories). Die Trajektorien werden angereichert durch Aktivitätsklassifikationen (z.B. Laufen, Radfahren, etc.), welche von der App, die diese Daten aufzeichnet, zugeordnet werden. Das Computermodel basiert auf diesen Daten und gliedert diese in drei grundlegende Komponenten: 1) Orte (Knotenpunkte) 2) Trips (Kanten) und 3) Cluster (Nachbarschaften). Zu Beginn der algorithmischen Verarbeitung werden die eingehenden Daten optimiert und analysiert, um in einem ersten Schritt geographische Orte zu identifizieren. Um diese Orte nun mit semantischen Informationen anzureichern wird ein automatisierter Algorithmus über User-Feedback trainiert, welcher die Orts-Typen selbstständig erkennt (z.B. Zuhause, Arbeitsplatz, Haltestelle). Der Algorithmus basiert auf einem künstlichen neuronalen Netz, welches versucht, Muster in den Daten zu erkennen. Die Entscheidung, neuronale Netze in diesem Prozess einzusetzen, ergab sich aus einer Evaluation verschiedener Verfahren der statistischen Klassifizierung und des maschinellen Lernens. Das Verfahren zur Erkennung der Orts-Typen erreichte unter Zuhilfenahme eines künstlichen neuronalen Netz eine Genauigkeit von 87.69% und war damit das akkurateste. Eine weitere Einsatzmöglichkeit solcher neuronalen Netze ist bei der Vorhersage von Aufenthaltsdauern an bestimmten Orten, welche im Durschnitt 0.69 Klassen vom korrekten Ergebnis abwich. Eine große Herausforderung für alle Module war sowohl die Ungenauigkeit der Rohdaten, also auch die ungleichmäßige Verteilung der Daten. Die Ungenauigkeit ist ein Resultat der Generierung der Positionsinformationen, welche zugunsten eines geringeren Energieverbrauchs der mobilen Geräte Ungenauigkeiten in Kauf nehmen muss. Die ungleichmäßige Verteilung ergibt sich wiederum durch häufig wiederkehrende Muster (z.B. Fahrten zur Arbeit und nach Hause), welche im Vergleich zu anderen Aktivitäten vergleichsweise häufig auftreten und die Datensätze dominieren. Die Orte, die in der ersten Phase identifiziert und klassifiziert wurden, werden im nächsten Schritt für die Konstruktion des eigentlichen räumlichen Netzwerks genutzt. Basierend auf den über einen bestimmten Zeitraum gesammelten Daten der NutzerInnen und im Rückgriff auf Hägerstrands Einschränkungsprinzip werden Vorhersagen über mögliche raumzeitliche Verhaltensweisen im nutzerspezifischen Netzwerk gemacht. Hierzu werden Methoden des maschinellen Lernens, in diesem Fall künstliche neuronale Netze und Nächste-Nachbarn-Klassifikation (k-nearest-neighbour), mit Methoden der Trajektorien-Analyse kombiniert. Die zugrundeliegenden Orts- und Bewegungsinformationen werden unter Anwendung von Netzwerk-Nachbarschafts-Methoden und klassischen räumlichen Gruppierungsmethoden (Clustering) für die Optimierung der Algorithmen verfeinert. Die aus diesen Schritten resultierende Methodik erreichte eine Genauigkeit von 75% bei der Vorhersage über raumzeitliches Verhalten. Wenn man Vorhersagen mit einbezieht, bei denen der korrekte Treffer auf Rang 2 und 3 der Nächste-Nachbarn-Klassifikation liegt, erreichte die Methodik sogar eine Vorhersagen-Genauigkeit von 90%. Um zu erproben, welche weiteren Schlussfolgerungen über die NutzerInnen basierend auf den zugrundeliegenden Daten getroffen werden könnten, werden abschließend zwei beispielhafte Methoden entwickelt und getestet: zum einen werden die Trajektorien genutzt um vorherzusagen, wie gut eine NutzerIn ein bestimmtes Gebiet kennt (Potential Memorisation Index). Zum anderen werden zeitlich-semantische Muster für Orts-Cluster extrahiert und darauf basierend berechnet, wann welche Aktivitäten und spezifischen Orte innerhalb eines Clusters für die NutzerIn potenziell von Interesse sind. Trotz der Herausforderungen, die mit den unausgeglichenen Datensätzen und teilweise fehlerhaften Daten einhergehen, spricht die dennoch vergleichsweise hohe Präzision der nutzerseitigen Klassifizierungs- und Vorhersagemethoden für den in dieser Arbeit vorgestellten Ansatz der nutzerseitigen Modellierung. In einem letzten Schritt kontextualisiert die vorliegende Arbeit die erstellten Ansätze in einem realweltlichen Anwendungsfall und diskutiert den Austausch der generierten Daten mit einem datengestützten Dienst. Hierzu wird das Konzept der Generalisierung genutzt, um im Sinne des Schutzes der Privatsphäre abstrahierte Daten mit einem Dienst zu teilen. Obgleich der positiven Ergebnisse der Tests gibt es auch klare Nachteile im Vergleich zur klassischen serverseitigen Modellierung, die unter Einbezug mehrerer aggregierter NutzerInnenprofile stattfindet. Hierzu zählt zum einen, dass unterrepräsentierte Klassen in den Daten schlechter identifiziert werden können. Zum anderen ergibt sich der Nachteil, dass nur Verhaltensweisen erkannt werden können, die bereits zuvor von der NutzerIn selber ausgeübt wurden und somit in den Daten bereits enthalten sind. Im Vergleich dazu besteht bei serverseitiger Modellierung auf der Basis zahlreicher Personenprofile der Zugriff auf ein breiteres Spektrum an Verhaltensmustern und somit die Möglichkeit, diese Muster mit dem der NutzerIn abzugleichen, ohne dass dieses Verhalten bereits in ihren nutzerseitig generierten Daten abgelegt ist. Nichtsdestotrotz zeigt die Arbeit, welches Potential die nutzerseitige Modellierung bereithält - nicht nur in Bezug auf den größeren Schutz der Privatsphäre der NutzerInnen, sondern ebenso in Hinsicht auf den Einsatz von Methoden des verteilten Rechnens (distributed computing). Die Kombination von beidem, nutzerInnen- und serverseitiger Modellierung, könnte ein neuer und vielversprechender Pfad für datengetriebene Innovation darstellen. Neben der technologischen Perspektive werden die entwickelten Methoden einer kritischen Analyse unterzogen. Durch das Einbringen der nutzerseitigen Modellierung in Form von benutzerspezifischen künstlichen neuronalen Netzen trainieren die NutzerInnen ihre eigenen Algorithmen auf ihren mobilen Geräten. Diese spezifischen Algorithmen sind weniger stark von generalisierten Vorannahmen, Vorurteilen und möglichen Befangenheiten der EntwicklerInnen beeinflusst. Hierdurch haben NutzerInnen die Möglichkeit, vielfältigere und persönlichere Perspektiven auf ihre Daten und ihr Verhalten zu generieren. Dieses Konzept setzt Ideen der kritischen Kartographie fort, in welcher der Status Quo der Wahrnehmung und Repräsentation des Raumes hinterfragt werden. KW - Personal Data KW - mobile KW - machine learning KW - privacy KW - spatio-temporal KW - recommendation KW - behaviour KW - persönliche Informationen KW - Mobil KW - Machine Learning KW - Privatsphäre KW - raum-zeitlich KW - Empfehlungen KW - Verhalten Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-406696 ER - TY - GEN A1 - Gebser, Martin A1 - Kaufmann, Benjamin A1 - Schaub, Torsten H. T1 - Multi-threaded ASP solving with clasp T2 - Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe N2 - We present the new multi-threaded version of the state-of-the-art answer set solver clasp. We detail its component and communication architecture and illustrate how they support the principal functionalities of clasp. Also, we provide some insights into the data representation used for different constraint types handled by clasp. All this is accompanied by an extensive experimental analysis of the major features related to multi-threading in clasp. T3 - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe - 586 KW - propositional satisfiability KW - clause elimination KW - parallel execution KW - SAT KW - algorithm KW - platypus KW - systems KW - search KW - solver Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-413977 SN - 1866-8372 IS - 586 ER - TY - GEN A1 - Hoos, Holger A1 - Kaminski, Roland A1 - Lindauer, Marius A1 - Schaub, Torsten H. T1 - aspeed BT - solver scheduling via answer set programming T2 - Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe N2 - Although Boolean Constraint Technology has made tremendous progress over the last decade, the efficacy of state-of-the-art solvers is known to vary considerably across different types of problem instances, and is known to depend strongly on algorithm parameters. This problem was addressed by means of a simple, yet effective approach using handmade, uniform, and unordered schedules of multiple solvers in ppfolio, which showed very impressive performance in the 2011 Satisfiability Testing (SAT) Competition. Inspired by this, we take advantage of the modeling and solving capacities of Answer Set Programming (ASP) to automatically determine more refined, that is, nonuniform and ordered solver schedules from the existing benchmarking data. We begin by formulating the determination of such schedules as multi-criteria optimization problems and provide corresponding ASP encodings. The resulting encodings are easily customizable for different settings, and the computation of optimum schedules can mostly be done in the blink of an eye, even when dealing with large runtime data sets stemming from many solvers on hundreds to thousands of instances. Also, the fact that our approach can be customized easily enabled us to swiftly adapt it to generate parallel schedules for multi-processor machines. T3 - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe - 588 KW - algorithm schedules KW - answer set programming KW - portfolio-based solving Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-414743 SN - 1866-8372 IS - 588 ER - TY - GEN A1 - Gebser, Martin A1 - Harrison, Amelia A1 - Kaminski, Roland A1 - Lifschitz, Vladimir A1 - Schaub, Torsten H. T1 - Abstract gringo T2 - Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe N2 - This paper defines the syntax and semantics of the input language of the ASP grounder gringo. The definition covers several constructs that were not discussed in earlier work on the semantics of that language, including intervals, pools, division of integers, aggregates with non-numeric values, and lparse-style aggregate expressions. The definition is abstract in the sense that it disregards some details related to representing programs by strings of ASCII characters. It serves as a specification for gringo from Version 4.5 on. T3 - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe - 592 KW - nested expressions Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-414751 SN - 1866-8372 IS - 592 ER - TY - GEN A1 - Gebser, Martin A1 - Lee, Joohyung A1 - Lierler, Yuliya T1 - On elementary loops of logic programs T2 - Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe N2 - Using the notion of an elementary loop, Gebser and Schaub (2005. Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’05 ), 53–65) refined the theorem on loop formulas attributable to Lin and Zhao (2004) by considering loop formulas of elementary loops only. In this paper, we reformulate the definition of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we also show that the corresponding problem is coNP-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs attributable to Ben-Eliyahu and Dechter (1994. Annals of Mathematics and Artificial Intelligence 12, 53–87). Like an HCF program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body. T3 - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe - 566 KW - stable model semantics KW - loop formulas KW - unfounded sets Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-413091 SN - 1866-8372 IS - 566 ER - TY - JOUR A1 - Kaitoua, Abdulrahman A1 - Rabl, Tilmann A1 - Markl, Volker T1 - A distributed data exchange engine for polystores JF - Information technology : methods and applications of informatics and information technology JF - Information technology : Methoden und innovative Anwendungen der Informatik und Informationstechnik N2 - There is an increasing interest in fusing data from heterogeneous sources. Combining data sources increases the utility of existing datasets, generating new information and creating services of higher quality. A central issue in working with heterogeneous sources is data migration: In order to share and process data in different engines, resource intensive and complex movements and transformations between computing engines, services, and stores are necessary. Muses is a distributed, high-performance data migration engine that is able to interconnect distributed data stores by forwarding, transforming, repartitioning, or broadcasting data among distributed engines' instances in a resource-, cost-, and performance-adaptive manner. As such, it performs seamless information sharing across all participating resources in a standard, modular manner. We show an overall improvement of 30 % for pipelining jobs across multiple engines, even when we count the overhead of Muses in the execution time. This performance gain implies that Muses can be used to optimise large pipelines that leverage multiple engines. KW - distributed systems KW - data migration KW - data transformation KW - big data KW - engine KW - data integration Y1 - 2020 U6 - https://doi.org/10.1515/itit-2019-0037 SN - 1611-2776 SN - 2196-7032 VL - 62 IS - 3-4 SP - 145 EP - 156 PB - De Gruyter CY - Berlin ER - TY - JOUR A1 - Dreseler, Markus A1 - Boissier, Martin A1 - Rabl, Tilmann A1 - Uflacker, Matthias T1 - Quantifying TPC-H choke points and their optimizations JF - Proceedings of the VLDB Endowment N2 - TPC-H continues to be the most widely used benchmark for relational OLAP systems. It poses a number of challenges, also known as "choke points", which database systems have to solve in order to achieve good benchmark results. Examples include joins across multiple tables, correlated subqueries, and correlations within the TPC-H data set. Knowing the impact of such optimizations helps in developing optimizers as well as in interpreting TPC-H results across database systems. This paper provides a systematic analysis of choke points and their optimizations. It complements previous work on TPC-H choke points by providing a quantitative discussion of their relevance. It focuses on eleven choke points where the optimizations are beneficial independently of the database system. Of these, the flattening of subqueries and the placement of predicates have the biggest impact. Three queries (Q2, Q17, and Q21) are strongly ifluenced by the choice of an efficient query plan; three others (Q1, Q13, and Q18) are less influenced by plan optimizations and more dependent on an efficient execution engine. Y1 - 2020 U6 - https://doi.org/10.14778/3389133.3389138 SN - 2150-8097 VL - 13 IS - 8 SP - 1206 EP - 1220 PB - Association for Computing Machinery CY - New York ER - TY - JOUR A1 - Navarro, Marisa A1 - Orejas, Fernando A1 - Pino, Elvira A1 - Lambers, Leen T1 - A navigational logic for reasoning about graph properties JF - Journal of logical and algebraic methods in programming N2 - Graphs play an important role in many areas of Computer Science. In particular, our work is motivated by model-driven software development and by graph databases. For this reason, it is very important to have the means to express and to reason about the properties that a given graph may satisfy. With this aim, in this paper we present a visual logic that allows us to describe graph properties, including navigational properties, i.e., properties about the paths in a graph. The logic is equipped with a deductive tableau method that we have proved to be sound and complete. KW - Graph logic KW - Algebraic methods KW - Formal modelling KW - Specification Y1 - 2021 U6 - https://doi.org/10.1016/j.jlamp.2020.100616 SN - 2352-2208 SN - 2352-2216 VL - 118 PB - Elsevier Science CY - Amsterdam [u.a.] ER - TY - THES A1 - Makowski, Silvia T1 - Discriminative Models for Biometric Identification using Micro- and Macro-Movements of the Eyes N2 - Human visual perception is an active process. Eye movements either alternate between fixations and saccades or follow a smooth pursuit movement in case of moving targets. Besides these macroscopic gaze patterns, the eyes perform involuntary micro-movements during fixations which are commonly categorized into micro-saccades, drift and tremor. Eye movements are frequently studied in cognitive psychology, because they reflect a complex interplay of perception, attention and oculomotor control. A common insight of psychological research is that macro-movements are highly individual. Inspired by this finding, there has been a considerable amount of prior research on oculomotoric biometric identification. However, the accuracy of known approaches is too low and the time needed for identification is too long for any practical application. This thesis explores discriminative models for the task of biometric identification. Discriminative models optimize a quality measure of the predictions and are usually superior to generative approaches in discriminative tasks. However, using discriminative models requires to select a suitable form of data representation for sequential eye gaze data; i.e., by engineering features or constructing a sequence kernel and the performance of the classification model strongly depends on the data representation. We study two fundamentally different ways of representing eye gaze within a discriminative framework. In the first part of this thesis, we explore the integration of data and psychological background knowledge in the form of generative models to construct representations. To this end, we first develop generative statistical models of gaze behavior during reading and scene viewing that account for viewer-specific distributional properties of gaze patterns. In a second step, we develop a discriminative identification model by deriving Fisher kernel functions from these and several baseline models. We find that an SVM with Fisher kernel is able to reliably identify users based on their eye gaze during reading and scene viewing. However, since the generative models are constrained to use low-frequency macro-movements, they discard a significant amount of information contained in the raw eye tracking signal at a high cost: identification requires about one minute of input recording, which makes it inapplicable for real world biometric systems. In the second part of this thesis, we study a purely data-driven modeling approach. Here, we aim at automatically discovering the individual pattern hidden in the raw eye tracking signal. To this end, we develop a deep convolutional neural network DeepEyedentification that processes yaw and pitch gaze velocities and learns a representation end-to-end. Compared to prior work, this model increases the identification accuracy by one order of magnitude and the time to identification decreases to only seconds. The DeepEyedentificationLive model further improves upon the identification performance by processing binocular input and it also detects presentation-attacks. We find that by learning a representation, the performance of oculomotoric identification and presentation-attack detection can be driven close to practical relevance for biometric applications. Eye tracking devices with high sampling frequency and precision are expensive and the applicability of eye movement as a biometric feature heavily depends on cost of recording devices. In the last part of this thesis, we therefore study the requirements on data quality by evaluating the performance of the DeepEyedentificationLive network under reduced spatial and temporal resolution. We find that the method still attains a high identification accuracy at a temporal resolution of only 250 Hz and a precision of 0.03 degrees. Reducing both does not have an additive deteriorating effect. KW - Machine Learning Y1 - 2021 ER -