c 2015 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. Re-publication of material from this volume requires permission by the copyright owners.
Herausgeber:
bereits zum 27. Mal fand vom 26.05.2015 bis 29.05.2015 der Workshop ”Grundlagen von Datenbanken“ (GvDB) statt. Nachdem der Workshop im letzten Jahr in Su¨dtirol zu Gast war, kehrte er in diesem Jahr wieder nach Deutschland zuru¨ck, genauer nach Gommern in Sachsen-Anhalt, wo er bereits das zweite Mal nach 2001 stattfand.
Der vierta¨gige Workshop wurde vom GI-Arbeitskreis Grundlagen von Informationssystemen im Fachbereich Datenbanken und Informationssysteme (DBIS) veranstaltet und hat die theoretischen, konzeptionellen und methodischen Grundlagen von Datenbanken und Informationssystemen zum Thema, ist aber auch fu¨r neue Anwendungsgebiete mit Datenmanagementbezug offen. Organisiert wurde der Workshop durch die Arbeitsgruppe Datenbanken und Software Engineering der Otto-von-Guericke-Universita¨t Magdeburg.
Der Workshop soll die Kommunikation zwischen Wissenschaftlern/-innen im deutschsprachigen Raum fo¨rdern, die sich grundlagenorientiert mit Datenbanken und Informationssystemen bescha¨ftigen. Er ist insbesondere als Forum fu¨r Nachwuchswissenschaftler/-innen gedacht, die ihre aktuellen Arbeiten in einem gro¨ßeren Forum vorstellen wollen. Der Workshop fand im idyllischen ”Hotel am See“, dem Robinien-Hof in Gommern, statt. Das Hotel befindet sich gleich gegenu¨ber der letzten Wanderdu¨ne in Sachsen-Anhalt. Durch die ruhige Lage am ”Kulk“ bietet der Tagungsort einen idealen Rahmen fu¨r offene und inspirierende Diskussionen zu
Aus den Einsendungen wurden 15 Arbeiten nach einem Review-Prozess ausgewa¨hlt und vorgestellt. Die Themenvielfalt erstreckte sich dabei von Crowdsourcing fu¨r Entity Resolution u¨ber klassischere Themen wie Datenkompression bis hinzu Datenstromanagementsystemen. Die Beitra¨ge wurden durch drei Keynotes erga¨nzt. Kai-Uwe Sattler, Professor an der TU Ilmenau, ging in seinem Vortrag Optimierung von Datenflussprogrammen - ein Fall klassischer Anfrageoptimierung? auf die Optimierung von Ausfu¨hrungspla¨nen zur Datenstromverarbeitung ein. Erhard Rahm, Professor an der Uni Leipzig, pra¨sentierte in seinem Vortrag Scalable Graph Analytics with GRADOOP die Potentiale von MapReduce-Frameworks wie Hadoop fu¨r Graphanalysen. Außerdem beleuchtete Wolfgang Lehner von der TU Dresden in seinem Vortrag Next-Generation Hardware for Data Management - More a Blessing than a Curse? offene Fragen bei der Entwicklung hardware-sensitiver Datenbanksysteme und gab einen Ausblick auf die Potentiale, die sich aus dem konsequentem
Das ausgewogene Workshop-Programm wurde von zwei Ausflu¨gen abgerundet. Zuna¨chst konnten die Teilnehmer bei einer Fu¨hrung durch den Gommeraner Gesteinsgarten eine der gro¨ßten und umfassendsten Sammlungen von Natursteinen aus Deutschland und Europa erkunden und bei der anschließenden Waldwanderung die Ruhe der Natur genießen. Aber auch fu¨r die kulinarische Unterhaltung war gesorgt. So stand neben einem Grillbu¨ffett zur Auffrischung der Kra¨fte nach den Wanderungen der Besuch von Deutschlands einziger Gasthausbrauerei auf einer u¨ber 1000 Jahre alten Burg an, natu¨rlich inklusive Verkostung. An dieser Stelle danke ich allen Beteiligten fu¨r die erfolgreiche Durchfu¨hrung des GvDB 2015: den Autoren, dem Programmkomittee und den Mitarbeitern des Tagungsghotels. Besonderer Dank gilt allen Mitgleidern des Organisations-Komittee ohne deren Hilfe die Durchfu¨hrung des GvDB 2015 nicht mo¨glich gewesen wa¨re: David Broneske, Sebastian Dorok, Andreas Meister, Siba Mohammad und Veit
Inhaltsverzeichnis
Optimierung von Datenflussprogrammen - ein Fall klassischer Anfrageoptimierung?
Kai-Uwe Sattler Scalable graph analytics with GRADOOP
Erhard Rahm Next-Generation Hardware for Data Management – more a Blessing than a Curse?
Wolfgang Lehner
Ontologie-basierte Fragmentierungs- und Replikationsverfahren fu¨r verteilte Datenbanksysteme
Lena Wiese Automated Silhouette Extraction for Mountain Recognition
Daniel Braun, Michael Singhof Slicing in Assistenzsystemen - Wie trotz Anonymisierung von Daten wertvolle Analyseergebnisse gewonnen werden ko¨nnen Hannes Grunert, Andreas Heuer Towards Visualization Recommendation – A Semi- Automated Domain-Specific Learning Approach
Pawandeep Kaur, Michael Owonibi, Birgitta Koenig-Ries Transparente Datenbankunterstu¨tzung fu¨r Analysen auf Big Data Dennis Marten, Andreas Heuer 9 9 10 11 12 12 18 24 30 36 Ausfu¨hrungspl¨ane und -planoperatoren relationaler Datenbankmanagementsysteme
Christoph Koch, Katharina Bu¨chse Modularisierung leichtgewichtiger Kompressionsalgorithmen
Juliana Hildebrandt, Dirk Habich, Patrick Damme, Wolfgang Lehner Annotation und Management heterogener medizinischer Studienformulare
Victor Christen Merkle Hash Tree based Techniques for Data Integrity of Outsourced Data
Muhammad Saqib Niaz, Gunter Saake Crowdsourcing Entity Resolution: a Short Overview and Open Issues
Xiao Chen Toward GPU Accelerated Data Stream Processing
Marcus Pinnecke, David Broneske, Gunter Saake Where- und Why-Provenance fu¨r syntaktisch reiches SQL durch Kombination von Programmanalysetechniken
Tobias Mu¨ller Large-scale Analysis of Event Data
Stefan Hagedorn, Kai-Uwe Sattler, Michael Gertz Flexible Online-Recommender-Systeme durch die Integration in ein Datenstrommanagementsystem
Cornelius A. Ludmann, Marco Grawunder, Hans-Ju¨rgen Appelrath
Das PArADISE-Projekt - Big-Data-Analysen fu¨r die Entwicklung von Assistenzsystemen Andreas Heuer, Holger Meyer 54 60 66 72 78 84 90 96 102 102 Optimierung von Datenflussprogrammen - ein Fall klassischer Anfrageoptimierung?
[Abstract]
Kai-Uwe Sattler Technische Universität Ilmenau
Helmholtzplatz 5
Ilmenau, Germany kus@tu-ilmenau.de Datenflusssprachen haben in den vergangenen Jahren speziell im Kontext von Big-Data-Plattformen - etwa in Form von Pig oder Jaql - große Aufmerksamkeit gewonnen. Sie bieten sich jedoch auch fu¨r die Verarbeitung und Analyse dynamischer Daten bzw. Datenstro¨me an. A¨ hnlich wie bei klassischen Anfragesprachen besteht bei Datenflusssprachen die Aufgabe, aus (mehr oder weniger) deklarativen Spezifikationen effiziente Ausfu¨hrungspla¨ne abzuleiten. Der Vortrag behandelt die Herausforderungen derartiger Optimierungen, geht auf Besonderheiten im Vergleich zur klassischen Anfrageoptimierung ein und diskutiert anhand von Beispielen aus den Bereichen Datenstromverarbeitung und MapReduce konkrete Problemstellungen.
About the Author Kai-Uwe Sattler ist Professor fu¨r Datenbanken und Informationssysteme an der TU Ilmenau. Zu seinen Arbeitsgebieten za¨hlen Datenbanksystemaspekte, Datenbankintegration sowie Anfrageverarbeitung fu¨r, heterogenen, massiv verteilte und dynamische Datenbesta¨nde. Er ist Koautor mehrerer Lehrbu¨cher, u.a. zu verschiedenen Datenbankkonzepten wie Grundlagen, Implementierungstechniken, Data Warehousing und Cloud Data Management sowie zu Algorithmen und Datenstrukturen. Scalable graph analytics with GRADOOP Many Big Data applications in business and science require the management and analysis of huge amounts of graph data. Previous approaches for graph analytics such as graph databases and parallel graph processing systems (e.g., Pregel) either lack sufficient scalability or flexibility and expressiveness. We are therefore developing a new end-to-end approach for graph data management and analysis at the Big Data center of excellence ScaDS Dresden/Leipzig. The system is called Gradoop (Graph analytics on Hadoop). Gradoop is designed around the so-called Extended Property Graph Data Model (EPGM) which supports semantically rich, schemafree graph data within many distinct graphs. A set of highlevel operators is provided for analyzing both single graphs and sets of graphs. The operators are usable within a domainspecific language to define and run data integration workflows (for integrating heterogeneous source data into the Gradoop graph store) as well as analysis workflows. The Gradoop data store is currently utilizing HBase for distributed storage of graph data in Hadoop clusters. An initial version of Gradoop is operational and has been used for analyzing graph data for business intelligence and social network analysis. 27th GI-Workshop on Foundations of Databases (Grundlagen von Datenbanken), 26.05.2015 - 29.05.2015, Magdeburg, Germany.
Copyright is held by the author/owner(s).
About the Author Erhard Rahm is full professor for databases at the computer science institute of the University of Leipzig. His current research focusses on Big Data and data integration. He has authored several books and more than 200 peer-reviewed journal and conference publications. His research on data integration and schema matching has been awarded several times, in particular with the renowned 10year best-paper award of the conference series VLDB (Very Large Databases) and the Influential Paper Award of the conference series ICDE (Int. conf. on Data Engineering).
Prof. Rahm is one of the two scientific coordinators of the new German center of excellence on Big Data ScaDS (competence center for SCAlable Data services and Solutions) Dresden/Leipzig that started its operation in Oct. 2014.
Next-Generation Hardware for Data Management - more a Blessing than a Curse? Recent hardware developments have touched almost all components of a computing system: the existence of many and potentially heterogeneous cores, the availability of volatile and non-volatile main memories with an ever growing capacity, and the emergence of economically affordable, highspeed/low-latency interconnects are only a few prominent examples. Every single development as well as their combination has a massive impact on the design of modern computing systems. However, it is still an open question, if, how, and at which level of detail, a database system has to explicitly be aware of those developments and exploit them using specifically designed algorithms and data structures. Within the talk I will try to give an answer to this question and argue for a clear roadmap of HW/SW-DB-CoDesign especially providing an outlook to upcoming technologies and discussion of their non-functional properties like energy-efficiency and resilience behavior.
About the Author Wolfgang Lehner is full professor and head of the database technology group at the TU Dresden, Germany. His research is dedicated to database system architecture specifically looking at crosscutting aspects from algorithms down to hardware-related aspects in main-memory centric settings. He is part of TU Dresden’s excellence cluster with research topics in energy-aware scheduling, resilient data structures on unreliable hardware, and orchestration of wildly heterogeneous systems; he is also a principal investigator of Germany’s national ”Competence Center for Scalable Data Services and Solutions” (ScaDS); Wolfgang also maintains a close research relationship with the SAP HANA development team. He serves the community in many PCs, is an elected member of the VLDB Endowment, serves on the review board of the German Research Foundation (DFG), and is an appointed member of the Academy of Europe. 27th GI-Workshop on Foundations of Databases (Grundlagen von Datenbanken), 26.05.2015 - 29.05.2015, Magdeburg, Germany.
Copyright is held by the author/owner(s).
Ontologie-basierte Fragmentierungs- und Replikationsverfahren für verteilte Datenbanksysteme
Lena Wiese Forschungsgruppe Knowledge Engineering
Institut für Informatik Georg-August-Universität Göttingen wiese@cs.uni-goettingen.de Das Auffinden von semantisch verwandten Daten in großen Datenmengen ist aufwa¨ndig und daher zur Laufzeit einer Anfrage nur schwierig durchzufu¨hren. In diesem Artikel stellen wir ein Verfahren vor, dass Datentabellen anhand einer Ontologie in semantisch zusammenha¨ngende Cluster aufteilt. Dadurch ergibt sich eine Ontologie-basierte Fragmentierung der Tabelle, die eine flexible Anfragebeantwortung unterstu¨tzt. Bei mehreren derartigen Fragmentierungen u¨berschneiden sich Fragmente; dies wird fu¨r ein intelligentes Replikationsverfahren ausgenutzt, um die Anzahl der Replikaserver zu reduzieren.
Keywords Verteiltes Datenbanksystem, Replikation, Ontologie, Fragmentierung, flexible Anfragebeantwortung
EINLEITUNG
Die Verwaltung von großen Datenmengen in Datenbanken erfordert die Verteilung der Daten auf mehrere DatenbankServer. Dies bietet mehrere Vorteile: • Lastverteilung: Datenbankanfragen ko¨nnen auf mehre
re Server verteilt und damit parallelisiert werden. • Verfu¨gbarkeit: Durch die Lastverteilung erho¨ht sich die
Verfu¨gbarkeit des Gesamtsystems, da einzelne Anfragen seltener verzo¨gert werden mu¨ssen.
Ein geeignetes Verfahren zur Fragmentierung (auch: Partitionierung oder Sharding) der Daten in Teilmengen ist daher notwendig. Die ga¨ngigen Fragmentierungsverfahren (Round-Robin, Hash-basiert, Intervall-basiert) ignorieren jedoch semantische Zusammenha¨nge der Daten.
Aus Gru¨nden der Ausfallsicherheit ist zusa¨tzlich noch die Replikation von Daten (also die Spiegelung desselben Datensatzes auf mehreren Servern) erforderlich. Dies gilt insbesondere fu¨r Hauptspeicherdatenbanken, die nicht u¨ber einen Hintergrundspeicher verfu¨gen. In dieser Arbeit stellen wir
Verfahren zur Ontologie-basierten Fragmentierung und zur intelligenten Replikation vor, womit folgende Eigenschaften sichergestellt werden: • durch die Fragmentierung wird ein Verfahren der flexiblen Anfragebeantwortung unterstu¨tzt, die dem Anfrager auch relevante verwandte Werte als Antworten zuru¨ckliefert. • durch die Fragmentierung wird eine Lastverteilung auf
mehrere Server mo¨glich. • durch die Fragmentierung wird die Anzahl der kontaktierten Server pro Anfrage reduziert und damit eine bessere Parallelisierung mo¨glich. • durch die intelligente Replikation wird die Anzahl der
beno¨tigten Replikaserver reduziert.
Abschnitt 2 beschreibt den Hintergrund zu flexibler Anfragebeantwortung, Fragmentierung und Datenverteilung. Abschnitt 3 stellt die Ontologie-basierte Fragmentierung inklusive Clustering, Fragmentverteilung und Anfragebeantwortung vor. Abschnitt 4 beschreibt darauf aufbauend ein Replikationsverfahren mit u¨berlappenden Fragmenten. Ein Wiederherstellungsverfahren anhand des Replikationsverfahrens wird in Abschnitt 5 dargestellt. Es folgt ein Verfahren fu¨r abgeleitete Fragmentierungen in Abschnitt 6 und abschließend eine Zusammenfassung in Abschnitt 7.
HINTERGRUND
Wir stellen hier kurz Vorarbeiten zu flexibler Anfragebeantwortung, Fragmentierung und Datenverteilung vor.
Diese Operatoren ko¨nnen auch kombiniert werden [IW11].
Diese syntaktischen A¨ nderungen ko¨nnen aber zu weit gehen und zu viele Antworten produzieren – insbesondere beim Ersetzen von Konstanten durch neue Variablen in der AntiInstantiation. Daher ist es wichtig, dass die Werte, die der neuen Variable zugewiesen werden ko¨nnen, beschra¨nkt werden: es sollen nur semantisch a¨quivalente oder semantisch nah verwandte Werte zugelassen werden. Diese semantische A¨ hnlichkeit kann anhand einer Ontologie oder Taxonomie von Werten bestimmt werden. Fu¨r Einzelrechner wurden bereits vor einiger Zeit Verfahren vorgeschlagen – ohne jedoch verteilte Datenspeicherung mit einzubeziehen. CoBase [CYC+96] und [SHL07] zum Beispiel benutzten sogenannte Abstraktionshierarchien, um einzelne Werte zu generalisieren. Auch fu¨r XML-Anfragen wurden Verfahren entwickelt [HTGC10].
Ein grundlegendes Problem ist dabei jedoch, dass die Bestimmung von a¨hnlichen Werten zur Laufzeit (wa¨hrend der Anfragebeantwortung) viel zu ineffizient ist [BDIW14]. Dieses Problem wird durch das hier vorgestellte Fragmentierungsverfahren gelo¨st. 2.2
Fragmentierung
Im relationalen Modell gibt es die Theorie der Datenfragmentierung, die sich aufgrund des strikten Tabellenformats aufteilen la¨sst in horizontale und vertikale Fragmentierung (siehe zum Beispiel [ O¨V11]): • Vertikale Fragmentierung: Fragmente entsprechen Teilmengen von Attributen (also Tabellenspalten). Die Eintra¨ge in den Fragmenten, die zur selben Tabellenzeile geho¨ren, mu¨ssen durch einen Tuple-Identifikator verbunden werden. Vertikale Fragmentierung entspricht einer Projektion auf der Tabelle. • Horizontale Fragmentierung: Fragmente sind Teilmengen von Tupeln (also Tabellenzeilen). Eine horizontale Fragmentierung entspricht einer Selektion auf der Tabelle. • Abgeleitete Fragmentierung: Eine bereits bestehende ”prima¨re“ horizontale Fragmenation of einer Tabelle induziert eine horizontale Fragmentierung einer weiteren Tabelle; dazu wird der Semi-JOIN auf beiden
Tabellen ausgefu¨hrt.
Drei grundlegende Eigenschaften sind wichtig fu¨r Fragmentierungen: • Vollsta¨ndigkeit: Keine Daten du¨rfen wa¨hrend der Fragmentierung verloren gehen. Bei vertikaler Fragmentierung ist jede Spalte in einem Fragment enthalten; bei horizontaler Fragmentierung ist jede Zeile in einem
Fragment enthalten. • Rekonstruierbarkeit: Daten aus den Fragmenten ko¨nnen wieder zur Originaltabelle zusammengefu¨gt werden. Bei vertikaler Fragmentierung wird der JOINOperator benutzt (basierend auf einem zusa¨tzlich eingefu¨gten Tupel-Identifikator), um die Spalten zu verbinden. Bei horizontaler Fragmentierung wird der Vereinigungsoperator zum Zusammenfu¨hren der Fragmente verwendet. • Redundanzfreiheit: Um Duplizieren von Daten zu vermeiden, sollen einzelne Datensa¨tze nur einem Fragment zugewiesen werden. Bei vertikaler Fragmentierung ist jede Spalte nur in einem Fragment enthalten (abgesehen vom Tupel-Identifikator). Bei horizontaler Fragmentierung ist jede Zeile in nur einem Fragment enthalten.
In anderen, nicht-relationalen Datenmodellen (Schlu¨sselWert-Speicher, Dokumentdatenbanken oder Spaltenfamiliendatenbanken) gibt es Fragmentierung meist u¨ber den Zugriffsschlu¨ssel entweder Hash-basiert [KLL+97] oder basierend auf Intervallen. Jedoch unterstu¨tzt keines dieser Verfahren die flexible Anfragebeantwortung; im Gegensatz dazu hat das im Folgenden vorgestellte Fragmentierungsverfahren den Vorteil, dass eine relaxierte Bedingung aus nur einem Fragment beantwortet werden kann. 2.3
Datenverteilung
In einem verteilten Datenbanksystem mu¨ssen Daten auf die verschiedenen Server verteilt werden. Wichtige Eigenschaften sind • Datenlokalita¨t: Daten, auf die innerhalb einer Anfrage oder Transaktion zugegriffen wird, sollten mo¨glichst auf einem Server sein. Dadurch verringert sich die Anzahl der kontaktierten Server und somit auch die Dauer der Anfragebeantwortung. Außerdem kann so die Parallelisierung der Anfragebeantwortung verbessert werden, da die anderen Server neue Anfragen annehmen ko¨nnen. • Lastverteilung: Daten sollen so verteilt werden, dass parallele Anfragen mo¨glichst auch von verschiedenen Servern beantwortet werden ko¨nnen, damit nicht einzelne Server unter Lastspitzen (”hot spots“) leiden.
Einige Arbeiten befassen sich mit horizontaler Fragmentierung und Verteilung; jedoch unterstu¨tzen diese nur exakte Anfragebeantwortung und keine flexible Anfragebeantwortung wie in unserem Ansatz. Die meisten Ansa¨tze gehen von einer vorgebenen Menge von Anfragen oder Transaktionen aus (”workload“) und optimieren die Lokalita¨t der Daten, die innerhalb der Anfrage beziehungsweise Transaktion beno¨tigt werden. Dies ist fu¨r die Anwendung der flexiblen Anfragebeantwortung jedoch nicht anwendbar, da hier auch Werte zuru¨ckgegeben werden, die nicht explizit in einer Anfrage auftauchen.
[CZJM10] stellen Tupel als Knoten eines Graphen dar.
Fu¨r eine vorgegebene Menge von Transaktionen fu¨gen sie Hyperkanten in den Graph ein, wenn die Tupel in derselben Transaktion beno¨tigt werden. Mit einem Graphpartitionierungsalgorithmus wird dann eine Datenfragmentierung ermittelt, die Zahl der zerschnittenen Kanten minimiert.
In einer zweiten Phase benutzen die Autoren einen Klassifizierer aus dem Maschinellen Lernen, der eine Intervallbasierte Fragmentierung herleitet. Experimentell vergleichen sie dann das Graph-basierten mit Intervall-basierten und Hash-basierten Verfahren. Im Gegensatz zu unserem Ansatz wenden sie jedoch volle Replikation an, bei der alle Server alle Daten vorhalten; dies ist wenig realistisch in großen verteilten Systemen. Zudem vergleichen sie drei verschiedene Arten von Lookup-Tabellen, die Tupel-Identifikatoren fu¨r jedes Fragment abspeichern: Indexe, Bitarrays und Bloomfilter. Bei der Analyse unseres Systems stellt sich jedoch heraus, dass Lookup-Tabellen ineffizienter sind als das Einfu¨hren einer zusa¨tzlichen Spalte mit der Cluster-ID in anderen Fragmentierungen.
Auch [QKD13] modellieren das Fragmentierungsproblem durch Minimierung zerschnittener Hyperkanten in einem Graphen. Zur Verbesserung der Effizienz komprimieren sie den Graphen und erhalten so Gruppen von Tupeln. Die Autoren kritisieren dabei auch den tupelweisen Ansatz von [CZJM10] als unpraktisch fu¨r große Tupelmengen. Die Autoren vergleichen ihren Ansatz mit zufa¨lligen und tupelweisen Fragmentierungen und betrachten auch A¨ nderungen der vorgegebenen Transaktionen.
[TCJM12] gehen von drei existierenden Fragmentierungen aus: Hash-basiert, Intervall-basiert und Lookup-Tabellen auf einzelnen Zugriffsschlu¨sseln. Sie vergleichen diese drei bezu¨glich Kommunikationskosten und Anfragendurchsatz. Zur Effiziensteigerung analysieren sie diverse Komprimierungstechniken. Sie beschreiben Hash-basierte Fragmentierung als zu ineffizient. Die Autoren beschreiben jedoch nicht, wie die Fragmentierungen fu¨r die Lookup-Tabellen berechnet werden; im Gegensatz dazu stellen wir ein Ontologie-basiertes Fragmentierungsverfahren vor.
Im Gegensatz zu den meisten anderen Ansa¨tzen gehen wir nicht von einer vorgegebenen Menge von Anfragen oder Transaktionen aus sondern schlagen ein allgemein anwendbares Clusteringverfahren vor, dass die flexible Anfragebeantwortung zum Auffinden semantisch a¨hnlicher Antworten ermo¨glicht. Unsere Ergebnisse zeigen, dass Lookup-Tabellen (selbst wenn sie auf allen Servern repliziert werden) fu¨r unseren Ansatz zu ineffizient sind, dadurch dass viele JOINOperationen durchgefu¨hrt werden mu¨ssen.
Unser Verfahren der Ontologie-basierten Fragmentierung beruht darauf, dass • zur Anti-Instantiierung ein Attribut (also eine Tabel
lenspalte) ausgewa¨hlt wird. • ein Clusteringverfahren auf dieser Tabellenspalte ausgefu¨hrt wird, um die a¨hnlichen Werte innerhalb dieser
Spalte zu gruppieren. • anhand der Cluster die Tabelle zeilenweise fragmen
tiert wird.
Wie in Abbildung 1 dargestellt werden dann die Anfragen so weitergeleitet, dass zu einer Konstante aus der Originalanfrage das semantisch a¨hnlichste Fragment ermittelt wird und anschließend alle Werte des Fragments als relevante Antworten zuru¨ckgeliefert werden. Daher werden zum Beispiel bei einer Anfrage nach Husten auch die a¨hnlichen Werte Asthma und Bronchitis gefunden. 3.1
Clustering
Zu dem zur Anti-Instantiierung ausgewa¨hlten Attribut A in der gegebenen Tabelle F werden alle in der Tabelle vorhandenen Werte (die sogenannte aktive Doma¨ne) ausgelesen durch Projektion πA(F ). Anhand einer gegebenen Ontologie werden A¨ hnlichkeitswerte sim zwischen jeweils zwei Termen a, b ∈ πA(F ) bestimmt im Wertebereich 0 (keine A¨ hnlichkeit) bis 1 (volle A¨ hnlichkeit). Dazu gibt es verschiedene Metriken, die meist auf der Berechnung von Pfaden zwischen den Termen in der Ontologie beruhen [Wie14, Wie13]. user query rewrite & redirect
Fragment 1: cough, bronchitis, asthma Fragment 2: brokenLeg, brokenArm cluster & fragment
Ein Clustering-Verfahren benutzt diese A¨ hnlichkeitswerte um Cluster zu bestimmen (in Anlehnung an [Gon85]). Dazu wird in jedem Cluster ein prototypisches Element head bestimmt, das das jeweilige Cluster repra¨sentiert. Zusa¨tzlich gibt es einen Schwellenwert α und das Verfahren unterteilt Cluster solange in Teilcluster, bis fu¨r jedes Element innerhalb eines Clusters die A¨ hnlichkeit zu head mindestens α ist. Das heißt, fu¨r jedes Cluster ci und head i ∈ ci gilt fu¨r jeden anderen Wert a ∈ ci (mit a 6= head i), dass sim(a, head i) ≥ α. Dieses Verfahren wird in Auflistung 1 dargestellt.
Listing 1 Clustering procedure Input: Set πA(F ) of values for attribute A, similarity thres
hold α Output: A set of clusters c1, . . . , cf 1: Let c1 = πA(F ) 2: Choose arbitrary head 1 ∈ c1 3: simmin = min{sim(a, head1) | a ∈ c1; a 6= head 1} 4: i = 1 5: while simmin < α do 6: Choose head i+1 ∈ S1≤j≤i{b | b ∈ cj ; b 6= head j ;
sim(b, headj ) = simmin } 7: ci+1 = {head i+1} ∪ S1≤j≤i{c | c ∈ cj; c 6= head j;
sim(c, headj ) ≤ sim(c, headi+1)} 8: i = i + 1 9: simmin = min{sim(d, headj ) | d ∈ cj; d 6= head j ; 1 ≤
j ≤ i} 10: end while
Zum Beispiel kann eine Taxonomie wie in Abbildung 2 benutzt werden, um die Tabellenspalte aus Abbildung 1 zu clustern. 3.2
Fragmentierung
Ein Clustering der aktiven Doma¨ne von A induziert eine horizontale Fragmentierung der Tabelle F in Fragmente Fi ⊆ F . Jede aktive Doma¨ne eines Fragments Fi entspricht genau den Werten in einem Cluster: ci = πA(Fi). Die grundlegenden Eigenschaften einer Fragmentierung (Vollsta¨ndigkeit, Rekonstruierbarkeit, Redundanzfreiheit) sollen auch bei einer Clustering-basierten Fragmentierung gelten. Auch das Clustering muss vollsta¨ndig sein: bei einer aktiven Doma¨ne πA(F ) muss dann fu¨r ein Clustering C = c1, . . . , cn gelten, dass es die ganze aktive Doma¨ne umfasst und kein Wert verloren geht: c1 ∪ . . . ∪ cn = πA(F ). Die Eigenschaften einer Clustering-basierten Fragmentierung werden in Definition 1 zusammengefasst.
Definition 1 (Clustering-bas. Fragmentierung).
Fu¨r ein Attribut A einer Tabelle F (eine Menge von Tupeln t) und ein Clustering C = {c1, . . . cn} der aktiven Doma¨ne πA(F ) und fu¨r head i ∈ ci gibt es eine Menge von Fragmenten {F1, . . . , Fn} (definiert u¨ber denselben Attributen wie F ), so dass folgende Eigenschaften gelten: • Horizontale Fragmentierung: fu¨r jedes Fragment Fi gilt
Fi ⊆ F • Clustering: fu¨r jedes Fi gibt es in Cluster ci ∈ C so
dass ci = πA(Fi) • Schwellenwert: fu¨r jedes a ∈ ci (wobei a 6= head i) gilt
sim(a, head i) ≥ α • Vollsta¨ndigkeit: fu¨r jedes Tupel t in F gibt es ein Frag
ment Fi, in dem t enthalten ist • Rekonstruierbarkeit: F = F1 ∪ . . . ∪ Fn • Redundanzfreiheit: fu¨r jedes i 6= j, Fi ∩ Fj = ∅ (oder
auch ci ∩ cj = ∅) 3.3
Fragmentverteilung
In verteilten Datenbanken mu¨ssen Fragmente verschiedenen Servern zugewiesen werden. Dieses Fragmentverteilungsproblem kann als ein Bin-Packing-Problem dargestellt werden: • K Server entsprechen K Bins • Jedes Bin hat maximale Kapazita¨t W • n Fragmente entsprechen n Objekten • Jedes Objekt/Fragment hat ein Gewicht (oder Kapizi
ta¨tsverbrauch) wi ≤ W • alle Objekte mu¨ssen auf mo¨glichst wenig Bins verteilt werden, wobei die Gewichtsgrenze W beachtet werden muss.
Dieses Bin-Packing-Problem kann auch als Problem der ganzzahligen linearen Optimierung dargestellt werden: s.t. xik ∈ {0, 1} k = 1, . . . , K, i = 1, . . . , n (1) (2) (3) (4) (5)
Dabei entspricht xik einer Bina¨rvariable die dann wahr (1) ist, wenn Fragment/Objekt i Server/Bin k zugewiesen wird; und yk bedeutet, dass Server/Bin k belegt ist (also nicht leer). Gleichung (1) fordert, dass die Anzahl der belegten Server minimiert wird; Gleichung (2) erzwingt, dass jedes Fragment einem Server zugewiesen wird; Gleichung (3) bedeutet, dass die Kapazita¨tsgrenzen nicht u¨berschritten werden; die letzten beiden Gleichungen stellen sicher, dass die Variablen bina¨r sind.
Zusa¨tzlich ko¨nnen noch die Eigenschaften der Datenlokalita¨t und der Lastverteilung optimiert werden. Datenverteilung mit einer guten Datenlokalita¨t platziert die Fragmente zusammen auf einen Server, die ha¨ufig gemeinsam innerhalb einer Datenbanktransaktion (oder auch innerhalb einer Anfrage) benutzt werden. Lastverteilung sorgt dafu¨r, dass alle Server ungefa¨hr dieselbe Anzahl von Anfragen beantworten mu¨ssen. 3.4
Metadaten
Fu¨r die Durchfu¨hrung des Clustering, der Fragmentverteilung und der Anfrageumschreibung und -umleitung werden ein paar Metadaten beno¨tigt.
Eine Tabelle root speichert einen Identifikator fu¨r jedes Cluster (Spalte ID), den Namen des Fragments (Name), den Repra¨sentaten des Clusters (Head), die Gro¨ße des Clusters (S) sowie den Server (Host), auf dem das Fragment gespeichert wird. Eine Beispieltabelle sieht dann so aus:
ROOT ID Name Head S Host 101 Respiratory Flu 4 S1 107 Fracture brokenArm 2 S2
Eine Tabelle similarities speichert die A¨ hnlichkeiten aller Werte des betrachteten Attributes zu den jeweiligen head Werten der Cluster. 3.5
Anfragebeantwortung
Fu¨r die flexible Anfragebeantwortung wird die Konstante im entsprechenden Attribut A in der Anfrage anti-instantiiert und die entstehende Anfrage dann aus dem semantisch a¨hnlichsten Fragment beantwortet.
Als Beispiel betrachten wir eine Anfrage nach Husten in einer Tabelle ill mit Patienten IDs und Krankheiten:
SELECT patientid, disease FROM ill WHERE disease=’cough’
U¨ ber die Tabelle similarities wird das Fragment Fi ausgewa¨hlt, dessen head am a¨hnlichsten zu der anti-instantiierten Konstante (im Beispiel cough) ist.
SELECT TOP 1 root.name FROM root, similarities WHERE similarities.term=’cough’ AND similarities.head = root.head ORDER BY similarities.sim DESC
Der Name der Originaltabelle F wird durch den Namen des Fragmentes Fi ersetzt und die gea¨nderte Anfrage an den entsprechenden Server gesendet. Dadurch werden alle Werte aus dem Fragment als relevante Antworten zuru¨ckgeliefert.
Als Beispiel sei der Fragmentname Respiratory. Daher wird die Anfrage gea¨ndert zu:
SELECT patientid, disease FROM respiratory und and den entsprechenden Server (hier S1) weitergeleitet.
A¨ hnliches gilt beim Einfu¨gen neuer Zeilen:
INSERT INTO ill VALUES (349, ’asthma’) wird umgeschrieben zu:
INSERT INTO respiratory VALUES (349, ’asthma’).
Auch das Lo¨schen von Werten wird so umgesetzt:
DELETE FROM ill WHERE disease=’cough’ wird zu:
DELETE FROM respiratory WHERE mesh=’cough’ 4. INTELLIGENTE REPLIKATION (6) (7) (8) (9) (10) (BPPC):
WIEDERHERSTELLUNG
Passend zum Replikationsverfahren mu¨ssen im Falle eines Serverausfalls einige Fragmente wiederhergestellt werden. Dazu werden der Originaltabelle Spalten fu¨r die jeweiligen Cluster-Identifikatoren hinzugefu¨gt. Anhand der IDs ko¨nnen die entsprechenden Fragmente rekonstruiert werden:
INSERT INTO ci SELECT * FROM rj WHERE clusterid=i
Alternativ ist die Erstellung einer sogenannten LookupTabelle [TCJM12] mo¨glich, die zu jeder Cluster-ID die beteiligten Tupelidentifikatoren abspeichert. Diese beno¨tigt jedoch einen JOIN-Operator:
INSERT INTO ci SELECT * FROM ill JOIN lookup ON (lookup.tupleid= rj.tupleid)
WHERE lookup.clusterid=i Die Lookup-Tabelle hat sich daher als ineffizienter herausgestellt. 6. DATENLOKALITÄT FÜR ABGELEITE
TE FRAGMENTIERUNGEN
Wenn auf mehrere Tabellen innerhalb einer Anfrage zugegriffen wird und diese Tabellen Join-Attribute gemeinsam haben, kann durch abgeleitete Fragmentierung die Datenlokalita¨t fu¨r die Anfragen erho¨ht werden. Zum Beispiel sei zusa¨tzlich zur Tabelle ill eine Tabelle info gegeben, die zu jeder Patienten-ID Adressangaben entha¨lt. Eine mo¨gliche Anfrage wa¨re daher, die Angaben zu Krankheiten und Adressen zu kombinieren:
SELECT a.disease, a.patientid, b.address FROM ill AS a,info AS b WHERE disease=’cough’ AND b.patientid= a.patientid
Anhand der vorgegebenen prima¨ren Fragmentierung der Tabelle ill wird dann auch die Tabelle info fragmentiert, zum Beispiel fu¨r das Fragment Respiratory: INSERT INTO inforesp SELECT a.patientid, b.address FROM respiratory AS a, info AS b WHERE b.patientid = a.patientid
Daher kann dann im Folgenden auch die Anfrage, die Angaben zu Krankheiten und Adressen kombiniert, entsprechend umgeschrieben werden:
SELECT a.disease, a.patientid, b.address FROM respiratory AS a
JOIN inforesp AS b ON (a.patientid=b.patientid)
ZUSAMMENFASSUNG UND AUSBLICK
Flexible Anfragebeantwortung unterstu¨tzt Benutzer bei der Suche nach relevanten Informationen. In unserem Verfahren wird auf eine Ontologie zuru¨ckgegriffen aufgrund derer semantisch a¨hnliche Werte in einem Cluster zusammengefasst werden ko¨nnen. Eine Fragmentierung der Originaltabelle anhand der Cluster ermo¨glichst ein effizientes Laufzeitverhalten der flexiblen Anfragebeantwortung. Durch einige Metadaten (Root-Tabelle, Similarities-Tabelle, zusa¨tzliche Spalte fu¨r Cluster-ID) werden alle typischen Datenbankoperationen unterstu¨tzt.
Zuku¨nftig soll insbesondere das dynamische Anpassen der Fragmente untersucht werden: da sich durch Einfu¨gungen und Lo¨schungen die Gro¨ßen der Fragmente stark a¨ndern ko¨nnen, mu¨ssen zur Laufzeit Fragmente verschoben werden, sowie gegebenenfalls zu kleine Fragmente in ein gro¨ßeres vereinigt werden beziehungsweise zu große Fragmente in kleinere aufgespalten werden.
Automated Silhouette Extraction for Mountain Recognition
Daniel Braun Heinrich-Heine-Universität
Institut für Informatik
Universitätsstraße 1 40225 Düsseldorf, Deutschland braun@cs.uni-duesseldorf.de ABSTRACT With the rise of digital photography and easy sharing of images over the internet, a huge amount of images with no notion of what they are showing exists. In order to overcome this problem, we – for the example of mountain recognition – introduce a method, that is able to automatically recognise a mountain shown in a photography.
Our method does not require GPS information stored in the image, since most images are not GPS tagged, either because of the absence of a GPS sensor in the device or because it has been deactivated for a lesser power consumption, which often is the case with smartphones. Instead, we propose a method that is able to automatically extract the mountain’s silhouette from a given image. This silhouette is then cleaned by removing artefacts and outliers, such as trees and clouds, with a histogram based approach. Finally, the cleaned silhouette can be compared to reference data in order to recognise the mountain that is shown in the picture. For this, time series comparison techniques can be used to find matching silhouettes. However, because of the huge number of reference silhouettes to compare against, we argue, that a preselection of those silhouettes is necessary and point out approaches to this problem.
Categories and Subject Descriptors I.4.8 [IMAGE PROCESSING AND COMPUTER VISION]: Scene Analysis—Object recognition; I.4.6 [IMAGE PROCESSING AND COMPUTER VISION]: Segmentation—Edge and feature detection; H.2.8 [DATABASE MANAGEMENT]: Database Applications —Data mining Keywords Object Recognition, Image Annotation, Outlier Detection, Image Segmentation, Skyline Recognition, Mountain Recognition, Time Series 27th GI-Workshop on Foundations of Databases (Grundlagen von Datenbanken), 26.05.2015 - 29.05.2015, Magdeburg, Germany.
Copyright is held by the author/owner(s).
Michael Singhof Heinrich-Heine-Universität
Institut für Informatik
Universitätsstraße 1 40225 Düsseldorf, Deutschland singhof@cs.uni-duesseldorf.de 1. INTRODUCTION
Sharing our experiences with digital images is a significant
part of our today’s life, which is partly a result of the high
availability of digital cameras, like in smartphones, and the
high use of social networks, that simplifies the publication
and sharing of images. As a consequence, the number of
images in the world wide web increases significantly. For
example, this can be seen on the image sharing platform
Instagram, where users share an average of 70 million new
photos per day [
As a result of such high numbers of images, searching photos which show specific objects is challenging, because the majority of these images is not properly tagged with the names of every object seen in them. So the need for efficient algorithms for automatic object recognition rises. In the last decades there were many advances in this research field, but especially the automatic identification of landmarks, which are subject to weather changes, areal erosion and vegetation, is still a challenging task, even if the amount of images with attached GPS data, which marks the geo-position of the camera when the photo was shot, is rising.
The growing spread of devices with the capability of generating GPS tags for the images, like smartphones and digital cameras with GPS units, enables many possibilities for an subsequent geo-localisation of images, due to the fact that GPS tags can significantly reduce the number of possible sights, buildings or landmarks to compare with. However, there exist too many images without the advantage of GPS tags, so that an automatic geo-localisation without prior knowledge of the camera position is still a valuable aim.
Our focus lies on the automatic landmark recognition, which we will describe by using the example of mountain recognition in images. To solve the question, which mountain can be seen on an given image, we match the skyline of the mountain in the image with silhouettes of mountains in our database. For this purpose, we have to automatically extract the exact skyline from the image, which is a difficult task, because the segmentation of the image can lead to artefacts, for instance due to weather conditions, noise, obstacles or overexposure.
In this paper we introduce a baseline segmentation algorithm, which uses an outlier detection algorithm to identify and eliminate these artefacts. The article is structured as follows: In the next section we discuss other papers related to our algorithm. We then introduce our algorithm, which consists of the three steps silhouette extraction, silhouette cleaning and silhouette matching. The section of the latter one will be a perspective of how to use the cleaned silhouette in further steps. The last chapter summarises this paper and outlines future work.
RELATED WORK
The amount of publications for automated mountain recognition increased significantly in the last two decades.
Given a high number of publicly available digital elevation
maps (DEM), the consensus in many publications [
Many approaches, like [
Baboud et al. [
Therefore, the authors introduce a robust matching metric,
using extracted edges in combination with a search space
reduction to further reduce computation time. [
All three approaches show good results for their issue,
but the need for GPS data for the processed image does
not match our problem specifications, different from Baatz
et al. [
They combine this approach with a relevance feedback-like
user interference, where the user can mark parts of the sky or
the foreground. This user intervention was needed for 49% of
the images in their dataset, which was collected during there
research. Thankfully, they published this dataset, so that
it will be used in this paper. After the contour extraction,
they match the coded contourlet with the contours extracted
from a DEM at several points on a predefined grid. At
last, when they find a suitable match, they recalculate the
geo-position of the camera. Naval et al. [
Tao et al. [
The silhouette recognition process is basically a process in three steps. The first step is the extraction of the silhouette from a given picture. This silhouette is stored as a polygonal chain. During the second step, this silhouette is cleaned by identifying and removing outliers. The cleaned silhouette is then used as the input to the third and final step, which consists of matching the silhouette against the reference data in order to be able to identify the structure in the picture.
Extracting the silhouette is the first step in the mountain
identification process described in this paper. The task of
this step is the separation of the sky from the rest of the
processed image. We therefore have a binary segmentation
task to solve, in which we check every pixel p of an image and
decide if p shows a part of the sky or not. For a human this
would be easy to do in most cases, even though it would
be too much work and time to segment great numbers of
pictures manually. Because of that, we use a growing seed
algorithm, like the algorithm described in [
The segmentation of an image generally suffers from different problems, like under-/overexposure, which results in a smaller difference between the pixel colours, or blur, which can be, for example, a result of a lossy compression of the image. In addition, our binary segmentation task has even some own problems to deal with. The first difficulty is a consequence of the motif itself, because the weather in mountainous terrain is very volatile. This and the fact that, for example in the alps, many mountain peaks are covered with snow, can make the extraction of the mountain silhouette out of an image imprecise. Furthermore differently coloured bands of cloud can lead to an extracted silhouette which lies in the sky and is therefore not part of the real skyline. The second one is a result of possible obstacles, which hide the real silhouette of the mountain or lead to smaller segments within the sky segment.
Even though we are aware of these problems, our naive segmentation algorithm cannot handle all of them. For the identification of artefacts as result of segmentation errors, we use the second step of our chain, which is described in section 3.2. Our segmentation algorithm uses the upper row of pixels as seed for the sky segment. This means that we mark the upper pixels as sky and process every neighbouring pixel to let this segment grow. For this purpose we first convert the processed photo to a gray-scale image G. Now we can define VG as overall variance of the brightness values.
Having VG, we now process every pixel p(x,y) which is not a part of the sky segment and mark it as sky candidate, if for p(x,y) it holds that
√
Bp(x,y) − meanrp(x,y) < γ · VG with Bp(x,y) the brightness of the pixel p(x,y), meanrp(x,y) as the mean of the brightness in an neighbourhood of the pixel with the radius of r and γ as a factor to scale the impact of the standard derivation. This means that we mark a pixel, if its distance to a local mean of brightness values is smaller than a fixed percentage of the global standard derivation of all brightness values. The idea behind this term is, that the border between sky and ground has in most cases a stronger contrast than the rest of the image, especially the sky. Therefore, the distance to the mean will be higher at the skyline as it will be at the border of possible clouds. With the connection of the upper bound to the standard derivation, we want to take into account the images where the brightness is very homogenous, for example due to overexposure, and therefore the contrast of the skyline decreases.
In our experience this naive assumption shows good
results for r = 5 and γ = 0.1 on most images out of the swiss
dataset published in [
1 −1 1
−1 sible candidates, we can finally let the sky segment grow. For that, we check for every pixel p(x,y), if it is a 4-connected neighbour, for explanation see the left side of figure 1, to a pixel of the sky segment and marked as sky candidate (see the previous step). If so, the pixel will get marked as sky.
This step is repeated until no more pixels can be added to the sky segment. At this point, we have a binary image, which represents the skyline as transition between the sky and the ground, like the one shown in figure 2.
For the silhouette extraction, we search a silhouette S = (v1, . . . , vn) where every vertex vi = (xi, yi) is a two dimensional point where xi describes the x-coordinate and yi describes the y-coordinate of that point in the picture. We start at the upper left pixel p(0,0) and search for the first nonsky pixel as start vertex v1 for our polygonal chain, which lies on the left pixel column with x1 = 0. Now, we have two possibilities: First, we can find no pixel, which results in checking the next column until we find a pixel or we have reached the lower right pixel of the image. Otherwise, if a possible skyline pixel was found, the algorithm tracks the transition between the sky and the ground in the following manner.
Having vi as the last extracted vertex of the silhouette, the algorithm checks the 8-connected neighbours of this point (see the right side of figure 1) and chooses the non-sky point as next vertex which has the lowest angle between the incoming line, defined by the two last vertices vi−1 and vi, and the outgoing line, defined by vi and the neighbouring point. This can easily be done, as shown in figure 3, by checking the 8-connected neighbours from vi in clockwise direction, starting at the predecessor. The only exception is the start point v1, where we set v0 = (−1, y1). This means that we choose in this case the left direct neighbour, which lies outside of the image, as predecessor.
2 1 vi−1 0 3 vi 7 4 5 6
Figure 3: An example how to choose the next silhouette point. Starting at vi−1 as predecessor of the current vertex vi, the algorithm searches in clockwise direction for the next ground pixel (blue). Therefore the third pixel will be chosen.
Now, we have the border of the mountain as chain of neighbouring pixels. To reduce the amount of vertices without loosing any information, we eliminate all vertices which bring no further information gain to the final silhouette in the last step of the extraction phase. For this, we define the
The schema S = {A1, . . . , An} for the contents in a window is known. Hence, maintaining one circular buffer as in Section 3.3 for each attribute Ai ∈ S splits each incoming tuple into its components. We propose to use a bucketing-operator that is responsible for portioning the incoming windows such that it holds n circular buffers, each buffering one attribute of the incoming tuple. Since external subscribers S1, ..., S` are known to the bucketing-operator, the operator adds itself as ”internal” subscriber to each 1 ≤ j ≤ n circular buffers, delegates the desired sizei for each external Si to all buffers.
This leads to notification of all circular buffers to the operator at the same time once sizei is achieved for some external subscriber Si. Now, the operator packages the n portions delivered to it into a collection, that is send to the external subscriber.
This allows a chain of operators where each consumes and produces a column-oriented event representation. To convert back to row-oriented event representation, another operator performs the described operations backwards. Hence, to revert the representation flip, another operator reads buckets and outputs them as a stream of regular tuples.
We propose to run these constructions in dedicated operators, since this allows sharing the costs of window portioning between several external subscribers and reverting the operation.
OPEN RESEARCH CHALLENGES
Based on existing research and related work, we cannot completely answer all relevant aspects. Therefore, we present two open research challenges in the following section. 4.1
Stream Processing on Modern Hardware
We propose an additional bucketing-operator to support event representation changes and window portioning to target GPU-specialized counterparts of existing stream operators.
On the other hand, current trends in hardware bring further
co-processors (e.g., Intel Xeon Phi or FPGA) with special
characteristics into view. Consequently, these co-processors
could be used to accelerate stream processing in addition to
the GPU. With the increasing amount of different devices,
we have to take care of optimized algorithms and execution
models for the respected processor to also reach optimized
performance [
Furthermore, with the availability of different devices, we
have to decide where to execute a given operator to reach
optimal performance. Here, it is not only important to
find the device with the best performance for the given
operator, but also to distribute the load between the devices
similar to the work of Breß et al. [
Scheduler for Heterogeneous Devices
As proposed by Breß et al. [
An interesting question is, how an advanced load balancer improves execution performance even further, if the targeted device runs a specialized kernel. This could be achieved with a more high-level load balancer that could decide on its own when to send jobs to device with an unified kernel, and when to to a dedicated device with highly optimized execution code that fits most to the device architecture.
RELATED WORK
The design space of DBMSs using GPU as co-processor
is well explored [
To enable GPU processing capabilities it is reasonable to
process batches, since a GPU might outperform a CPU only
if a bulk of data is present at once. Some SPSs do only
support a tuple-at-a-time approach [
In this paper we motivated and introduced a concept for a dedicated stream processing operator, the bucketing-operator, that consumes a stream of length-varying windows and produces a stream of fixed-sized window portions with a columnoriented event representation. We motivated the revertible event representation transposition to match the GPU architecture better, since a GPU uses the SIMD approach and otherwise we would waste memory and increase transfer costs.
However, we suggest a strategy to perform bucketing using a fixed-sized circular buffer for each attribute of a given schema.
This approach is efficient in time and space, since it mainly depends linearly on the actual window content length and could be stored in a predefined sized buffer per-attribute.
We ensured here, that data corruption cannot occur using our construction.
Finally, we identified two research questions for processing data streams on modern hardware and scheduling for heterogeneous devices.
ACKNOWLEDGMENTS
We thank Bernhard Seeger for fruitful discussions that heavily influenced this work.
Where- und Why-Provenance für syntaktisch reiches SQL durch Kombination von Programmanalysetechniken
Tobias Müller
Universität Tübingen
Tübingen, Deutschland to.mueller@uni-tuebingen.de ABSTRACT Das hier vorgestellte Verfahren ermöglicht die Analyse der Data Provenance von beliebigen SQL-Queries. Von der ebenfalls hier skizzierten Implementierung des Verfahrens werden unter anderem unterstützt: Subqueries, Aggregierungen, rekursive Queries und Window Functions. Eingabequeries werden zunächst in eine imperative Programmiersprache übersetzt. Der Programmcode wird mit einem neuen Verfahren analysiert, das auf bekannte Techniken aus dem Bereich der Programmanalyse aufbaut: Program Slicing, Kontrollflussanalyse und abstrakte Interpretation. Dadurch erhält man eine Berechnung von Where- und Why-Provenance auf der Granularitätsebene einzelner Tabellenzellen.
Categories and Subject Descriptors General Terms Languages Keywords Data provenance, SQL, program analysis
Wir stellen einen neuen Ansatz für die Analyse der Data
Provenance [
Die theoretische Anwendbarkeit auf beliebige Queries wird
dadurch erreicht, dass wir Eingabequeries zuerst in eine
imperative (Turing-vollständige) Programmiersprache
übersetzen, das resultierende Programm in eine linearisierte Form
(erläutert in Abschnitt 4) umwandeln und anschließend die
eigentliche Provenance-Analyse durchführen. Dieser von uns
entwickelte Ansatz basiert auf dem Prinzip des Program
Slicing [
Von bisherigen Arbeiten wurde sukzessive der Umfang der
analysierbaren SQL-Konstrukte erweitert. Dazu zählen
beispielsweise geschachtelte Subqueries [
BEISPIEL-QUERIES
Im Folgenden werden zwei Beispiel-Queries und die Ergebnisse der mit unserer Implementierung durchgeführten Provenance-Analyse vorgestellt. Die erste Query greift ein Beispiel aus der Literatur auf und die zweite wurde gewählt, um die Mächtigkeit unseres Ansatzes zu demonstrieren. agencies
name based_in phone t1 BayTours San Francisco 415-1200 t2 HarborCruz Santa Cruz 831-3000 externaltours
name destination type t3 BayTours San Francisco cable car t4 BayTours Santa Cruz bus t5 BayTours Santa Cruz boat t6 BayTours Monterey boat t7 HarborCruz Monterey boat t8 HarborCruz Carmel train Abbildung 1: Bootstouren-Beispiel: Where- und Why-Provenance sind markiert mit sowie .
Falls beides zutrifft, wird verwendet. Tupel sind mit ti bezeichnet.
SELECT e.name, a.phone FROM agencies AS a,
externaltours AS e WHERE a.name = e.name AND e.type = b’oat’ output
name phone HarborCruz 831-3000 BayTours 415-1200 BayTours 1 415-1200
2 (a) SFW-Query (b) Ergebnis Abbildung 2: Welche Agenturen bieten Bootstouren an? 2.1
Bootstouren
Diese Beispiel-Query stammt aus [
Die Ausgaberelation steht in Abbildung 2(b).
Zelle 1 ist hier als Where-abhängig von t5: BayTours markiert. Ein Blick auf die SQL-Query (SELECT e.name) bestätigt dieses Ergebnis: denn hier werden Werte aus der Eingabetabelle ins Resultat kopiert. Dies entspricht den Kriterien von Where-Provenance, wie wir sie in Abschnitt 1 angegeben haben.
Die Markierungen zeigen außerdem Why-Abhängigkeiten von t1: BayTours , t5: BayTours und t5: boat . Diese drei Werte werden im WHERE-Teil der SQL-Query für die Joinund Filterkriterien benutzt.
1 und 2 zeigen, dass die wertemäßig nicht unterscheidbaren BayTours und BayTours anhand ihrer jeweiligen Provenance (t5 oder t6) unterscheidbar werden.
3 veranschaulicht, dass Data Provenance entgegen der wörtlichen Bedeutung auch in Vorwärts-Richtung funktioniert. Die Farbmarkierungen besagen, dass t1: 415-1200 mit zwei Werten von der Ausgabetabelle auf Werteebene zusammenhängt. Konkret wird hier die Telefonnummer zwei Mal kopiert.
Die hier vorgestellte Provenance-Analyse einer rekursiven Query ist nach dem Wissen der Autoren mit keiner anderen existierenden Implementierung möglich. Die Query besteht auch aus einer Anzahl von Funktionsaufrufen. Interessante Ausschnitte des Ergebnisses unserer Provenance-Analyse werden erneut mit farbigen Markierungen dargestellt.
Abbildung 3(a) zeigt die Eingaberelationen. compounds enthält chemische Summenformeln und ihre Bezeichnungen.
In Tabelle fsm ist ein endlicher Automat codiert, der die Syntax dieser Formeln überprüfen kann.
Die SQL-Query in Abbildung 3(b) führt diesen Automaten aus. Da alle Formeln in compounds parallel verarbeitet werden, existieren mehrere Automaten parallel. In jedem Schritt eines Automaten wird das erste Zeichen einer Formel abgeschnitten und der entsprechende Zustandsübergang durchgeführt. Aktueller Zustand und “Restformel” sind in der Tabelle run gespeichert, die bei jedem Schritt der Automaten neu berechnet wird. In Abbildung 3(c) sind zwei Versionen von run abgebildet: direkt nach der Initialisierung (step: 0) und nach drei Schritten (step: 3). Wenn die Formeln vollständig verzehrt sind, beendet sich der rekursive Teil der Query. Als Endresultat werden die Ableitungsschritte für citrate (siehe Abbildung 3(d)) zurückgegeben.
Die Where-Provenance von 4 zeigt an, von welchen Werten O73- abgeleitet wurde. Dazu zählt erst einmal die vollständige Summenformel t9: C6H5O73- . Aber auch alle Zwischenzustände werden von der Analyse erfasst, wie anhand der Markierungen in Abbildung 3(c) zu erkennen ist.
Die interessantesten Why-Abhängigkeiten von 4 sind innerhalb der Tupel t12 und t13 zu finden. Das sind nämlich gerade die Kanten des Automaten, die besucht wurden, um O73- abzuleiten. compounds compound t9 citrate t11 hydronium HC36HO1+2O6 t10 glucose formula
C6H5O73t12 t13 t14 t15 t16 t17 t18 (a) Eingabetabellen (b) Rekursive Query (c) Zwischenergebnisse (d) Ergebnis Abbildung 3: Endlicher Automat, der die Syntax von chemischen Summenformeln überprüft. 1 def query(agencies , externaltours ): 2 #FROM clause: read source tables 3 rows = [] 4 for tupVar2 in agencies: 5 for tupVar3 in externaltours: 6 rs = {"tupVar2": tupVar2 , 7 "tupVar3": tupVar3 , 8 "tmp": {}, 9 } 10 rows.append(rs) 11 #WHERE clause: compute where predicate 12 rowIdx = 0 13 while rowIdx < len(rows): 14 rs = rows[rowIdx] 15 col4 = rs["tupVar2"]["name"] 16 col5 = rs["tupVar3"]["name"] 17 res6 = col4 == col5 18 col7 = rs["tupVar3"]["type"] 19 val8 = "boat" 20 res9 = col7 == val8 21 res10 = res6 and res9 22 rs["tmp"]["where"] = res10 23 rowIdx = rowIdx + 1 24 #WHERE clause: apply where predicate 25 filtered = [] 26 for rs in rows: 27 if rs["tmp"]["where"]: 28 filtered.append(rs) 29 rows = filtered 30 #SELECT clause: compute result columns 31 rowIdx = 0 32 while rowIdx < len(rows): 33 rs = rows[rowIdx] 34 col11 = rs["tupVar3"]["name"] 35 col12 = rs["tupVar2"]["phone"] 36 rs["tmp"]["eval0"] = col11 37 rs["tmp"]["eval1"] = col12 38 rowIdx = rowIdx + 1 39 #SELECT clause: assemble result table 40 ship = [] 41 for rs in rows: 42 row = {} 43 row["name"] = rs["tmp"]["eval0"] 44 row["phone"] = rs["tmp"]["eval1"] 45 ship.append(row) 46 return ship
Listing 1: Übersetzung der Bootstouren-Query. Es findet (noch) keine Code-Optimierung statt.
Zuletzt wird mit 5 noch die Einsicht transportiert, dass die Schrittzahl des Automaten keinerlei Einfluss auf die Ableitung von citrate hat. Die Markierungen zeigen lediglich eine Where-Provenance zwischen den Schritten 0 bis 8 an, die auf das Inkrementieren zurückzuführen ist. Es gibt keine Why-Provenance, das heißt keine (versehentliche) Beeinflussung des Endresultats durch die Schrittzählung. 3. SQL-ÜBERSETZUNG
Die zu analysierenden SQL-Queries werden in unserer Implementierung zunächst in Python-Programme übersetzt.
Python hat als Zwischensprache den Vorteil, sehr leichtgewichtig und daher für die weitere Analyse gut zugänglich
Abbildung 4: Hauptelemente der ProvenanceAnalyse zu sein. Es wird außerdem von Kooperationspartnern eingesetzt. Ein Nachteil von Python ist die schlechtere Performance (gegenüber Sprachen wie C). Es gibt jedoch keinen Hinderungsgrund, die mit Hilfe von Python erarbeiteten Techniken der Provenance-Analyse nicht auf andere Sprachen wie LLVM zu übertragen.
Damit würden wir einem aktuellen Forschungstrend in der
Datenbank-Community folgen, SQL nicht länger mit dem
Volcano-Iterator-Model zu implementieren, sondern Queries
just-in-time zu kompilieren (siehe [
Aus Platzgründen wird der von uns verwendete Übersetzer nur anhand eines Beispiels vorgestellt. Listing 1 zeigt, wie die Übersetzung von Query 2(a) aussieht. Je Query oder Sub-Query wird eine eigene Python-Funktion erzeugt. Die Argumente und Rückgabewerte sind Tabellen, die in Python als Listen von Dictionaries implementiert sind. Die SQL-Klauseln einer Query werden in eine Reihenfolge gebracht, die eine Berechnung im imperativen Paradigma erlaubt: SFW wird beispielsweise zu FWS. 4. PROVENANCE-ANALYSE
IN ZWEI STUFEN
Wie in Abbildung 4 dargestellt, teilt sich die ProvenanceAnalyse im Wesentlichen auf zwei Schritte auf: 1 Kontrollflussanalyse (dynamisch, zur Laufzeit) und 2 abstrakte Interpretation (statisch, zur Kompilierzeit).
Die Kontrollflussanalyse ist dafür zuständig, alle für den Kontrollfluss benötigten Prädikate zu bestimmen und deren Werte zu speichern. Beispielsweise würde bei der Ausführung einer if-Anweisung die zugehörige Kontrollflussinformation darin bestehen, ob entweder der if- oder der elseRumpf ausgeführt wird. Die Information kann durch einen einzelnen booleschen Wert codiert werden.
In Phase 2 findet die eigentliche Provenance-Analyse statt. Hier wird das Kontrollfluss-Log benutzt, um den tatsächlichen Ausführungspfad nachvollziehen zu können, den das Programm zur Laufzeit genommen hat.
In Abschnitt 4.1 wird die Motivation für die soeben skizzierte Struktur geschildert sowie ein Bezug zu Ergebnissen der theoretischen Informatik hergestellt, die einer Programmanalyse harte Grenzen setzt. Abschnitt 5 erläutert die beiden Analyseschritte genauer sowie deren Implementierung in Python. 4.1 Linearisierung
Eine rein statische Provenance-Analyse ist im Allgemeinen für Python-Programme nicht möglich, denn Python ist eine Turing-vollständige Programmiersprache. Der Satz von Rice besagt, dass nicht-triviale Laufzeiteigenschaften (wie Data Provenance) für allgemeine Turing-Maschinen nicht algorithmisch entscheidbar sind.
Um den Konsequenzen des Satzes von Rice zu entgehen, ändert dieses Verfahren die Voraussetzungen. Wie in Abbildung 4 dargestellt, wird der zur Laufzeit aufgezeichnete Kontrollfluss an die abstrakte Interpretation übergeben.
Zu Kontrollflussanweisungen zählen unter anderem if- und while-Anweisungen. Für diese Konstrukte besteht das zugehörige Kontrollfluss-Log lediglich aus einer Folge von booleschen Werten: • Wird entweder if oder else ausgeführt? • Wird der Rumpf von while (nochmal) ausgeführt oder
wird die Schleife beendet?
Dieses Log steht also während der statischen Analyse zur Verfügung. Das heißt, die statische Analyse weiß für jedes if x:, ob es in Wirklichkeit entweder ein if True: oder if False: ist - je nachdem, ob True oder False im Log steht.
Mit dem Kontrollfluss-Log findet deshalb eine Linearisierung des Python-Programms statt. Die Abfolge der Anweisungen im Programm ist statisch festgelegt, weil der Kontrollfluss festgelegt ist. Kontrollfluss-Konstrukte verhalten sich nun transparent und im einfachsten Fall besteht die restliche Analyse des Programms nur noch darin, Zuweisungen an Variablen zu betrachten.
Dadurch liegt in 2 keine Turing-Vollständigkeit mehr vor. Der Satz von Rice gilt nicht mehr und eine ProvenanceAnalyse ist (quasi-statisch) möglich.
Das Beispiel in Abschnitt 5 wird das verdeutlichen. 4.2
Granularität und Auflösung
Als Granularität (oder level of detail) wird in [
Orthogonal dazu wollen wir den Begriff Auflösung verwenden, um damit die Größe der Programmfragmente zu bezeichnen, für die am Ende der Analyse eine Data Provenane ausgegeben wird.
Beispielsweise könnte es in einer niedrigen Auflösung so sein, dass das Programm nur als Ganzes analysiert wird.
Das heißt, die Data Provenance bezieht sich gerade auf die Ein/Ausgabedaten des Programms selbst und zeigt an, wie die Ausgabedaten von den Eingabedaten abhängig sind. Eine andere Variante bestünde darin, für jeden einzelnen Ausdruck in diesem Programm eine Data Provenance auszugeben. Das heißt, für einen Ausdruck wie b+c wird als Ergebnis die Abhängigkeit von den Einzelwerten b sowie c ausgegeben. Hier ist die Auflösung sehr hoch.
Von uns wurde als Auflösung die Ebene von Funktionsaufrufen benutzerdefinierter Funktionen gewählt. Im Ergebnis der Provenance-Analyse sind deshalb die Parameter und Rückgabewerte von Funktionsaufrufen aufgeführt sowie die dazugehörende Data Provenance. 5. IMPLEMENTIERUNG
Als Grundlage für die Implementierung der ProvenanceAnalyse dient CPython in Version 3.4. Dabei handelt es sich um die stabile und zum Zeitpunkt des Schreibens dieses Artikels aktuelle Referenzimplementation von Python. Intern übersetzt sie Quelltext in Bytecode, der anschließend in der zugehörigen virtuellen Maschine (VM) ausgeführt wird. Als Zwischenschritt während der Übersetzung erzeugt CPython einen Abstract Syntax Tree (AST), auf dessen Basis wir das Analyseverfahren implementiert haben.
In Abbildung 5 ist dargestellt, wie die einzelnen PythonKomponenten zusammenarbeiten. Mit weißem Hintergrund dargestellt sind die ein/ausgehenden Datensätze (Relationen) sowie der Python Programmcode, der analysiert wer
Abbildung 5: Implementierung
Komponenten der
Pythonden soll. Grau hinterlegt sind Komponenten der CPythonImplementierung selbst, die unmodifiziert verwendet werden. In schwarz ist, was wir zusätzlich implementiert haben.
Während der Analyse wird das zu einem AST kompilierte Eingabeprogramm zwei Mal verarbeitet. In Schritt 1 wird es zunächst instrumentiert. Dabei werden zusätzliche Python-Anweisungen eingefügt, die einerseits die vorhandene Funktionalität nicht verändern und andererseits für das Schreiben des Kontrollfluss-Log zuständig sind. Das so modifizierte Programm wird zu Bytecode kompiliert und anschließend mit der VM ausgeführt. Während der Ausführung werden Eingabe/Ausgabedaten gelesen/geschrieben sowie das Kontrollfluss-Log produziert. Schritt 1 wird in Abschnitt 5.1 genauer beschrieben.
In Schritt 2 wird das unmodifizierte (nicht instrumentierte) Eingabeprogramm erneut hergenommen und mit Hilfe des Kontrollfluss-Logs die eigentliche Provenance-Analyse durchgeführt. Eine genaue Beschreibung dieses Teils folgt in Abschnitt 5.2. Bemerkenswert ist, dass hier keine Eingabedaten benötigt werden. Die abstrakte Interpretation findet auf symbolischer Ebene statt, das heißt es wird lediglich ermittelt, wie die im Programm benutzten Variablen voneinander abhängig sind. Dies genügt, um sowohl Why- als auch Where-Provenance zu berechnen. 5.1
Instrumentierung
Allgemein gesprochen müssen diejenigen Sprachkonstrukte instrumentiert werden, deren Verhalten bezüglich Data Provenance sich nicht durch rein statische Analyse bestimmen lässt. Bisher instrumentieren wir zwei Kategorien von Sprachkonstrukten: (i) Kontrollfluss und (ii) Indexzugriff.
Listing 2 zeigt ein bereits instrumentiertes Programmfragment, das je ein Beispiel für beide Fälle enthält. Die Funktion dow() erhält als Argumente den Wochentag als Zahlenwert (num = 0...6) und eine Liste mit Namen von Wochentagen. Sie liefert eine String-Repräsentation zurück.
Sie unterstützt außerdem zwei verschiedene Datumsformate: Wochenbeginn am Montag (fmt = True) oder am Sonntag (fmt = False). 6 7 8 9 10 11 12 1 days = ["Sun","Mon","Tue", 2 "Wed","Thu","Fri","Sat"] 3 def dow(num , fmt , days ): 4 if fmt: 5 #true: week starts on Monday logCtrl(True)
Nachdem die Kontrollfluss-Logs erzeugt worden sind, kann jetzt die eigentliche Ableitung der Data Provenance stattfinden. Dazu werden wie in Abbildung 5 dargestellt, lediglich das Eingabeprogramm zusammen mit den Logs verwendet.
Daten sind an dieser Phase nicht beteiligt. Dementsprechend werden auch keine Berechnungen von Werten ausgeführt, was Systemressourcen spart.
Die abstrakte Interpretation wird durchgeführt, indem alle Anweisungen des Programms in derselben Reihenfolge nachvollzogen werden, in der sie auch zur Laufzeit ausgeführt wurden. Die richtige Reihenfolge einzuhalten ist dank des aufgezeichneten Kontrollflusses sehr einfach. Immer dann, wenn eine Kontrollflussentscheidung benötigt wird (zum Beispiel: if- oder else-Block ausführen), kann diese Information im Kontrollfluss-Log nachgeschlagen werden.
Where-Provenance.
Während die Anweisungen nacheinander interpretiert wer1 days = [(),(),() , 2 () ,() ,() ,()] 3 def dow(num , fmt , days ): 4 if fmt: #fmt: True 5 pos = (num +()) % () 6 else: 7 pos = num 8 res = days[pos] #pos: 5 9 return res 10 dow((), (), days) #returns: ()
Listing 3: Pseudocode aus Sicht der abstrakten Interpretation. den, wird eine Variablenumgebung gepflegt und mit jeder interpretierten Anweisung gegebenenfalls aktualisiert. Die Umgebung beinhaltet alle derzeit sichtbaren Variablen zusammen mit ihren jeweiligen Abhängigkeiten von den Eingabedaten.
Der Aufbau dieser Umgebung ist ein inkrementeller Prozess. Jede Zuweisung einer Variablen, wie zum Beispiel in a = b, wird eine entsprechende Aktualisierung der Umgebung nach sich ziehen. In diesem Beispiel müssten alle Abhängigkeiten von b nach a kopiert werden.
Auf diese Weise wird die Umgebung ständig aktuell gehalten und referenziert in ihren Abhängigkeiten stets die Eingabedaten. Am Ende der Analyse braucht nur noch die gewünschte Variable, zum Beispiel res, in der Umgebung nachgeschlagen zu werden.
Why-Provenance.
Die Ausführung von Anweisungen in einem if- oder elseRumpf sind abhängig vom zugehörigen Prädikat des if/elseKonstrukts. Diese Abhängigkeit modellieren wir als WhyProvenance.
In der Analyse wird dazu eine Menge an Abhängigkeiten gepflegt, die dem Kontrollfluss selbst zugeordnet ist. Bei Eintritt in den Rumpf einer if-Anweisung wird dem Kontrollfluss eine Abhängigkeit vom Prädikat dieser if-Anweisung zugeordnet. Allen Zuweisungen, die in diesem Rumpf ausgeführt werden, werden dann wiederum die Abhängigkeiten des Kontrollflusses in Form von Why-Provenance hinzugefügt.
Nachdem der if-Rumpf abgearbeitet ist, werden die Abhängigkeiten des Kontrollflusses wieder zurückgesetzt. Ob if- oder else-Rumpf ausgeführt werden, macht hier keinen Unterschied: in beiden Fällen gilt dasselbe Prädikat. Die Interpretation von Schleifen funktioniert analog.
Beispiel-Analyse.
In Listing 3 ist abgedruckt, wie sich das aus dem Instrumentierungsschritt bereits bekannte Programmfragment in Schritt 2 der Provenance-Analyse darstellen würde. Alle vorkommenden atomaren Werte sind durch () ersetzt worden. Code in dieser Form wird nicht erzeugt, doch das Listing veranschaulicht, auf welcher Basis die abstrakte Interpretation arbeitet.
Anhand dieses Beispiels wird nun dargestellt, wie die Ableitung der Data Provenance funktioniert. Das Ergebnis dieser Analyse besteht gemäß der gewählten Granularität und Auflösung (siehe Abschnitt 4.2) darin, wie die Variable res von den Funktionsparametern abhängig ist.
Um die Analyse zu initialisieren, werden die in den Funktionsparametern vorkommenden Werte durch künstliche ids repräsentiert. Abbildung 6 zeigt die im Beispiel gewählte Repräsentation, die aus ansteigenden natürlichen Zahlen besteht. Die Variable days ist eine Liste und enthält dementsprechend für jedes Listenelement einen anderen Repräsentanten. Das tiefgestellte e soll anzeigen, dass eine WhereAbhängigkeit besteht (= Abhängigkeit vom Wert an dieser Stelle). Why-Abhängigkeiten kommen später hinzu und werden entsprechend durch y gekennzeichnet.
Diese Repräsentanten ersetzen während der abstrakten Interpretation die tatsächlichen Werte. Am Ende der Analyse von dow() wird die Variable res nicht mit dem Wert "Fri" belegt sein, sondern mit einer Menge von Repräsentanten.
In Tabelle 1 sind die einzelnen Analyseschritte der abstrakten Interpretation aufgeführt. In der ersten Spalte steht die Zeilennummer des Python-Statements, das soeben interpretiert wurde. Die mittlere Spalte enthält die Abhängigkeiten des Kontrollflusses. Die letzte Spalte zeigt den Inhalt der Variablenumgebung. Um die Übersichtlichkeit zu verbessern, wird hier die Variable days nicht dargestellt.
In Zeile 3 wird die Funktion betreten. Hier findet die Initialisierung der Datenstrukturen statt, das heißt die ids 0..8 werden vergeben. num, fmt und days sind die Parameter der Funktion und werden der Umgebung hinzugefügt.
In Zeile 4 beginnt das if/else-Konstrukt. Hier werden zunächst die Abhängigkeiten des if/else-Prädikats fmt den Kontrollfluss-Abhängigkeiten hinzugefügt. Dabei findet eine Transformation von 8e zu 8y statt. Die Umgebung bleibt unverändert. Als dritter Punkt wird das Kontrollfluss-Log gelesen, um festzustellen, ob der if- oder else-Rumpf besucht werden soll. Das Log liefert ein True zurück, also wird eine Analyse des if-Rumpfs durchgeführt.
Zeile 5 enthält eine Zuweisung an die Variable pos. Dazu wird zunächst der Ausdruck (num+()) % () analysiert. Die beiden () haben hier keine Abhängigkeiten, werden also einfach ignoriert. Die Abhängigkeiten von num werden kopiert: 7e. Außerdem werden die Kontrollflussabhängigkeiten übernommen: 8y.
Zuletzt findet in Zeile 8 ein Listenzugriff statt. Hier wird das Indices-Log bemüht, das den Index 5 enthält. An 5.
Stelle von days befindet sich 5e und wird nach res kopiert.
Darüber hinaus hat der Index wie auch der Kontrollfluss eine steuernde Funktion. Deshalb wird der Inhalt von pos als Why-Provenance kopiert.
Das Ergebnis der Analyse für res ist: [8y, 7y, 5e], also Where-Abhängigkeit von "Fri" und Why-Abhängigkeit von fmt: True und num: 4.
ZUSAMMENFASSUNG UND AUSBLICK
Unser hier vorgestellte Ansatz und seine konkrete Implementierung erweitert die bisherigen Grenzen der Provenance-Analyse von SQL. Window Functions und rekursive Queries sind Bestandteile aktueller DBMS-Implementierungen und können von unserem Prototypen analysiert werden.
Derzeit wird im Rahmen einer studentischen Arbeit eine zusätzliche Python-Implementierung der hier vorgestellten Provenance-Analyse entwickelt. Ihr Merkmal besteht darin, dass sie Bytecode direkt analysiert (statt den Python-AST).
Abhängigkeiten
Kontrollfluss Variablen Zeile Wir versprechen uns eine Performanceverbesserung von dieser neuen Implementierung.
Als weitere Implementierung ist LLVM geplant, um
mittels [
Habitat [
Large-scale Analysis of Event Data Stefan Hagedorn
TU Ilmenau, Germany stefan.hagedorn@tuilmenau.de
Kai-Uwe Sattler TU Ilmenau, Germany kus@tu-ilmenau.de
Michael Gertz Heidelberg University,
Germany gertz@informatik.uniheidelberg.de ABSTRACT With the availability of numerous sources and the development of sophisticated text analysis and information retrieval techniques, more and more spatio-temporal data are extracted from texts such as news documents or social network data. Temporal and geographic information obtained this way often form some kind of event, describing when and where something happened. An important task in the context of business intelligence and document exploration applications is the correlation of events in terms of their temporal, geographic or even semantic properties. In this paper we discuss the tasks related to event data analysis, ranging from the extraction of events to determining events that are similar in terms of space and time by using skyline processing and clustering. We present a framework implemented in Apache Spark that provides operators supporting these tasks and thus allows to build analysis pipelines. 1. INTRODUCTION
Traditionally, research on querying and analyzing
spatiotemporal data focuses on data obtained from sensors that
record the evolution and movement of objects in 2- or
3dimensional space over time. Typical examples of such data
include trajectories of moving objects (e.g., [
A prominent source for event data are textual
information from newsfeeds, websites, and social media such as
blogs, tweets or social networks. Underlying the extraction
of such information about events are temporal taggers for
the temporal component and geo-taggers for the spatial or
geographic components [
The result of such a query is a list of pointers to documents in which similar (correlated) events have been detected.
For such correlation tasks, one is facing several challenges ranging from extracting event data from documents, dealing with imprecise event specifications resulting from the extraction process, to exploiting different correlation techniques for finding similar events, to scalable processing for large datasets.
In this paper, we describe a framework for analyzing event data and detecting correlations between events. Based on a model for spatio-temporal events at different granularities we discuss corresponding distance measures. We present the analysis tasks and discuss how these tasks can be supported by a set of basic operators for extracting event data from text documents, preparing the data, and analyzing event correlations using top-k and skyline processing as well as clustering.
We further describe how these operators are supported as transformation operators in Apache Spark and outline the support for explorative analyses.
An important data analysis task is to find similar events, i.e. events that share the same context or have other values in common. In this paper, we consider the spatio-temporal aspect of events for determining similarities, i.e., we focus on the similarity of their respective location and/or time of occurrence.
For our analysis framework, we assume an event model in which information about events has been extracted from some document (see Sect. 4) and is represented by useful and necessary information like ID, description, origin, etc. as well as a temporal and a geographic component, describing the when and where. The expressions underlying these components are based on concept hierarchies for time and space, as shown in Figure 1.
year month day country state city
The temporal as well as the spatial expressions can be of different granularities. For temporal expressions we consider days to be of the finest and years of the coarsest granularity. Of course one could also extend this model with further granularity levels, such as weeks, hours, or minutes.
In this paper, however, and for the sake of simplicity, we will only consider days, months, and years. We denote the corresponding domains as T = {Tday, Tmonth, Tyear}. For example, “2001-05-20”, “2013-05”, and “1995” are all valid temporal expressions from these three different domains.
Analogously, geographic expressions are taken from the domains in G = {Gcity, Gstate, Gcountry}. We assume that with each expression a spatial object in the form of a single polygon (without holes) is associated. For example, the geographic expressions “Heidelberg” and “Germany” are both valid expressions of type Gcity and Gcountry, respectively.
Definition. (Event) Given concept hierarchies T and G for temporal and geographic expressions, respectively. An event e = ht, gi consists of a temporal expression t with t.type ∈ T and a geographic expression g with g.type ∈ G.
Examples of (imprecise) event specifications are (2013-0902, Munich), (1955, Germany), or (2000-04, Bavaria). To account for these types of uncertainties, in our framework we make the following assumptions: 1. Temporal and geographic expressions of the finest gran
ularity are certain. 2. Every temporal (resp. geographic) expression of type
P 0 that refines a given temporal (resp. geographic) expression of type P , with P 0 being of finer granularity than P , is equally likely.
Distance Measures. To determine the similarity between events, a distance measure is needed that takes both the temporal and the geographic component of an event into account, both of which can be imprecise.
Precise events are those events for which both the location and temporal information is given as a fine-grained concept, i.e., they are defined on the city and day level. For such events, calculating the distance is trivial resulting in a scalar value for time (e.g., distance in days) and location (e.g. distance in meters). Both values can be combined into a single (weighted) result. Although we cannot use the traditional distance functions for events that are imprecise in at least one component, we can specify new distance functions accordingly. However, the definition of such functions is beyond the scope of this paper and we will give only a brief overview below.
First, we convert the imprecise event data into intervals and regions. As imprecise temporal data is defined as a month or year (to be imprecise the day part is missing), we can create an interval of days that starts with the minimal possible day, i.e., the first day of the corresponding month or a year and ends with the maximal possible day, which is the last day of the month or year, respectively. Each subinterval is called a valid instance of this interval. As an example consider the imprecise temporal expression “2014-05” that is mapped to the (right-open) interval i = [2014-05-01, 201405-30]). Note that any subinterval in i is a valid instance of the temporal expression. Analogously, for imprecise geographic expression, i.e., expressions not at the city level, a polygon (or its minimum bounding box) is used. Then, a function that calculates the distance between such intervals and between polygons/boxes is needed. Such distance function can yield a scalar value, which may be the average distance between points in the respective intervals or polygons, or it can yield an interval, representing the minimum and maximum distance between the intervals/polygons.
The Hausdorff distance is a typical approach to calculate the distance between two intervals or polygons as a scalar value. Its main idea is to compute the maximum distance between any point in one interval to any other point of the second interval. For two temporal intervals t1 and t2, the distance can be computed as dH (t1, t2) := max{max dh(i1, t2), max dh(i2, t1)}
i1∈t1 i2∈t2 where the distance dh(i, t) between a day i and a temporal interval t defined as dh(i, t) := mini0∈t(|i − i0|).
For polygons/boxes, the Hausdorff distance can be defined as follows: dH (g1, g2) := max
x∈g1 ym∈ign2 ||x − y||
This is the greatest distance from a point in g1 to the closest point in g2. However, the calculation of this distance measure can become very expensive as the distance from every point in the first interval to every other point in the second interval has to be computed. For temporal intervals this is not a big problem, because when taking years as the most imprecise and days as most precise level, such an interval can have only 365 (or 366) points at most. However, for polygons the set of inner points is in principle infinite.
On the one hand, one could use the cities that are located in the respective region. This approach may not lead to good results as many cities may be clustered around a large metropolis, whereas in rural regions only very few cities can be found. On the other hand, one could impose a raster on the respective regions using a fixed grid. Then, only the points of this grid will be used for calculations. Then, however, the definition of the grid size may be difficult since choosing a small grid step size may lead to many data points that will take part in the calculation and thus, will not improve the computation time. Choosing a large grid size will result in only very few data points, which might again result in incorrect distance values. In order to use common distance functions, one could reduce a polygon to a single point that represents this polygon, e.g., the center point.
However, these simplifications result in distances that may not necessarily reflect the real distances. Therefore, more sophisticated distance functions are needed.
Analysis of event data comprises several tasks. Depending on the sources of events (structured data, text documents) and the specific questions different tasks have to be combined in an analysis pipeline. In addition, such analyses are often interactive and explorative processes requiring a flexible combination of a set of powerful extraction and correlation operators. The whole process is depicted in Fig. 2.
In the following, we describe a basic set of tasks that our framework supports by dedicated operators. 3.1
Prior to any analysis task event information needs to be extracted from the text documents of a given corpus, such as Wikipedia or news articles. As an event is assumed to be composed of a temporal expression describing the “when” of an event and a geographic expression describing the “where” of an event, respective event components need to be determined in a given text and mapped to some standard format. The function of a temporal tagger is to determine such temporal information and to map each piece of information found to a temporal expression. One typically distinguishes between explicit, implicit and relative information temporal information. Explicit temporal information refers to a sequence of tokens that describe an exact date, month in a year or year, e.g., “April 1, 2015”. Implicit temporal information often refers to holidays or some named events, such as “Independence Day 2015” or “Summer Olympics 2012”.
Finally, relative temporal information can only be
determined using the context or document in which the token
sequence appears. For example, in this paper, the string
“last year” would refer to the year 2014. Popular
temporal taggers such as HeidelTime [
Similarly, for geographic information in documents, a geotagger is employed. Popular tools include GeoNames1 or Yahoo! Placemaker2. Mapping token sequences found in a text to some standardized format, however, is less trivial. For example, most taggers would map the string “Magdeburg” to a latitude/longitude pair rather than to some complex polygon description. Also, several geo-taggers also include some information about the granularity of the geographic expression based on concept hierarchies.
Once a temporal tagger and a geo-tagger have extracted and mapped temporal expressions from a given text, events are formed. In the most simple case, an event is a pair consisting of a temporal expression and a geographic expression found in close text proximity, typically at the sentence level. 1http://www.geonames.org/ 2https://developer.yahoo.com/boss/geo/
All events extracted from a document or document collection are then stored based on our event model described in Sect. 2. For each event detected, it describes the normalized temporal and geographic expression, the granularity of the expressions, and also some offset information (in what document and at what position each of the two components have been determined). 3.2
Nearest Neighbor Queries.
A straightforward solution to find correlated, i.e., similar, events is to find the neighbors of a given reference event.
Given a set of events E, a reference event er and a distance function dist, the task is to find the set kNN(er) of the k nearest events. In the case of our spatio-temporal event data this requires a single distance measure, which is usually defined using weights for the spatial and temporal distances. These weights are necessary, because we cannot directly combine the spatial distance with the temporal distance into one distance measure. However, with the weights we can adjust the impact of the spatial and temporal distance to the overall distance:
dist(e1, e2) = wg · distg(e1, e2) + wt · distt(e1, e2)
where wt, wg ∈ [
Skyline.
In contrast to the Nearest Neighbor search, Skyline queries do not need weights for the spatial and temporal distance, which are often difficult to determine. Adapted to our scenario, the notion of the Skyline algorithm is to find those events in E that “match” a query event q = htq, gqi best.
Since we consider two dimension for events, time and space, it is thus intuitive to employ a skyline-based approach as there might be events that match tq well but not gq, and vice versa. A core concept of skylines is the dominance relationship. The skyline Sq consists of all events that are not dominated by any other event in E with respect to q:
Sq = {ei|ei ∈ E ∧ ¬∃ej ∈ E : ej 6= ei ∧ ej q ei} where q denotes a dominance relationship with ej q ei meaning that ej is “in closer proximity to q” than ei. Because the dominance of an event with respect to another event is determined based on their respective distances to q, the distance function outlined before comes into play.
Clustering.
Other than in the two approaches mentioned before, for
clustering, a definition of a reference event is not needed. It
is typically understood as the task of grouping objects based
on the principle of maximizing the intra-class similarity and
minimizing the inter-class similarity. However, there is a
rich diversity in specific definitions of clustering and many
different techniques exist [
The clusters can be formed using distance values between other events. Thus, events that belong to the same cluster can be considered to be correlated as they occur around the same time and place.
Text documents Contextual Information (e.g., GeoNames)
Vocabularies
Extraction
Mapping & Normalization
Event Correlation &
Resolution Raw event
data
Processing pipeline
After the events have been extracted from the text document using the approach as outline in Section 2, the events are fed into the correlation pipeline. This pipeline is implemented using the Apache Spark3 platform. However, it can be easily ported to other platforms like Apache Flink4 or even Google’s new DataFlow SDK5 if they provide a Scalabased API. We chose Spark over other MapReduce based approaches, e.g., Pig, because it provides a very efficient data structure called resilient distributed datasets (RDD). RDDs are immutable, in-memory partitioned collections that can be distributed among the cluster nodes. With the help of such a data structure, the performance of the computations is significantly faster than in MapReduce programs that materialize their intermediate results to disk. Furthermore, Spark allows to implement iterative models that are needed for our computations as well as for programs following the MapReduce paradigm.
dominates
SkylineOp
EventSkyline RawEventData
PrepareEvents
EventData
GeoDB distance reference event
CalcDistance EventDistanceData time, location k, weights TopKOp EventList
EventCluster
distance-func
ClusteringOp
The Spark operators represent transformations on these RDD. Fig. 3 gives an overview of the correlation pipeline, where the tasks of the operators is described below: PrepareEvents: This operator transforms a set of raw (textual) event data into a set of event records ht, qi conforming to our framework. This means that textual temporal and geographic properties are normalized into numerical values, i.e., date/time values and points or polygons for the spatial descriptions such as names of cities or locations. 3http://spark.apache.org 4http://flink.apache.org 5https://cloud.google.com/dataflow/
CalcDistance: This implements a transformation operator for calculating the geographic and temporal distance dist of each event of an RDD to a given reference event.
TopKOp: This operator computes the k nearest neighbors as a top-k list of events from an input RDD produced by CalcDistance. Parameters to this operator are k as well as the weights for the geographic (wg) and temporal (wt) distance.
SkylineOp: This operator computes the skyline of event
records from an RDD produced by CalcDistance. Our
implementation adopts the grid-based approach using
bitsets described in [
ClusteringOp: Finding groups of correlated events is
realized by the ClusteringOp operator implementing a
parallel variant of DBSCAN [
TOWARDS AN INTERACTIVE EXPLO
RATION OF EVENT CORRELATIONS
We will use the above processing pipeline to build an event repository that makes the extracted event data publicly available as Open Data. As an underlying data structure we are going to use the Linked Data principle, which allows for a flexible schema for different types of events and also makes the information contained in the event itself machine readable. Furthermore, one can easily add links between events that have been identified to be correlated and thus make these correlations also available for querying and processing. Adding links to other datasets like YAGO2 or DBpedia will enrich our event repository with even more useful and broader information that can be used for data analysis and exploration.
The event repository will be free to download and will also be made queryable via web services. Via an API users can run Spark programs (using operators introduced in Sect. 3) or SPARQL queries.
Next to the event repository we plan to develop a data exploration platform that will allow users to interactively analyze the data. Different from traditional business intelligence frameworks that provide only a predefined set of tools for reporting and visualization, our planned platform allows very different interaction paradigms. We integrate the idea of notebooks that was inspired by Mathematica’s interactive documents and IPython’s (and Jupyter’s) notebooks.
With the help of such notebooks users can create their own programs that fit their needs and run them in a managed cluster environment without the need to set up any hardware or other software before. The idea of web-based notebooks allows users to organize text, scripts, and plots on a single webpage so that all information for data analytics can be kept in one place.
For our data exploration tool we chose the Apache Zeppelin6, because it already has support for Spark programs and also provides the possibility to visualize script results.
Content in the format of CSV, HTML, or images can
directly be visualized as tables, bar charts, line graphs, and
scatter plots. A notebook in Zeppelin is organized in
paragraphs where each of them can contain and execute a script
of a different (supported) language. On execution, the script
content of a paragraph is sent to the server, which will
forward it to the appropriate interpreter. The interpreter is
chosen by a magic keyword given by the user at the
beginning of the script, e.g. %spark. When the execution has
finished, the interpreter will return the results to the server,
which in turn will publish them on the website. Figure 4
shows a screenshot of a notebook in Zeppelin that executed
a Pig [
Zeppelin currently supports shell scripts and Spark programs written in Scala or Python out of the box and can 6https://zeppelin.incubator.apache.org also make use of Spark modules like SparkSQL and Spark Streaming. Although the Spark support lets users create efficient data analytics programs, it may be hard for a nonprogrammer to create such programs.
We argue that a declarative approach will be easier to use
for users that are not familiar with the Spark API and the
concepts of their RDDs. For this reason, we integrate a new
interpreter that allows to run Pig scripts. Since our event
repository uses Linked Data, we do not use the conventional
Pig interpreter, but our extended Pig version that allows to
use SPARQL-like features, such as BGP, in Pig scripts [
To do so, we enhanced Pig’s FILTER operator. This allows
the user to easily define queries on the Linked Data sets with
a more powerful language than SPARQL. Though, the triple
structure of the Linked Data concept is not very well suited
for a tuple-based execution environment as it requires a lot
of (self-)joins to reconstruct all details of an entity from the
triples. To solve this issue, in [
We also showed that this format can lead to significant performance gains.
However, since Pig programs are compiled into MapReduce programs, the execution of these programs will take longer than for Spark programs. Thus, to combine the advantages of both approaches, in our ongoing work we use the Pig Latin language and compile it into Spark programs.
This will allow users to write intuitive data flow scripts without the need to know a specific API and characteristics of the underlying platform and to get very efficient programs that will execute faster than MapReduce programs.
For our event correlation framework, we employ concepts developed in different areas of information extraction, event similarity especially for spatio-temporal similarity, as well as skylines and clustering algorithms for distributed environments.
To extract the spatial and temporal information from
textual data, we use concepts that were described, e.g., in [
Our correlation operators mainly focus on Skylines and
clustering. Among the numerous techniques that build on
the concept of skyline queries [
To compute skylines for large datasets, new algorithms
have been proposed that allow the computation in
MapReduce environments. Here, an important challenge is to
partition the data in a way, that the partitioning itself is efficient
and data is distributed to all nodes equally to ensure that
all nodes get approx. the same workload to avoid one node
having to do all the work while the others are idle. In [
For clustering, density based algorithms like DBSCAN [
In this paper we presented our approach for an event correlation framework based on Apache Spark. The framework provides operators for importing data as well as for clustering, skylines and k nearest neighbor queries. We chose Apache Zeppelin for our exploration tool to allow an incremental creation of scripts and an immediate visualization of results.
Acknowledgements This work was funded by the German Research Foundation (DFG) under grant no. SA782/22.
REFERENCES Cornelius A. Ludmann
Universität Oldenburg
Escherweg 2 26121 Oldenburg, Germany cornelius.ludmann@unioldenburg.de
Marco Grawunder Universität Oldenburg
Escherweg 2 26121 Oldenburg, Germany marco.grawunder@unioldenburg.de
H.-Jürgen Appelrath
Universität Oldenburg
Escherweg 2 26121 Oldenburg, Germany appelrath@unioldenburg.de ZUSAMMENFASSUNG In dieser Arbeit wird eine flexible, erweiterbare und doma¨nenunbha¨ngige Integration von Online-RecSys-Funktionen in ein Datenstrommanagementsystem (DSMS) vorgestellt. Dazu werden neue logische Operatoren eingefu¨hrt, mit der Nutzer eines DSMS auf einer abstrakten Ebene RecSys-Funktionen nutzen ko¨nnen. Des Weiteren wird eine beispielhafte Realisierung durch physische Operatoren vorgestellt, wie sie aus den logischen Operatoren durch Transformationsregeln erzeugt werden kann. Durch dieses Konzept ko¨nnen Benutzer ein RecSys mit Hilfe einer Anfragesprache auf die doma¨nenspezifischen Bedu¨rfnisse anpassen und mit anderen Funktionen eines DSMS kombinieren. Des Weiteren bringt ein DSMS einige Eigenschaften (z. B. Anfrageplanoptimierung, Fragmentierung, Scheduling etc.) mit, von denen ein Online-RecSys profitieren kann. Die Flexibilita¨t eines DSMS ermo¨glicht den Vergleich und die Evaluation verschiedener RecSys-Algorithmen durch den Benutzer.
Keywords recommender system, collaborative filtering, data stream management system, stream processing
EINLEITUNG
Recommender-Systeme (RecSys) haben das Ziel, das Interesse eines Benutzers an einem bestimmten Objekt zu scha¨tzen, um dem Benutzer aus einer großen Menge an Objekten die subjektiv interessantesten Objekte zu empfehlen.
Eine ga¨ngige Methode ist das modellbasierte, kollaborative Filtern (CF), bei dem aufgrund von bekannten Objektbewertungen verschiedener Benutzer (z. B. Produktbewertungen) ein Modell angelernt wird, mit dem gescha¨tzt werden kann, wie ein Benutzer unbekannte Objekte bewerten wu¨rde. Durch die Entwicklung von Online-Algorithmen fu¨r das CF ko¨nnen neue Bewertungen von Benutzern in die Modelle integriert werden, ohne dass das Modell von Grund auf neu gelernt werden muss. Das ermo¨glicht eine neue Betrachtung des RecSys-Problems: Wa¨hrend bisherige Methoden das RecSys-Problem als periodisches Anlernen eines Modells basierend auf einen statischen und endlichen Datensatz betrachten, kann durch Online-Algorithmen das Problem als Verarbeitung von Bewertungs-Ereignissen eines kontinuierlichen und potenziell unendlichen Datenstroms betrachtet werden. Das hat den Vorteil, dass durch die sofortige Integration neuer Bewertungsinformationen nicht nur das grundsa¨tzliche Interesse, sondern auch das aktuelle Interesse des Benutzers beru¨cksichtigt werden kann.
Zur Konzeption eines datenstrombasierten RecSys schlagen wir vor, auf ein anwendungsunabha¨ngiges und generisches Datenstrommanagementsystem (DSMS) aufzubauen. Die Eingabedaten werden als kontinuierlich auftretende, zeitannotierte Ereignisse eines potenziell unendlichen Datenstroms betrachtet. Das DSMS berechnet mit Hilfe von Datenstrom-Operatoren und Anfragepla¨nen kontinuierlich ein RecSys-Modell. Dieser Ansatz hat folgende Vorteile:
(1) Die Modellierung der Daten als Datenstro¨me kommt dem realen Einsatz eines RecSys na¨her als die Verwendung von statischen Datensa¨tzen.
(2) Ein DSMS bringt als Grundlage fu¨r ein RecSys bereits Konzepte und Operatoren zur effizienten Verarbeitung von Datenstro¨men mit temporal koha¨renten Ereignissen mit.
(3) In einem DSMS kann ein RecSys in logische Teile zerlegt werden, welche jeweils durch einen Operator repra¨sentiert werden. Das ermo¨glicht eine flexible und auf die konkrete Anwendung angepasste Komposition von RecSys-Operatoren mit Standardoperatoren, z. B. fu¨r die Datenvor- bzw. -nachbearbeitung, Kontextmodellierung etc.
(4) Eine Aufgabe, zum Beispiel das Modelllernen, kann durch austauschbare Operatoren mit gleicher Semantik aber unterschiedlicher Implementierung realisiert werden. Das ermo¨glicht den Vergleich sowie den bedarfsgerechten Einsatz von verschiedenen Lernalgorithmen.
Ziel der Arbeit ist die Einfu¨hrung eines generischen Konzepts zur Integration von RecSys-Funktionen in ein DSMS.
Dazu fu¨hren wir im folgenden Abschnitt zuna¨chst die Grundlagen ein und stellen in Abschnitt 3 verwandte Arbeiten vor. Danach beschreiben wir die logischen Operatoren fu¨r die Umsetzung eines RecSys (Abschnitt 4) und stellen eine Transformation in physische Operatoren vor (Abschnitt 5).
In Abschnitt 6 diskutieren wir anschließend einige Entscheidungen unseres Konzepts und stellen Alternativen vor. Zum Schluss pra¨sentieren wir in Abschnitt 7 unsere prototypische Implementierung in ein Open-Source-DSMS und zeigen die Machbarkeit durch eine Evaluation, bevor wir mit einer Zusammenfassung und einem Ausblick die Arbeit beenden.
GRUNDLAGEN
Ein RecSys hat die Aufgabe einem aktiven Benutzer u0 ∈ U eine Menge an Objekten aus I (Menge aller Objekte) zu empfehlen, fu¨r die dieser sich interessiert (Empfehlungsmenge). Dazu scha¨tzt das RecSys fu¨r jedes zur Empfehlung infrage kommende Objekt eine Bewertung rˆ ∈ R, welche das Interesse des Benutzers an dem Objekt quantifiziert. Die Menge der infrage kommenden Objekte wird als Menge der Empfehlungskandidaten bezeichnet. Die Empfehlungsmenge wird durch die K Objekte der Empfehlungskandidaten gebildet, die die ho¨chsten Bewertungen haben (Top-K-Menge).
Um die Bewertung eines Objekts fu¨r einen Benutzer bestimmen zu ko¨nnen, ermittelt das RecSys (z. B. mit der MatrixFaktorisierung) eine Anna¨herung fˆR an eine wahre aber unbekannte Bewertungsfunktion fR : U × I → R.
Seit den 1970er/1980er Jahren sind relationale Datenbankmanagementsysteme (DBMS) die bedeutendste Technik, Daten dauerhaft zu speichern. Ein DBMS abstrahiert von der Komplexita¨t der Datenspeicherung und sorgt fu¨r eine effiziente Verarbeitung von komplexen Anfragen, um Daten zu speichern, zu lesen, zu aktualisieren und zu lo¨schen. DBMS sind allerdings nicht mit dem Ziel entwickelt worden, kontinuierlich erzeugte Daten zu verarbeiten. Diese Lu¨cke schließen DSMS, die auf die fortlaufende Verarbeitung von Datenstro¨men ausgelegt sind.
Wa¨hrend ein DBMS wahlfreien Zugriff auf gespeicherte Daten hat, erha¨lt ein DSMS die Daten von einem kontinuierlichen Datenstrom (potenziell unendliche Sequenz von Datenstromelementen). Die Datenstromelemente werden von einer aktiven Quelle erzeugt und an das DSMS u¨bertragen.
Ein DSMS hat keine Kontrolle u¨ber die Reihenfolge, in der
die Datenstromelemente von der Quelle gesendet werden –
weder innerhalb eines Datenstroms, noch zwischen
verschiedenen Datenstro¨men. Sobald ein Element verarbeitet ist,
wird es verworfen oder archiviert. Das DSMS kann nicht
erneut auf bereits verarbeitete Elemente zugreifen, es sei denn,
sie werden explizit im Arbeitsspeicher gehalten (one-pass
paradigma). Dies kann allerdings nur fu¨r einen begrenzten Teil
der Datenstromelemente geschehen, da der Speicher im
Gegensatz zum Datenstrom in der Gro¨ße begrenzt ist [
Die Verarbeitung der Daten in einem DBMS erfolgt
u¨blicherweise mit Hilfe von Einmal-Anfragen. Diese werden
einmalig auf aktuellem Datenbestand ausgefu¨hrt und der
anfragende DBMS-Benutzer erha¨lt einmalig eine Antwort. Bei
der Verarbeitung von kontinuierlichen Datenstro¨men stellt
der Benutzer eine kontinuierliche Anfrage. Diese wird
einmalig dem DSMS u¨bergeben und produziert kontinuierlich
Ergebnisse [
Eine Anfrage wird von einem DSMS in einen
Anfrageplan u¨bersetzt. Dieser besteht aus Operatoren, die durch
Warteschlangen miteinander verbunden sind. Ein
Anfrageplan kann als gerichteter Graph interpretiert werden,
dessen Knoten die Operatoren und Kanten die Warteschlangen
darstellen. Die Ausfu¨hrung der Operatoren koordiniert ein
Scheduler [
VERWANDTE ARBEITEN
Verschiedene Vero¨ffentlichungen u¨ber inkrementelle oder
online Algorithmen fu¨r CF (z. B. [
Einige Vero¨ffentlichungen nutzen Frameworks zur
Implementierung eines RecSys, die bei der Entwicklung von
datenstrombasierten Systemen unterstu¨tzen. Zum Beispiel setzt
Ali et al. [
Mit StreamRec stellen Chandramouli et al. [
LOGISCHE OPERATORSICHT
Betrachtet man die Ein- und Ausgabedaten eines RecSys, so kann man diese als folgende Datenstro¨me auffassen: Erstens u¨bertra¨gt die Benutzeranwendung BenutzerObjekt-Bewertungs-Tripel (u, i, r) fu¨r jede Bewertung, die ein Benutzer vornimmt. Zweitens werden von einem Benutzer u Empfehlungen angefordert (z. B. dann, wenn ein Benutzer die Empfehlungsseite der Benutzeranwendung o¨ffnet; im folgenden Empfehlungsanforderungen – engl. Request for Recommendations, RfR – genannt). Drittens sendet das RecSys eine Empfehlungsmenge zuru¨ck an die Benutzeranwendung. Des Weiteren ko¨nnen die Eingabedaten
Learning
Requests for Recommendations Learning Data Window Recommending Recomm. Candidates Recommend.
Candidates
Abbildung 1: Logische Sicht auf die Operatoren eines DSMS-basierten RecSys um ein Benutzerfeedback erga¨nzt werden. Im folgenden erwarten wir das Benutzerfeedback in der selben Form wie neue Bewertungen (u-i-r-Tripel). Mo¨chte man das RecSys kontinuierlich evaluieren, so erha¨lt man einen zusa¨tzlichen Ausgabedatenstrom mit Fehlerwerten, der den Modellfehler angibt.
Zwischen den Ein- und Ausgabedatenstro¨men verarbeiten Datenstromoperatoren einer oder mehrerer Anfragen die Daten. Um ein RecSys mit Hilfe eines DSMS zu realisieren, muss mit Hilfe einer Anfrage aus den Eingabedatenstro¨men (u-i-r-Tripel und Empfehlungsanforderungen) als Antwort ein Datenstrom an Empfehlungsmengen erzeugt werden, der fu¨r jede Empfehlungsanforderung eine aktuelle und personalisierte Liste an Empfehlungen entha¨lt.
Die Anfrage fu¨r ein RecSys haben wir in logische Operatoren zerlegt, die jeweils einen Teil der RecSys-Funktionalita¨t u¨bernehmen. Diese Operatoren bilden eine Abstraktionsebene, sodass der DSMS-Benutzer diese in der Anfrage nutzen kann, ohne die genaue Umsetzung durch physische Operatoren kennen zu mu¨ssen. Wo dies mo¨glich ist, werden diese Operatoren bei der Transformation zu physischen Operatoren durch vorhandene Operatoren ersetzt.
Abbildung 1 zeigt eine U¨ bersicht u¨ber die logischen Operatoren und wie diese in einer Beispielanfrage zusammenha¨ngen. Auf der linken Seite sehen wir die Eingabedatenstro¨me und auf der rechten Seite die Ausgabedatenstro¨me.
Die dazwischenliegenden Operatoren ko¨nnen in drei Kategorien eingeteilt werden: Operatoren zum Lernen des RecSysModells (mittig), zum Empfehlen von Objekten (unten) und zum Evaluieren (oben).
Die Anfrage besteht aus folgenden logischen Operatoren: Window: Ein zeitbasiertes Fenster (umgesetzt durch einen WINDOW-Operator) ermo¨glicht, die Gu¨ltigkeit der Bewertungsdaten zu beschra¨nken. Das kann sinnvoll sein, um ein Modell anzulernen, welches sich auf die neuesten Daten beschra¨nkt und a¨ltere Daten verwirft (z. B. um Concept Drifts zu beru¨cksichtigen). Zusa¨tzlich beschra¨nkt es die Menge der Bewertungsdaten, die im Speicher gehalten werden mu¨ssen.
Sollen alle Daten fu¨r immer behalten werden, so kann dieser Operator entfernt werden.
Train RecSys Model: Dieser Operator lernt aus den Bewertungsdaten ein Modell an. Wenn neue Daten hinzugefu¨gt werden gibt es ein aktualisiertes Modell aus. Das Modell ist fu¨r eine bestimmte Zeitspanne gu¨ltig, sodass zu jedem Zeitpunkt genau ein Modell fu¨r die Vorhersage der Bewertung zusta¨ndig ist.
Recomm. Candidates: Fu¨r jede Empfehlungsanforderung bestimmt dieser Operator die Empfehlungskandidaten. Diese sind in der Regel alle Objekte, die von dem anfordernden Benutzer noch nicht bewertet wurden.
Predict Rating: Dieser Operator wird sowohl fu¨r die Bestimmung der Empfehlungsmenge als auch fu¨r die Evaluation genutzt. Er scha¨tzt die Bewertung des Benutzers fu¨r jeden Empfehlungskandidaten bzw. fu¨r jedes Testtupel ab.
Mit diesem Operator wird sichergestellt, dass genau das Model genutzt wird, welches zum gleichen Zeitpunkt wie die Empfehlungsanforderung bzw. das Testtupel gu¨ltig ist. Das stellt eine deterministische Verarbeitung der Daten sicher, was insbesondere fu¨r die Evaluation von Vorteil ist.
Recommend: Aus den bewerteten Empfehlungskandidaten werden die Objekte ausgewa¨hlt, die dem Benutzer empfohlen werden sollen. Das sind in der Regel die K Objekte mit den ho¨chsten, gescha¨tzten Bewertungen (Top-K-Menge). Eine weitere Mo¨glichkeit besteht darin, nur Elemente mit einer minimalen Bewertung zu beru¨cksichtigen.
Extract Test Data: Um das RecSys zu evaluieren, gibt dieser Operator neben den Lerndaten auch Testdaten aus. Eine mo¨gliche Implementierung filtert 10 % der Bewertungsdaten als Testdaten aus und leitet die restlichen Daten als Lerndaten an den Modelllerner weiter.
Test Prediction: Dieser Operator implementiert eine Evaluationsmetrik, z. B. Root Mean Square Error (RMSE). Dabei vergleicht er die wahren Bewertungen aus den Testdaten mit den gescha¨tzten Bewertungen zu den Testdaten oder die wahre Position in einem Ranking mit der Position aufgrund der gescha¨tzten Bewertungen. Der daraus resultierende Modellfehler wird zu einem gleitenden Durchschnittswert oder einem gesamten Durchschnittswert aggregiert. 5. PHYSISCHE OPERATORSICHT
Die logischen Operatoren werden durch Transformationsregeln in physische Operatoren u¨berfu¨hrt. Abbildung 2 zeigt ein Beispiel fu¨r einen physischen Anfrageplan, der aus einer Anfrage generiert wird, der die logischen Operatoren nutzt.
Die linke Spalte entha¨lt die Operatoren fu¨r die Evaluation (entspricht dem oberen Teil von Abbildung 1), die mittlere Spalte die Operatoren fu¨r das Lernen des Modells (mittlerer Teil von Abbildung 1) und die rechte Spalte die Operatoren fu¨r die Berechnung der Empfehlungsmenge (unterer Teil von Abbildung 1). Dabei sind die Operatoren, die zu einem logischen Operator aus Abbildung 1 geho¨ren, durch ein gestricheltes Ka¨stchen zusammengefasst. Wo es mo¨glich ist,
Test Prediction
Predict Rating Extract
Test Data Bind
Input Stream send RMSE map aggregate time window map predict rating cross product ITTT access ratings str.
Abbildung 2: Physischer Operatorplan
werden die logischen Operatoren durch vorhandene
physische Basisoperatoren (Operatoren mit durchgezogener
Linie) implementiert. Neue, speziell fu¨r die RecSys-Funktion
implementierte physische Operatoren (mit gestrichelter,
dicker Linie) sind:
– ITTT: Impl. der Evaluationsmethode ITTT [
Im folgenden wird die Verarbeitung der Datenstromelemente anhand des physischen Anfrageplans aus Abbildung 2 na¨her erla¨utert. Dazu werden die drei Teilgraphen Lernen des Modells, Bestimmung der Empfehlungsmenge und Berechnung des Modellfehlers in jeweils einem Abschnitt behandelt.
Von Bewertungsdaten zu Modellen Der ACCESS-Operator ist fu¨r die Anbindung von Datenstro¨men zusta¨ndig. Mit ihm werden das Transportprotokoll sowie das Datenformat festgelegt. Aus jedem ankommenden Datenstromelement wird ein Tupel in der Form (u, i, r) erzeugt, das die Benutzer-ID u, die Objekt-ID i sowie die Bewertung r des Benutzers u fu¨r das Objekt i entha¨lt. Außerdem wird der Gu¨ltigkeitszeitraum des Datenstromelements festgelegt. Gibt die Datenquelle einen Zeitstempel mit, so kann dieser als Startzeitpunkt des Gu¨ltigkeitsintervalls genutzt werden. Andernfalls wird der aktuelle Zeitpunkt als Startzeitpunkt genutzt. Bewertungsdaten sind initial unendlich gu¨ltig und erhalten somit als Endzeitpunkt des Gu¨ltigkeitsintervals den Wert ∞.
Der Operator ITTT implementiert die Evaluationsmethode Interleaved Test-Than-Train (ITTT), die aus den Bewertungsdaten Tupel als Lern- und Testdaten erzeugt. Als Lerndaten werden alle Bewertungsdaten ohne A¨ nderung weitergeleitet. Auf die Erzeugung der Testdaten wird spa¨ter bei der Beschreibung der Evaluation na¨her eingegangen.
Ein TIME-WINDOW-Operator beschra¨nkt die Gu¨ltigkeit der Lerndaten. So kann zum Beispiel festgelegt werden, dass die Lerndaten in dem BRISMF-Operator nur fu¨r 30 Tage lang
send recomm set top K select predict rating cross product recomm cand cross product time window access RfR stream Recommend Predict Rating Recomm.
Candidates
beru¨cksichtigt werden sollen. Der BRISMF-Operator
implementiert den Lernalgorithmus BRISMF [
Von Empf.-Anforderungen zu Empf.-Mengen Zu jeder Empfehlungsanforderung eines Benutzers u soll eine Menge an Empfehlungen ermittelt werden. Dazu bindet ein ACCESS-Operator den Eingabedatenstrom mit den Anforderungen und ein TIME-WINDOW-Operator setzt deren Gu¨ltigkeit. Das Gu¨ltigkeitsintervall wird so gesetzt, dass diese nur zum Zeitpunkt der Empfehlungsanforderung gu¨ltig sind und nach Verarbeitung direkt verworfen werden.
Zur Bestimmung der Empfehlungskandidaten werden der Datenstrom der Empfehlungsanforderungen und der Datenstrom der Modelle, der von dem BRISMF-Operator erzeugt wird, mit einem Kreuzprodukt-Operator zusammengefu¨hrt.
Dieser Operator beru¨cksichtigt die Gu¨ltigkeitsintervalle, sodass nur Datenstromelemente mit u¨berlappenden Intervallen zusammengefu¨hrt werden. Da der BRISMF-Operator Modelle in der Art erzeugt, so dass zu jedem Zeitpunkt genau ein Modell gu¨ltig ist, wird jeder Empfehlungsanforderung genau ein Modell zugeordnet. Der RECOMM-CAND-Operator bekommt anschließend die Anforderungen mit den passenden Modellen und erzeugt einen Datenstrom, der fu¨r jedes in dem Modell nicht bewertete Objekt i des Benutzers u ein Tupel (u, i) mit dem anfordernden Benutzer und dem nicht bewerteten Objekt entha¨lt.
Im na¨chsten Schritt wird fu¨r jeden Empfehlungskandidaten eine Bewertung gescha¨tzt. Dazu wird mit einem Kreuzprodukt-Operator zu jedem Empfehlungskandidaten das temporal passende Modell zugeordnet. Der PREDICT-RATINGOperator nutzt nun das jeweilige Modell zu Bestimmung der Scha¨tzung und gibt zu jedem Empfehlungskandidaten ein Tupel (u, i, rˆ) aus, welches den Benutzer u, den Empfehlungskandidaten i und die gescha¨tzte Bewertung rˆ entha¨lt.
Anschließend werden aus den bewerteten Empfehlungskandidaten die Objekte fu¨r die Empfehlungsmenge ausgewa¨hlt. In der Beispielanfrage in Abbildung 2 werden dazu mit einem SELECT-Operator die Kandidaten entfernt, deren gescha¨tzte Bewertung kleiner als ein bestimmter Schwellwert ist (z. B. 3,5). Von den verbleibenden Kandidaten werden mit dem TOP-K-Operator die K Objekte mit den gro¨ßten Bewertungen ausgewa¨hlt (z. B. K = 8) und an den Ausgabedatenstrom u¨bergeben.
Von Bewertungsdaten zu Modellfehlerwerten Fu¨r die Evaluation werden vom ITTT-Operator Testdaten erzeugt. Ein Testdatum (u, i, r) wird als ein Empfehlungskandidat i fu¨r einen anfragenden Benutzer u betrachtet und vom PREDICT-RATING-Operator um eine gescha¨tzte Bewertung rˆ erweitert. Die PREDICT-RATING-Operatoren fu¨r die Berechnung der Empfehlungen und fu¨r die Evaluation haben die gleiche Implementierung: Sie erhalten vom vorgelagerten CROSS-PRODUCT-Operator ein Tupel, welches einen Benutzer u, ein Objekt i, ein Modell fˆ und evtl. beliebig weitere Attribute besitzt. Die Ausgabe ist in beiden Fa¨llen ein Tupel mit dem Benutzer u, dem Objekt i, der gescha¨tzten Bewertung rˆ durch Anwendung des Modells rˆ = fˆ(u, i) und alle weiteren Attribute des Eingabetupels (ohne das Modell fˆ, welches nach der Berechnung von rˆ im folgenden Verlauf nicht mehr beno¨tigt wird). Fu¨r die Evaluation za¨hlt zu den weiteren Attributen des Eingabetupels insbesondere die wahre Bewertung r, die auch im Ausgabetupel enthalten ist. Somit gibt der PREDICT-RATING-Operator fu¨r die Evaluation ein Tupel (u, i, r, rˆ) aus.
Im nachfolgenden Verlauf wird nun ein Fehlerwert berechnet. In unserer Beispielanfrage wird dazu ein gleitender RMSE berechnet. Dazu berechnet zuerst ein MAP-Operator den quadratischen Fehler se = (r − rˆ)2 der Scha¨tzung. Anschließend wird mit einem TIME-WINDOW-Operator die gleitende Zeitspanne festgelegt, u¨ber die der Fehlerwert aggregiert werden soll (z. B. die letzten 24 Stunden). Der nachfolgende AGGREGATE-Operator berechnet das arithmetische Mittel der quadratischen Fehler, die sich in einem Aggregationsfenster befinden (z. B. alle Werte der letzten 24 Stunden).
Abschließend berechnet der letzte MAP-Operator die Quadratwurzel aus dem aggregierten Fehlerwert, welches dem RMSE u¨ber das Aggregationsfenster entspricht. Diese Werte werden an den Ausgabedatenstrom u¨bergeben.
Fu¨r die Evaluation ist es wichtig, dass zum Testen des Modells das zu testende Datum nicht im Modell enthalten ist.
Eine einfache Mo¨glichkeit dies sicherzustellen ist die
Trennung von Test- und Lerndaten. Dies kann durch einen
ROUTE-Operator realisiert werden, der zufa¨llig 10 % der Daten
als Testdaten und die restlichen Daten als Lerndaten
weiterleitet. Der hier vorgestellte Operator implementiert
stattdessen die Evaluationsmethode Interleaved Test-Than-Train
[
Um sicherzustellen, dass zur Scha¨tzung der Bewertung eines jeden Testdatums ein Modell genutzt wird, dass nicht das Testdatum, aber ansonsten so viele Lerndaten wie mo¨glich entha¨lt, wird das Gu¨ltigkeitsintervall des Testdatums vom ITTT-Operator angepasst. Ist ein Lerndatum im Gu¨ltigkeitsintervall [ts, te) mit dem Startzeitpunkt ts und dem Endzeitpunkt te gu¨ltig, so wird die Gu¨ltigkeit des Testdatums so gesetzt, dass dieses ungu¨ltig wird, gerade bevor das ¨aquivalente Lerndatum gu¨ltig wird. Bei einem Lerndatum von einem Gu¨ltigkeitsintervall [45, ∞) erha¨lt das Testdatum das Gu¨ltigkeitsintervall [44, 45). Es ist genau wie die Empfehlungsanforderungen nur ein Zeitpunkt gu¨ltig: zum Zeitpunkt t1 = 44 ist es gu¨ltig und zum Zeitpunkt t2 = 45 bereits ungu¨ltig (wegen des halboffenes Intervalls). Wie bereits weiter oben gefordert, soll ein Modell genau alle Lerndaten enthalten, welche im Gu¨ltigkeitsintervall des Modells ebenfalls gu¨ltig sind. Der BRISMF-Operator erzeugt also ein Modell mit dem Lerndatum, welches ab t2 = 45 gu¨ltig ist und das vorherige Modell wird somit zum Zeitpunkt t2 = 45 ungu¨ltig. Der CROSS-PRODUCT-Operator vor dem PREDICT-RATING-Operator der Evaluation fu¨hrt nun unter Beru¨cksichtigung der Gu¨ltigkeitsintervalle Testdatum und MoWindow Recomm. Candidates
Recommend Abbildung 3: Gegenu¨berstellung: Drei Operatoren vs. ein Operator fu¨r die Bewertungssch¨atzung dell zusammen. Da sich die Gu¨ltigkeitsintervalle des Testdatums und des Modells, welches das zum Testdatum a¨quivalente Lerndatum entha¨lt, nicht u¨berschneiden, werden diese nicht zusammengefu¨hrt. Dafu¨r u¨berschneidet sich das vorherige Modell mit dem Testdatum und wird somit, wie bei der ITTT-Methode gefordert, zur Bewertungsscha¨tzung genutzt.
DISKUSSION Die Aufteilung der Bewertungsschätzung in drei Operatoren Bei dem hier vorgestellten Konzept haben wir das RecSysProblem der Scha¨tzung von Bewertungen im Wesentlichen auf drei Operatoren aufgeteilt: TRAIN RECSYS MODEL, RECOMM. CANDIDATES und PREDICT RATING. Das hat den Nachteil, das eine Kopie des gelerntes Modells vom TRAINRECSYS-MODEL-Operator an die anderen beiden Operatoren als Datenstromelement u¨bertragen werden muss. Das fu¨hrt, insbesondere bei großen Modellen, zu einem zusa¨tzlichen Aufwand. Eine Alternative wa¨re, alle drei Operatoren zu einem Operator zu vereinen (vgl. Abbildung 3). Dies ha¨tte folgende Nachteile:
Durch die Aufteilung in drei Operatoren kann jeder Operator fu¨r sich verschiedene Implementierungen (physische Operatoren) haben. Zum Beispiel kann man sich ein RecSys fu¨r Filme vorstellen, bei dem der Benutzer angeben kann, dass er z. B. eine Komo¨die und keinen Actionfilm sehen mo¨chte. Dies wu¨rde die Empfehlungsanforderung um eine Genre-Angabe erweitern. Ein fu¨r diese Anwendung angepasster RECOMM-CAND-Operator kann von vornherein als Empfehlungskandidaten nur die Objekte beru¨cksichtigen, die unter die Kategorie Komo¨die fallen. Alternativ ko¨nnte man zwischen RECOMM CAND und PREDICT RATING einen Selektionsoperator einfu¨gen, der alle Kandidaten, die nicht unter Komo¨die fallen, herausfiltert. Die anderen Operatoren bleiben davon unberu¨hrt. Die Aufteilung sorgt somit fu¨r klare Zusta¨ndigkeiten der Operatoren und ermo¨glicht eine einfachere Erweiterung der Anfrage.
Der TRAIN-RECSYS-MODEL-Operator bestimmt die Gu¨ltigkeit eines Modells, so dass zu jeden Zeitpunkt genau ein Modell gu¨ltig ist. Durch die Zusammenfu¨hrung von Modell und Empfehlungsanforderung durch einen Kreuzprodukt-Operator findet eine deterministische, temporale Zuordnung statt. Diese Zuordnung basiert alleine auf den Gu¨ltigkeitsintervallen und ist nicht davon abha¨ngig, ob aufgrund der Steuerung des Schedulers oder anderer Latenzen zuerst das Lerndatum oder die Empfehlungsanforderung den Operator erreicht. Das Zeitmodell des DSMS sorgt dafu¨r, dass genau das zusta¨ndige Modell reproduzierbar fu¨r die Vorhersage genutzt wird. Des Weiteren kann der TRAIN-RECSYSMODEL-Operator das Modell fu¨r den Gu¨ltigkeitszeitraum anpassen, z. B. um temporale Verzerrungen aufgrund von Concept Drift zu beru¨cksichtigen.
Die Ausgabe der Empfehlungskandidaten Der RECOMM-CAND-Operator gibt fu¨r jeden Empfehlungskandidaten einer Empfehlungsanforderung ein Datenstromelement aus. Eine Alternative wa¨re die Ausgabe eines Datenstromelements je Empfehlungsanforderung, welches eine Liste von Empfehlungskandidaten entha¨lt. Das ha¨tte den Nachteil, dass der PREDICT-RATING-Operator fu¨r die Bestimmung der Empfehlungen und fu¨r die Evaluation andere Eingabedaten verarbeiten ko¨nnen mu¨sste: im ersten Fall eine Liste von Benutzer-Objekt-Paaren, im zweiten Fall einzelne Benutzer-Objekt-Paare.
Der RECOMM-CAND-Operator gibt nur die Empfehlungskandidaten ohne Modell aus. Dieser Operator ko¨nnte auch das Modell den Empfehlungskandidaten beifu¨gen, so ko¨nnte man auf den CROSS-PRODUCT-Operator vor PREDICT RATING verzichten. Das hier vorgestellte Konzept hat den Vorteil, dass BRISMF an RECOMM CAND und PREDICT RATING unterschiedliche Modelle u¨bergeben kann. Wenn zum Beispiel aus dem Modell fu¨r die Scha¨tzung der Bewertung gar nicht hervorgeht, welche Objekte ein Benutzer nicht bewertet hat (und somit zu den Empfehlungskandidaten geho¨rt), so kann an RECOMM CAND ein Modell u¨bergeben werden, dass die Zuordnung von Benutzer zu unbewerteten Objekten ermo¨glicht, dafu¨r aber keine Scha¨tzung der Bewertung vornehmen kann (z. B. ein einfaches Mapping u 7→ unbewertete Objekte). 7. IMPLEMENTIERUNG UND EVALUATI
ON
Das vorgestellte Konzept haben wir mit dem
erweiterbaren Open-Source-DSMS Odysseus1 [
Die Machbarkeit des Konzepts und die korrekte
Implementierung konnten wir durch den Vergleich der
Evaluationsergebnisse mit MOA und dem MovieLens-Datensatz
nachweisen. Dazu haben wir als BRISMF-Operator die
MOAImplementierung des BRISMF-Algorithmus’ [
Da MOA die Gu¨ltigkeit von Lerndaten nicht begrenzt, haben wir den WINDOW-Operator entfernt und die RMSE u¨ber den gesamten Datensatz berechnet (kein gleitender RMSE). Den MovieLens-Datensatz haben wir, wie MOA, zeilenweise eingelesen um einen Datenstrom zu simulieren und haben nach jedem getesteten Tupel den RMSE ausgegeben.
Die RMSE-Werte stimmen dabei mit denen von MOA exakt u¨berein. Das zeigt, dass die temporale Zuordnung von Lernund Testdaten mit den Modellen sowie die Umsetzung der Evaluationsmethode korrekt funktionieren.
In dieser Arbeit haben wir ein Konzept fu¨r die Umsetzung eines modellbasierten und kollaborativen RecSys mit einem auf Operatoren basierten DSMS vorgestellt. Dazu haben wir logische Operatoren definiert, die fu¨r Teilaufgaben eines RecSys zusta¨ndig sind. Zu einem Beispiel eines logischen Anfrageplans fu¨r ein RecSys haben wir eine beispielhafte Umsetzung durch einen physischen Anfrageplan gezeigt und die Umsetzung und deren Alternativen diskutiert.
Unser Konzept haben wir durch eine Implementierung in dem DSMS Odysseus und dem Vergleich der Evaluationsergebnisse mit MOA validiert.
Um die Praxistauglichkeit nachzuweisen, soll das Konzept
in Zukunft unter realen Bedingungen, z. B. in einem Living
Lab wie Newsreel2 [
REFERENCES 1http://odysseus.informatik.uni-oldenburg.de/ 2http://www.clef-newsreel.org/
Das PArADISE-Projekt Big-Data-Analysen für die Entwicklung von Assistenzsystemen
(Extended Abstract)∗
Andreas Heuer Lehrstuhl DBIS, Institut für Informatik
Universität Rostock 18051 Rostock, Deutschland heuer@informatik.uni-rostock.de ZUSAMMENFASSUNG Bei der Erforschung und systematischen Entwicklung von Assistenzsystemen fallen eine große Menge von Sensordaten an, aus denen Situationen, Handlungen und Intentionen der vom Assistenzsystem unterstu¨tzten Personen abgescha¨tzt (modelliert) werden mu¨ssen. Neben Privatheitsaspekten, die bereits wa¨hrend der Phase der Modellbildung beru¨cksichtigt werden mu¨ssen, sind die Performance des Analysesystems sowie die Provenance (Ru¨ckverfolgbarkeit von Modellierungsentscheidungen) und die Preservation (die langfristige Aufbewahrung der Forschungsdaten) Ziele unserer Projekte in diesem Bereich. Speziell sollen im Projekt PArADISE die Privatheitsaspekte und die Performance des Systems beru¨cksichtigt werden. In einem studentischen Projekt wurde innerhalb einer neuen experimentellen Lehrveranstaltung im reformierten Bachelor- und MasterStudiengang Informatik an der Universita¨t Rostock eine Systemplattform fu¨r eigene Entwicklungen geschaffen, die auf Basis von klassischen zeilenorientierten Datenbanksystemen, aber auch spaltenorientierten und hauptspeicheroptimierten Systemen die Analyse der Sensordaten vornimmt und fu¨r eine effiziente, parallelisierte Verarbeitung vorbereitet. Ziel dieses Beitrages ist es, die Ergebnisse dieser studentischen Projektgruppe vorzustellen, insbesondere die Erfahrungen mit den gewa¨hlten Plattformen PostgreSQL, DB2 BLU, MonetDB sowie R (als Analysesystem) zu pra¨sentieren.
Ein Forschungsschwerpunkt am Institut fu¨r Informatik der Universita¨t Rostock ist die Erforschung und systematische Entwicklung von Assistenzsystemen, etwa im DFGGraduiertenkolleg MuSAMA. Da in Assistenzsystemen unterstu¨tzte Personen durch eine Vielzahl von Sensoren beobachtet werden, mu¨ssen bei der datengetriebenen Modellie∗Eine Langfassung dieses Artikels ist erha¨ltlich als [HM15] unter http://www.ls-dbis.de/digbib/dbis-tr-cs-04-15.pdf
Holger Meyer Lehrstuhl DBIS, Institut für Informatik
Universität Rostock 18051 Rostock, Deutschland hme@informatik.uni-rostock.de rung von Situationen, Handlungen und Intentionen der Personen aus großen Datenmengen mittels Machine-LearningMethoden entsprechende Modelle abgeleitet werden: ein Performance-Problem bei einer Big-Data-Analytics-Fragestellung.
Da Personen beobachtet werden, mu¨ssen auch Privatheitsaspekte bereits wa¨hrend der Phase der Modellbildung beru¨cksichtigt werden, um diese bei der konkreten Konstruktion des Assistenzsystems automatisch in den Systementwurf zu integrieren. Somit gibt es fu¨r die Datenbankforscher unter anderem die Teilprobleme der performanten Berechnung der Modelle als auch der Wahrung der Privatheitsanspru¨che des Nutzers, die zu lo¨sen sind und die in einer langfristigen Projektgruppe des Datenbanklehrstuhls angegangen werden: im Projekt PArADISE (Privacy AwaRe Assistive Distributed Information System Environment) werden effiiziente Techniken zur Auswertung von großen Mengen von Sensordaten entwickelt, die definierte Privatheitsanspru¨che der spa¨teren Nutzer per Systemkonstruktion erfu¨llen.
Wa¨hrend wir in [Heu15] ausfu¨hrlicher auf die Verknu¨pfung der Aspekte Privatheit (Projekt PArADISE) und Provenance (Projekt METIS) eingegangen sind, werden wir uns in diesem Beitrag auf die beiden Schwerpunkte des PArADISEProjektes konzentrieren, das ist neben der Privatheit die Performance durch Parallelita¨t und Verteilung.
Um seine Assistenzaufgaben zu erfu¨llen, besteht ein Assistenzsystem u¨blicherweise aus fu¨nf Schichten [Heu15]. In der untersten Schicht werden sta¨ndig viele Daten (etwa von Sensoren) erzeugt, in der obersten Schicht wird aber nur im Bedarfsfall (also eher selten) ein akustischer oder optischer Hinweis, also eine geringe Datenmenge, ausgegeben.
In der mittleren der fu¨nf Schichten mu¨ssen Sensordaten gefiltert, erfasst, ausgewertet, verdichtet und teilweise langfristig verwaltet werden. Aufgrund der extrem großen Datenmenge (Big Data) muss die Verarbeitung verteilt erfolgen: teilweise eine Filterung und Verdichtung schon im Sensor, im na¨chsterreichbaren Prozessor (etwa im Fernseher oder im Smart Meter in der Wohnung) und im Notfall u¨ber das Internet in der Cloud. Neben Daten des Assistenzsystems mu¨ssen auch fremde Daten etwa u¨ber das Internet beru¨cksichtigt werden, beispielsweise Wartungspla¨ne beim Auto oder die elektronische Patientenakte beim Patienten. Allgemein ko¨nnen hier natu¨rlich auch die Daten sozialer Netz
Die Forschungsschwerpunkte der Rostocker Datenbankgruppe lassen sich in diesem Zusammenhang mit vier P charakterisieren, die im Folgenden na¨her erla¨utert werden sollen.
Forschung und Entwicklung: In der Forschungs- und Entwicklungsphase eines Assistenzsystems ist das vorrangige Ziel, eine effiziente Modellbildung auf großen Datenmengen zu unterstu¨tzen. Dabei sollte mo¨glichst automatisch eine Selektion der Daten (Filterung wichtiger Sensordaten nach einfachen Merkmalen) und eine Projektion der Daten (die Beschra¨nkung der großen Sensormenge auf wenige, besonders aussagekra¨ftige Sensoren) vorgenommen werden. Die no¨tige Effizienz in dieser Phase fu¨hrt auf unser Forschungsthema P3: Performance. Da wa¨hrend der Entwicklung bei fehlerhafter Erkennung von Handlungen und Intentionen die dafu¨r zusta¨ndigen Versuchsdaten ermittelt werden mu¨ssen, fu¨hrt die Ru¨ckverfolgbarkeit der Analyseprozesse in der Entwicklung auf unsere Forschungsthemen P2: Provenance Management und P4: Preservation (Langfristarchivierung von Forschungsdaten).
Einsatz: In der Einsatzphase eines Assistenzsystems sind dagegen Privatheitsanspru¨che vorherrschend, die im Gesamtsystem durch stufenweise Datensparsamkeit erreicht werden ko¨nnen (unser Forschungsthema P1: Privatheit). Eine weitere Verdichtung (auch Reduktion und Aggregation) der live ausgewerteten Daten unterstu¨tzen aber nicht nur die Privatheit, sondern auch die Performance.
Die vier P behandeln wir in drei langfristigen Forschungsprojekten (METIS, PArADISE, HyDRA), in diesem Beitrag konzentrieren wir uns auf den Aspekt P3 (Performance) des PArADISE-Projektes.
Die in MuSAMA bisher verwendete Lo¨sung mit Plain R wies dabei die schlechteste Effizienz auf, auch wenn man den Prozess des initialen Ladens der Daten in den Hauptspeicher herausrechnet. Unter den Varianten mit einer Analyse in reinem SQL-92 (Regression per Hand mit Aggregatfunktionen umgesetzt) war die MonetDB-Lo¨sung etwas besser als die DB2-Variante, PostgreSQL fiel sta¨rker ab. Die SQL:2003Lo¨sung konnte in MonetDB mangels vorhandener OLAPund Rekursions-Fa¨higkeiten nicht umgesetzt werden, DB2 war hier wiederum deutlich besser als PostgreSQL. Weiterhin bemerkt man im Vergleich von SQL-92 und SQL:2003, dass der Optimierer von DB2 als auch PostgreSQL die direkte Verwendung der OLAP-Funktionen belohnt. Die beste Performance aller Varianten erreichte jedoch MonetDB mit integrierten R-Funktionen. 5.
DANKSAGUNGEN
Wir danken der studentischen Projektgruppe PArADISE im Wintersemester 2014/2015, die im Rahmen einer experimentellen Projekt-Lehrveranstaltung die Basis fu¨r die softwaretechnische Umsetzung des PArADISE-Projektes gelegt hat: Pia Wilsdorf, Felix Ko¨ppl, Stefan Lu¨dtke, Steffen Sachse, Jan Svacina, Dennis Weu.