=Paper=
{{Paper
|id=Vol-1366/gvd2015
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1366/gvd2015.pdf
|volume=Vol-1366
}}
==None==
Proceedings of the 27th GI-Workshop Grundlagen von Datenbanken Gommern, Deutschland, 26.-29. Mai 2015 c 2015 for the individual papers by the papers’ authors. Copying permitted for pri- vate and academic purposes. Re-publication of material from this volume requires permission by the copyright owners. Herausgeber: Gunter Saake, David Broneske, Sebastian Dorok, Andreas Meister Otto-von-Guericke-Universität Magdeburg Fakultät für Informatik Institut für Technische und Betriebliche Informationssysteme Universitätsplatz 2 DE-39106 Magdeburg E-Mail: vorname.nachname@ovgu.de 2 Vorwort Liebe Teilnehmerinnen und Teilnehmer, bereits zum 27. Mal fand vom 26.05.2015 bis 29.05.2015 der Workshop Grundla- ” gen von Datenbanken“ (GvDB) statt. Nachdem der Workshop im letzten Jahr in Südtirol zu Gast war, kehrte er in diesem Jahr wieder nach Deutschland zurück, genauer nach Gommern in Sachsen-Anhalt, wo er bereits das zweite Mal nach 2001 stattfand. Der viertägige Workshop wurde vom GI-Arbeitskreis Grundlagen von Informati- onssystemen im Fachbereich Datenbanken und Informationssysteme (DBIS) ver- anstaltet und hat die theoretischen, konzeptionellen und methodischen Grundla- gen von Datenbanken und Informationssystemen zum Thema, ist aber auch für neue Anwendungsgebiete mit Datenmanagementbezug offen. Organisiert wurde der Workshop durch die Arbeitsgruppe Datenbanken und Software Engineering der Otto-von-Guericke-Universität Magdeburg. Der Workshop soll die Kommunikation zwischen Wissenschaftlern/-innen im deutsch- sprachigen Raum fördern, die sich grundlagenorientiert mit Datenbanken und In- formationssystemen beschäftigen. Er ist insbesondere als Forum für Nachwuchs- wissenschaftler/-innen gedacht, die ihre aktuellen Arbeiten in einem größeren Fo- rum vorstellen wollen. Der Workshop fand im idyllischen Hotel am See“, dem ” Robinien-Hof in Gommern, statt. Das Hotel befindet sich gleich gegenüber der letzten Wanderdüne in Sachsen-Anhalt. Durch die ruhige Lage am Kulk“ bietet ” der Tagungsort einen idealen Rahmen für offene und inspirierende Diskussionen zu Datenbanken und Informationssystemen. Aus den Einsendungen wurden 15 Arbeiten nach einem Review-Prozess ausgewählt und vorgestellt. Die Themenvielfalt erstreckte sich dabei von Crowdsourcing für Entity Resolution über klassischere Themen wie Datenkompression bis hinzu Da- tenstromanagementsystemen. Die Beiträge wurden durch drei Keynotes ergänzt. Kai-Uwe Sattler, Professor an der TU Ilmenau, ging in seinem Vortrag Optimie- rung von Datenflussprogrammen - ein Fall klassischer Anfrageoptimierung? auf die Optimierung von Ausführungsplänen zur Datenstromverarbeitung ein. Erhard Rahm, Professor an der Uni Leipzig, präsentierte in seinem Vortrag Scalable Graph Analytics with GRADOOP die Potentiale von MapReduce-Frameworks wie Hadoop fü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 Datenbank- systeme und gab einen Ausblick auf die Potentiale, die sich aus dem konsequentem HW/SW-Datenbank-CoDesign ergeben. Das ausgewogene Workshop-Programm wurde von zwei Ausflügen abgerundet. Zunächst konnten die Teilnehmer bei einer Führung durch den Gommeraner Ge- steinsgarten eine der größten und umfassendsten Sammlungen von Natursteinen aus Deutschland und Europa erkunden und bei der anschließenden Waldwande- 3 rung die Ruhe der Natur genießen. Aber auch für die kulinarische Unterhaltung war gesorgt. So stand neben einem Grillbüffett zur Auffrischung der Kräfte nach den Wanderungen der Besuch von Deutschlands einziger Gasthausbrauerei auf ei- ner über 1000 Jahre alten Burg an, natürlich inklusive Verkostung. An dieser Stelle danke ich allen Beteiligten für die erfolgreiche Durchführung des GvDB 2015: den Autoren, dem Programmkomittee und den Mitarbeitern des Ta- gungsghotels. Besonderer Dank gilt allen Mitgleidern des Organisations-Komittee ohne deren Hilfe die Durchführung des GvDB 2015 nicht möglich gewesen wäre: David Broneske, Sebastian Dorok, Andreas Meister, Siba Mohammad und Veit Köppen. Vielen Dank! Gunter Saake Magdeburg am 26.05.2015 4 Komittee Organisationskomittee David Broneske Sebastian Dorok Andreas Meister Siba Mohammad Veit Köppen Gunter Saake Programm-Komittee Stefan Brass Universität Halle Erik Buchmann Universität Karlsruhe Stefan Conrad Universität Düsseldorf Rainer Gemulla Universität Mannheim Friederike Klan Friedrich-Schiller Universität Jena Holger Meyer Universität Rostock Klaus Meyer-Wegener Universität Erlangen Gunter Saake Universität Magdeburg Kai-Uwe Sattler TU Ilmenau Eike Schallehn Universität Magdeburg Ingo Schmitt TU Cottbus Holger Schwarz Universität Stuttgart Günther Specht Universität Innsbruck Jens Teubner TU Dortmund 5 Inhaltsverzeichnis Key Notes: 9 Optimierung von Datenflussprogrammen - ein Fall klassischer An- frageoptimierung? Kai-Uwe Sattler 9 Scalable graph analytics with GRADOOP Erhard Rahm 10 Next-Generation Hardware for Data Management – more a Bles- sing than a Curse? Wolfgang Lehner 11 Workshopbeiträge: 12 Ontologie-basierte Fragmentierungs- und Replikationsverfahren für verteilte Datenbanksysteme Lena Wiese 12 Automated Silhouette Extraction for Mountain Recognition Daniel Braun, Michael Singhof 18 Slicing in Assistenzsystemen - Wie trotz Anonymisierung von Da- ten wertvolle Analyseergebnisse gewonnen werden können Hannes Grunert, Andreas Heuer 24 Towards Visualization Recommendation – A Semi- Automated Domain-Specific Learning Approach Pawandeep Kaur, Michael Owonibi, Birgitta Koenig-Ries 30 Transparente Datenbankunterstützung für Analysen auf Big Data Dennis Marten, Andreas Heuer 36 Ansätze zur Erkennung von Kommunikationsmodi in Online-Diskussionen Matthias Liebeck 42 6 Ausführungspläne und -planoperatoren relationaler Datenbank- managementsysteme Christoph Koch, Katharina Büchse 48 Modularisierung leichtgewichtiger Kompressionsalgorithmen Juliana Hildebrandt, Dirk Habich, Patrick Damme, Wolfgang Lehner 54 Annotation und Management heterogener medizinischer Studien- formulare Victor Christen 60 Merkle Hash Tree based Techniques for Data Integrity of Out- sourced Data Muhammad Saqib Niaz, Gunter Saake 66 Crowdsourcing Entity Resolution: a Short Overview and Open Issues Xiao Chen 72 Toward GPU Accelerated Data Stream Processing Marcus Pinnecke, David Broneske, Gunter Saake 78 Where- und Why-Provenance für syntaktisch reiches SQL durch Kombination von Programmanalysetechniken Tobias Müller 84 Large-scale Analysis of Event Data Stefan Hagedorn, Kai-Uwe Sattler, Michael Gertz 90 Flexible Online-Recommender-Systeme durch die Integration in ein Datenstrommanagementsystem Cornelius A. Ludmann, Marco Grawunder, Hans-Jürgen Appelrath 96 Extended Abstracts: 102 Das PArADISE-Projekt - Big-Data-Analysen für die Entwicklung von Assistenzsystemen Andreas Heuer, Holger Meyer 102 7 8 Optimierung von Datenflussprogrammen - ein Fall klassischer Anfrageoptimierung? [Abstract] Kai-Uwe Sattler Technische Universität Ilmenau Helmholtzplatz 5 Ilmenau, Germany kus@tu-ilmenau.de ABSTRACT About the Author Datenflusssprachen haben in den vergangenen Jahren speziell Kai-Uwe Sattler ist Professor für Datenbanken und Infor- im Kontext von Big-Data-Plattformen - etwa in Form von mationssysteme an der TU Ilmenau. Zu seinen Arbeits- Pig oder Jaql - große Aufmerksamkeit gewonnen. Sie bieten gebieten zählen Datenbanksystemaspekte, Datenbankinte- sich jedoch auch für die Verarbeitung und Analyse dynamis- gration sowie Anfrageverarbeitung für, heterogenen, massiv cher Daten bzw. Datenströme an. Ähnlich wie bei klas- verteilte und dynamische Datenbestände. Er ist Koautor sischen Anfragesprachen besteht bei Datenflusssprachen die mehrerer Lehrbücher, u.a. zu verschiedenen Datenbank- Aufgabe, aus (mehr oder weniger) deklarativen Spezifika- konzepten wie Grundlagen, Implementierungstechniken, Data tionen effiziente Ausführungspläne abzuleiten. Der Vortrag Warehousing und Cloud Data Management sowie zu Algo- behandelt die Herausforderungen derartiger Optimierungen, rithmen und Datenstrukturen. geht auf Besonderheiten im Vergleich zur klassischen An- frageoptimierung ein und diskutiert anhand von Beispielen aus den Bereichen Datenstromverarbeitung und MapReduce konkrete Problemstellungen. 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. Copyright is held by the author/owner(s). 9 Scalable graph analytics with GRADOOP [Abstract] Erhard Rahm University of Leipzig Augustusplatz 10 Leipzig, Germany rahm@informatik.uni-leipzig.de ABSTRACT About the Author Many Big Data applications in business and science require Erhard Rahm is full professor for databases at the com- the management and analysis of huge amounts of graph puter science institute of the University of Leipzig. His data. Previous approaches for graph analytics such as graph current research focusses on Big Data and data integra- databases and parallel graph processing systems (e.g., Pregel) tion. He has authored several books and more than 200 either lack sufficient scalability or flexibility and expressive- peer-reviewed journal and conference publications. His re- ness. We are therefore developing a new end-to-end ap- search on data integration and schema matching has been proach for graph data management and analysis at the Big awarded several times, in particular with the renowned 10- Data center of excellence ScaDS Dresden/Leipzig. The sys- year best-paper award of the conference series VLDB (Very tem is called Gradoop (Graph analytics on Hadoop). Gradoop Large Databases) and the Influential Paper Award of the is designed around the so-called Extended Property Graph conference series ICDE (Int. conf. on Data Engineering). Data Model (EPGM) which supports semantically rich, schema- Prof. Rahm is one of the two scientific coordinators of the free graph data within many distinct graphs. A set of high- new German center of excellence on Big Data ScaDS (com- level operators is provided for analyzing both single graphs petence center for SCAlable Data services and Solutions) and sets of graphs. The operators are usable within a domain- Dresden/Leipzig that started its operation in Oct. 2014. specific language to define and run data integration work- flows (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 anal- ysis. 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. Copyright is held by the author/owner(s). 10 Next-Generation Hardware for Data Management - more a Blessing than a Curse? [Abstract] Wolfgang Lehner Technische Universität Dresden Noethnitzer Str. 46 Dresden, Germany wolfgang.lehner@tu-dresden.de ABSTRACT About the Author Recent hardware developments have touched almost all com- Wolfgang Lehner is full professor and head of the database ponents of a computing system: the existence of many and technology group at the TU Dresden, Germany. His re- potentially heterogeneous cores, the availability of volatile search is dedicated to database system architecture specifi- and non-volatile main memories with an ever growing ca- cally looking at crosscutting aspects from algorithms down pacity, and the emergence of economically affordable, high- to hardware-related aspects in main-memory centric set- speed/low-latency interconnects are only a few prominent tings. He is part of TU Dresden’s excellence cluster with examples. Every single development as well as their combi- research topics in energy-aware scheduling, resilient data nation has a massive impact on the design of modern com- structures on unreliable hardware, and orchestration of wildly puting systems. However, it is still an open question, if, how, heterogeneous systems; he is also a principal investigator of and at which level of detail, a database system has to explic- Germany’s national ”Competence Center for Scalable Data itly be aware of those developments and exploit them using Services and Solutions” (ScaDS); Wolfgang also maintains specifically designed algorithms and data structures. Within a close research relationship with the SAP HANA develop- the talk I will try to give an answer to this question and ar- ment team. He serves the community in many PCs, is an gue for a clear roadmap of HW/SW-DB-CoDesign especially elected member of the VLDB Endowment, serves on the re- providing an outlook to upcoming technologies and discus- view board of the German Research Foundation (DFG), and sion of their non-functional properties like energy-efficiency is an appointed member of the Academy of Europe. and resilience behavior. 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. Copyright is held by the author/owner(s). 11 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 ABSTRACT Verfahren zur Ontologie-basierten Fragmentierung und zur Das Auffinden von semantisch verwandten Daten in großen intelligenten Replikation vor, womit folgende Eigenschaften Datenmengen ist aufwändig und daher zur Laufzeit einer sichergestellt werden: Anfrage nur schwierig durchzuführen. In diesem Artikel stel- • durch die Fragmentierung wird ein Verfahren der fle- len wir ein Verfahren vor, dass Datentabellen anhand einer xiblen Anfragebeantwortung unterstützt, die dem An- Ontologie in semantisch zusammenhängende Cluster auf- frager auch relevante verwandte Werte als Antworten teilt. Dadurch ergibt sich eine Ontologie-basierte Fragmen- zurückliefert. tierung der Tabelle, die eine flexible Anfragebeantwortung unterstützt. Bei mehreren derartigen Fragmentierungen über- • durch die Fragmentierung wird eine Lastverteilung auf schneiden sich Fragmente; dies wird für ein intelligentes Re- mehrere Server möglich. plikationsverfahren ausgenutzt, um die Anzahl der Replika- server zu reduzieren. • durch die Fragmentierung wird die Anzahl der kontak- tierten Server pro Anfrage reduziert und damit eine bessere Parallelisierung möglich. Keywords Verteiltes Datenbanksystem, Replikation, Ontologie, Frag- • durch die intelligente Replikation wird die Anzahl der mentierung, flexible Anfragebeantwortung benötigten Replikaserver reduziert. 1. EINLEITUNG 1.1 Übersicht Abschnitt 2 beschreibt den Hintergrund zu flexibler Anfra- Die Verwaltung von großen Datenmengen in Datenbanken gebeantwortung, Fragmentierung und Datenverteilung. Ab- erfordert die Verteilung der Daten auf mehrere Datenbank- schnitt 3 stellt die Ontologie-basierte Fragmentierung inklu- Server. Dies bietet mehrere Vorteile: sive Clustering, Fragmentverteilung und Anfragebeantwor- • Lastverteilung: Datenbankanfragen können auf mehre- tung vor. Abschnitt 4 beschreibt darauf aufbauend ein Repli- re Server verteilt und damit parallelisiert werden. kationsverfahren mit überlappenden Fragmenten. Ein Wie- derherstellungsverfahren anhand des Replikationsverfahrens • Verfügbarkeit: Durch die Lastverteilung erhöht sich die wird in Abschnitt 5 dargestellt. Es folgt ein Verfahren für Verfügbarkeit des Gesamtsystems, da einzelne Anfra- abgeleitete Fragmentierungen in Abschnitt 6 und abschlie- gen seltener verzögert werden müssen. ßend eine Zusammenfassung in Abschnitt 7. Ein geeignetes Verfahren zur Fragmentierung (auch: Par- titionierung oder Sharding) der Daten in Teilmengen ist 2. HINTERGRUND daher notwendig. Die gängigen Fragmentierungsverfahren Wir stellen hier kurz Vorarbeiten zu flexibler Anfragebe- (Round-Robin, Hash-basiert, Intervall-basiert) ignorieren je- antwortung, Fragmentierung und Datenverteilung vor. doch semantische Zusammenhänge der Daten. Aus Gründen der Ausfallsicherheit ist zusätzlich noch die 2.1 Flexible Anfragebeantwortung Replikation von Daten (also die Spiegelung desselben Da- Flexible Anfragebeantwortung ist ein intelligentes Verfah- tensatzes auf mehreren Servern) erforderlich. Dies gilt insbe- ren, um Datenbanknutzern Antworten zu liefern, die zwar sondere für Hauptspeicherdatenbanken, die nicht über einen nicht exakt der Anfrage entsprechen, die jedoch dennoch in- Hintergrundspeicher verfügen. In dieser Arbeit stellen wir teressante Informationen für den Benutzer darstellen. Dabei gibt es syntaktische und semantische Ansätze. Zum einen gibt es syntaktische Änderungen, die Teile der Anfrage verändern. Dazu zählen [Mic83]: • Dropping Conditions: Selektionsbedingungen werden aus der Originalanfrage entfernt. • Goal Replacement: einige Bedingungen der Originalan- 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. frage werden anhand einer Ableitungsregel durch an- Copyright is held by the author/owner(s). dere Bedingungen ersetzt. 12 • Anti-Instantiation: Ein Term (eine Variable mit meh- • Redundanzfreiheit: Um Duplizieren von Daten zu ver- reren Vorkommen oder eine Konstante) wird durch ei- meiden, sollen einzelne Datensätze nur einem Frag- ne neue Variable ersetzt. ment zugewiesen werden. Bei vertikaler Fragmentie- Diese Operatoren können auch kombiniert werden [IW11]. rung ist jede Spalte nur in einem Fragment enthalten Diese syntaktischen Änderungen können aber zu weit ge- (abgesehen vom Tupel-Identifikator). Bei horizontaler hen und zu viele Antworten produzieren – insbesondere beim Fragmentierung ist jede Zeile in nur einem Fragment Ersetzen von Konstanten durch neue Variablen in der Anti- enthalten. Instantiation. Daher ist es wichtig, dass die Werte, die der In anderen, nicht-relationalen Datenmodellen (Schlüssel- neuen Variable zugewiesen werden können, beschränkt wer- Wert-Speicher, Dokumentdatenbanken oder Spaltenfamili- den: es sollen nur semantisch äquivalente oder semantisch endatenbanken) gibt es Fragmentierung meist über den Zu- nah verwandte Werte zugelassen werden. Diese semantische griffsschlüssel entweder Hash-basiert [KLL+ 97] oder basie- Ähnlichkeit kann anhand einer Ontologie oder Taxonomie rend auf Intervallen. Jedoch unterstützt keines dieser Ver- von Werten bestimmt werden. Für Einzelrechner wurden fahren die flexible Anfragebeantwortung; im Gegensatz dazu bereits vor einiger Zeit Verfahren vorgeschlagen – ohne je- hat das im Folgenden vorgestellte Fragmentierungsverfahren doch verteilte Datenspeicherung mit einzubeziehen. CoBase den Vorteil, dass eine relaxierte Bedingung aus nur einem [CYC+ 96] und [SHL07] zum Beispiel benutzten sogenannte Fragment beantwortet werden kann. Abstraktionshierarchien, um einzelne Werte zu generalisie- ren. Auch für XML-Anfragen wurden Verfahren entwickelt 2.3 Datenverteilung [HTGC10]. In einem verteilten Datenbanksystem müssen Daten auf Ein grundlegendes Problem ist dabei jedoch, dass die Be- die verschiedenen Server verteilt werden. Wichtige Eigen- stimmung von ähnlichen Werten zur Laufzeit (während der schaften sind Anfragebeantwortung) viel zu ineffizient ist [BDIW14]. Die- ses Problem wird durch das hier vorgestellte Fragmentie- • Datenlokalität: Daten, auf die innerhalb einer Anfra- rungsverfahren gelöst. ge oder Transaktion zugegriffen wird, sollten möglichst auf einem Server sein. Dadurch verringert sich die An- 2.2 Fragmentierung zahl der kontaktierten Server und somit auch die Dauer Im relationalen Modell gibt es die Theorie der Datenfrag- der Anfragebeantwortung. Außerdem kann so die Par- mentierung, die sich aufgrund des strikten Tabellenformats allelisierung der Anfragebeantwortung verbessert wer- aufteilen lässt in horizontale und vertikale Fragmentierung den, da die anderen Server neue Anfragen annehmen (siehe zum Beispiel [ÖV11]): können. • Vertikale Fragmentierung: Fragmente entsprechen Teil- • Lastverteilung: Daten sollen so verteilt werden, dass mengen von Attributen (also Tabellenspalten). Die Ein- parallele Anfragen möglichst auch von verschiedenen träge in den Fragmenten, die zur selben Tabellenzeile Servern beantwortet werden können, damit nicht ein- gehören, müssen durch einen Tuple-Identifikator ver- zelne Server unter Lastspitzen ( hot spots“) leiden. bunden werden. Vertikale Fragmentierung entspricht ” einer Projektion auf der Tabelle. Einige Arbeiten befassen sich mit horizontaler Fragmentie- rung und Verteilung; jedoch unterstützen diese nur exakte • Horizontale Fragmentierung: Fragmente sind Teilmen- Anfragebeantwortung und keine flexible Anfragebeantwor- gen von Tupeln (also Tabellenzeilen). Eine horizontale tung wie in unserem Ansatz. Die meisten Ansätze gehen von Fragmentierung entspricht einer Selektion auf der Ta- einer vorgebenen Menge von Anfragen oder Transaktionen belle. aus ( workload“) und optimieren die Lokalität der Daten, die ” innerhalb der Anfrage beziehungsweise Transaktion benötigt • Abgeleitete Fragmentierung: Eine bereits bestehende werden. Dies ist für die Anwendung der flexiblen Anfrage- primäre“ horizontale Fragmenation of einer Tabelle ” beantwortung jedoch nicht anwendbar, da hier auch Werte induziert eine horizontale Fragmentierung einer wei- zurückgegeben werden, die nicht explizit in einer Anfrage teren Tabelle; dazu wird der Semi-JOIN auf beiden auftauchen. Tabellen ausgeführt. [CZJM10] stellen Tupel als Knoten eines Graphen dar. Drei grundlegende Eigenschaften sind wichtig für Fragmen- Für eine vorgegebene Menge von Transaktionen fügen sie tierungen: Hyperkanten in den Graph ein, wenn die Tupel in dersel- ben Transaktion benötigt werden. Mit einem Graphpartitio- • Vollständigkeit: Keine Daten dürfen während der Frag- nierungsalgorithmus wird dann eine Datenfragmentierung mentierung verloren gehen. Bei vertikaler Fragmentie- ermittelt, die Zahl der zerschnittenen Kanten minimiert. rung ist jede Spalte in einem Fragment enthalten; bei In einer zweiten Phase benutzen die Autoren einen Klas- horizontaler Fragmentierung ist jede Zeile in einem sifizierer aus dem Maschinellen Lernen, der eine Intervall- Fragment enthalten. basierte Fragmentierung herleitet. Experimentell vergleichen • Rekonstruierbarkeit: Daten aus den Fragmenten kön- sie dann das Graph-basierten mit Intervall-basierten und nen wieder zur Originaltabelle zusammengefügt wer- Hash-basierten Verfahren. Im Gegensatz zu unserem Ansatz den. Bei vertikaler Fragmentierung wird der JOIN- wenden sie jedoch volle Replikation an, bei der alle Server Operator benutzt (basierend auf einem zusätzlich ein- alle Daten vorhalten; dies ist wenig realistisch in großen ver- gefügten Tupel-Identifikator), um die Spalten zu ver- teilten Systemen. Zudem vergleichen sie drei verschiedene binden. Bei horizontaler Fragmentierung wird der Ver- Arten von Lookup-Tabellen, die Tupel-Identifikatoren für je- einigungsoperator zum Zusammenführen der Fragmen- des Fragment abspeichern: Indexe, Bitarrays und Bloomfil- te verwendet. ter. Bei der Analyse unseres Systems stellt sich jedoch her- 13 aus, dass Lookup-Tabellen ineffizienter sind als das Einfüh- Fragment 1: cough, ren einer zusätzlichen Spalte mit der Cluster-ID in anderen bronchitis, Table column: Fragmentierungen. query asthma cough, rewrite & cluster & brokenLeg, Auch [QKD13] modellieren das Fragmentierungsproblem fragment user redirect bronchitis, durch Minimierung zerschnittener Hyperkanten in einem Gra- brokenArm, Fragment 2: phen. Zur Verbesserung der Effizienz komprimieren sie den brokenLeg, asthma Graphen und erhalten so Gruppen von Tupeln. Die Autoren brokenArm kritisieren dabei auch den tupelweisen Ansatz von [CZJM10] als unpraktisch für große Tupelmengen. Die Autoren verglei- Figure 1: Fragmentation and query rewriting chen ihren Ansatz mit zufälligen und tupelweisen Fragmen- tierungen und betrachten auch Änderungen der vorgegebe- Diseases nen Transaktionen. [TCJM12] gehen von drei existierenden Fragmentierungen Disease, Injuries Wound aus: Hash-basiert, Intervall-basiert und Lookup-Tabellen auf Respiratory Tract einzelnen Zugriffsschlüsseln. Sie vergleichen diese drei be- Disorder, Diseases, Respiratory züglich Kommunikationskosten und Anfragendurchsatz. Zur Fracture Respiration Bronchial Tract Infections Effiziensteigerung analysieren sie diverse Komprimierungs- Fracture Tibial techniken. Sie beschreiben Hash-basierte Fragmentierung als Cough Asthma Influenza of ulna Fractures zu ineffizient. Die Autoren beschreiben jedoch nicht, wie die Fragmentierungen für die Lookup-Tabellen berechnet wer- den; im Gegensatz dazu stellen wir ein Ontologie-basiertes Figure 2: Beispieltaxonomie für Krankendaten Fragmentierungsverfahren vor. Im Gegensatz zu den meisten anderen Ansätzen gehen Ein Clustering-Verfahren benutzt diese Ähnlichkeitswerte wir nicht von einer vorgegebenen Menge von Anfragen oder um Cluster zu bestimmen (in Anlehnung an [Gon85]). Da- Transaktionen aus sondern schlagen ein allgemein anwend- zu wird in jedem Cluster ein prototypisches Element head bares Clusteringverfahren vor, dass die flexible Anfragebe- bestimmt, das das jeweilige Cluster repräsentiert. Zusätz- antwortung zum Auffinden semantisch ähnlicher Antworten lich gibt es einen Schwellenwert α und das Verfahren un- ermöglicht. Unsere Ergebnisse zeigen, dass Lookup-Tabellen terteilt Cluster solange in Teilcluster, bis für jedes Element (selbst wenn sie auf allen Servern repliziert werden) für un- innerhalb eines Clusters die Ähnlichkeit zu head mindes- seren Ansatz zu ineffizient sind, dadurch dass viele JOIN- tens α ist. Das heißt, für jedes Cluster ci und head i ∈ ci Operationen durchgeführt werden müssen. gilt für jeden anderen Wert a ∈ ci (mit a 6= head i ), dass sim(a, head i ) ≥ α. Dieses Verfahren wird in Auflistung 1 3. ONTOLOGIE-BASIERTE FRAGMENTIE- dargestellt. RUNG Unser Verfahren der Ontologie-basierten Fragmentierung Listing 1 Clustering procedure beruht darauf, dass Input: Set πA (F ) of values for attribute A, similarity thres- • zur Anti-Instantiierung ein Attribut (also eine Tabel- hold α lenspalte) ausgewählt wird. Output: A set of clusters c1 , . . . , cf 1: Let c1 = πA (F ) • ein Clusteringverfahren auf dieser Tabellenspalte aus- 2: Choose arbitrary head 1 ∈ c1 geführt wird, um die ähnlichen Werte innerhalb dieser 3: sim min = min{sim(a, head1 ) | a ∈ c1 ; a 6= head 1 } Spalte zu gruppieren. 4: i = 1 • anhand der Cluster die Tabelle zeilenweise fragmen- 5: while sim min < α do S tiert wird. 6: Choose head i+1 ∈ 1≤j≤i {b | b ∈ cj ; b 6= head j ; sim(b, headj ) = sim min } S Wie in Abbildung 1 dargestellt werden dann die Anfra- 7: ci+1 = {head i+1 } ∪ 1≤j≤i {c | c ∈ cj ; c 6= head j ; gen so weitergeleitet, dass zu einer Konstante aus der Ori- sim(c, headj ) ≤ sim(c, headi+1 )} ginalanfrage das semantisch ähnlichste Fragment ermittelt 8: i=i+1 wird und anschließend alle Werte des Fragments als rele- 9: sim min = min{sim(d, headj ) | d ∈ cj ; d 6= head j ; 1 ≤ vante Antworten zurückgeliefert werden. Daher werden zum j ≤ i} Beispiel bei einer Anfrage nach Husten auch die ähnlichen 10: end while Werte Asthma und Bronchitis gefunden. 3.1 Clustering Zum Beispiel kann eine Taxonomie wie in Abbildung 2 Zu dem zur Anti-Instantiierung ausgewählten Attribut A benutzt werden, um die Tabellenspalte aus Abbildung 1 zu in der gegebenen Tabelle F werden alle in der Tabelle vor- clustern. handenen Werte (die sogenannte aktive Domäne) ausgelesen durch Projektion πA (F ). Anhand einer gegebenen Ontologie 3.2 Fragmentierung werden Ähnlichkeitswerte sim zwischen jeweils zwei Termen Ein Clustering der aktiven Domäne von A induziert ei- a, b ∈ πA (F ) bestimmt im Wertebereich 0 (keine Ähnlich- ne horizontale Fragmentierung der Tabelle F in Fragmente keit) bis 1 (volle Ähnlichkeit). Dazu gibt es verschiedene Me- Fi ⊆ F . Jede aktive Domäne eines Fragments Fi entspricht triken, die meist auf der Berechnung von Pfaden zwischen genau den Werten in einem Cluster: ci = πA (Fi ). Die grund- den Termen in der Ontologie beruhen [Wie14, Wie13]. legenden Eigenschaften einer Fragmentierung (Vollständig- 14 keit, Rekonstruierbarkeit, Redundanzfreiheit) sollen auch bei Dabei entspricht xik einer Binärvariable die dann wahr (1) einer Clustering-basierten Fragmentierung gelten. Auch das ist, wenn Fragment/Objekt i Server/Bin k zugewiesen wird; Clustering muss vollständig sein: bei einer aktiven Domäne und yk bedeutet, dass Server/Bin k belegt ist (also nicht πA (F ) muss dann für ein Clustering C = c1 , . . . , cn gelten, leer). Gleichung (1) fordert, dass die Anzahl der belegten dass es die ganze aktive Domäne umfasst und kein Wert ver- Server minimiert wird; Gleichung (2) erzwingt, dass jedes loren geht: c1 ∪ . . . ∪ cn = πA (F ). Die Eigenschaften einer Fragment einem Server zugewiesen wird; Gleichung (3) be- Clustering-basierten Fragmentierung werden in Definition 1 deutet, dass die Kapazitätsgrenzen nicht überschritten wer- zusammengefasst. den; die letzten beiden Gleichungen stellen sicher, dass die Variablen binär sind. Definition 1 (Clustering-bas. Fragmentierung). Zusätzlich können noch die Eigenschaften der Datenloka- Für ein Attribut A einer Tabelle F (eine Menge von Tupeln lität und der Lastverteilung optimiert werden. Datenvertei- t) und ein Clustering C = {c1 , . . . cn } der aktiven Domäne lung mit einer guten Datenlokalität platziert die Fragmente πA (F ) und für head i ∈ ci gibt es eine Menge von Fragmen- zusammen auf einen Server, die häufig gemeinsam innerhalb ten {F1 , . . . , Fn } (definiert über denselben Attributen wie F ), einer Datenbanktransaktion (oder auch innerhalb einer An- so dass folgende Eigenschaften gelten: frage) benutzt werden. Lastverteilung sorgt dafür, dass alle Server ungefähr dieselbe Anzahl von Anfragen beantworten • Horizontale Fragmentierung: für jedes Fragment Fi gilt müssen. Fi ⊆ F • Clustering: für jedes Fi gibt es in Cluster ci ∈ C so 3.4 Metadaten dass ci = πA (Fi ) Für die Durchführung des Clustering, der Fragmentvertei- lung und der Anfrageumschreibung und -umleitung werden • Schwellenwert: für jedes a ∈ ci (wobei a 6= head i ) gilt ein paar Metadaten benötigt. sim(a, head i ) ≥ α Eine Tabelle root speichert einen Identifikator für jedes Cluster (Spalte ID), den Namen des Fragments (Name), den • Vollständigkeit: für jedes Tupel t in F gibt es ein Frag- Repräsentaten des Clusters (Head), die Größe des Clusters ment Fi , in dem t enthalten ist (S) sowie den Server (Host), auf dem das Fragment gespei- • Rekonstruierbarkeit: F = F1 ∪ . . . ∪ Fn chert wird. Eine Beispieltabelle sieht dann so aus: ROOT ID Name Head S Host • Redundanzfreiheit: für jedes i 6= j, Fi ∩ Fj = ∅ (oder 101 Respiratory Flu 4 S1 auch ci ∩ cj = ∅) 107 Fracture brokenArm 2 S2 Eine Tabelle similarities speichert die Ähnlichkeiten al- 3.3 Fragmentverteilung ler Werte des betrachteten Attributes zu den jeweiligen head - In verteilten Datenbanken müssen Fragmente verschie- Werten der Cluster. denen Servern zugewiesen werden. Dieses Fragmentvertei- lungsproblem kann als ein Bin-Packing-Problem dargestellt 3.5 Anfragebeantwortung werden: Für die flexible Anfragebeantwortung wird die Konstante im entsprechenden Attribut A in der Anfrage anti-instantiiert • K Server entsprechen K Bins und die entstehende Anfrage dann aus dem semantisch ähn- lichsten Fragment beantwortet. • Jedes Bin hat maximale Kapazität W Als Beispiel betrachten wir eine Anfrage nach Husten in • n Fragmente entsprechen n Objekten einer Tabelle ill mit Patienten IDs und Krankheiten: SELECT patientid, disease • Jedes Objekt/Fragment hat ein Gewicht (oder Kapizi- FROM ill WHERE disease=’cough’ tätsverbrauch) wi ≤ W Über die Tabelle similarities wird das Fragment Fi ausge- wählt, dessen head am ähnlichsten zu der anti-instantiierten • alle Objekte müssen auf möglichst wenig Bins verteilt Konstante (im Beispiel cough) ist. werden, wobei die Gewichtsgrenze W beachtet werden SELECT TOP 1 root.name muss. FROM root, similarities Dieses Bin-Packing-Problem kann auch als Problem der WHERE similarities.term=’cough’ ganzzahligen linearen Optimierung dargestellt werden: AND similarities.head = root.head ORDER BY similarities.sim DESC Der Name der Originaltabelle F wird durch den Namen K X des Fragmentes Fi ersetzt und die geänderte Anfrage an den minimize yk (1) entsprechenden Server gesendet. Dadurch werden alle Werte k=1 aus dem Fragment als relevante Antworten zurückgeliefert. K X Als Beispiel sei der Fragmentname Respiratory. Daher wird s.t. xik = 1, i = 1, . . . , n (2) die Anfrage geändert zu: k=1 SELECT patientid, disease FROM respiratory n X und and den entsprechenden Server (hier S1) weitergeleitet. wi xik ≤ W yk , k = 1, . . . , K (3) Ähnliches gilt beim Einfügen neuer Zeilen: i=1 INSERT INTO ill VALUES (349, ’asthma’) yk ∈ {0, 1} k = 1, . . . , K (4) wird umgeschrieben zu: xik ∈ {0, 1} k = 1, . . . , K, i = 1, . . . , n (5) INSERT INTO respiratory VALUES (349, ’asthma’). 15 Auch das Löschen von Werten wird so umgesetzt: (BPPC): DELETE FROM ill WHERE disease=’cough’ wird zu: K X DELETE FROM respiratory WHERE mesh=’cough’ minimize yk (6) k=1 4. INTELLIGENTE REPLIKATION K X s.t. xik = 1, i = 1, . . . , n (7) Bisherige Replikationsverfahren kopieren die vorhandenen k=1 Fragmente auf andere Server; bei einer m-fachen Replikati- n X on verteilen sich so m verschiedene Kopien jedes Fragments wi xik ≤ W yk , k = 1, . . . , K (8) auf m verschiedenen Servern. Dabei wird davon ausgegan- i=1 gen, dass die Fragmentierung redundanzfrei ist und sich die xik + xi0 k ≤ yk k = 1, . . . , K, i ∩ i0 6= ∅ (9) Fragmente daher nicht überschneiden: jedes Tupel ist in ge- nau einem Fragment enthalten. yk ∈ {0, 1} k = 1, . . . , K (10) Bei der Ontologie-basierten Fragmentierung kann es je- xik ∈ {0, 1} k = 1, . . . , K, i = 1, . . . , n (11) doch sein, dass mehrere Attribute zur Anti-Instantiierung Um diese Konflikte (überlappende Fragmente) zu identifi- ausgewählt werden. Dadurch ergeben sich mehrere Fragmen- zieren werden Fragmente aus verschiedenen Fragmentierun- tierungen derselben Tabelle. Fragmente aus unterschiedli- gen verglichen. Im Beispiel gibt es Fragmente ci mit einer chen Fragmentierungen überschneiden sich deswegen. Bei α Cluster-ID (Fragmentierung wie im obigen Beispiel über den redundanzfreien Fragmentierungen ist daher jedes Tupel in Werten der Krankheiten) und Fragmente rj mit einer Range- α verschiedenen Fragmenten enthalten. ID (Fragmentierung über den Werten der Patienten-ID): Beispielsweise kann unsere Beispieltabelle anhand eines SELECT DISTINCT clusterid, rangeid Clusterings der Krankheitsdiagnose fragmentiert werden; so FROM ci JOIN rj ON (rj .tupleid=ci .tupleid) ergeben sich zwei Fragemente: Respiratory und Fracture. Respiratory PatientID Disease für jedes Cluster-Fragment ci und jedes Range-Fragment rj . Danach wird das resultierende BPPC gelöst und die Frag- 8457 Cough mente auf entsprechend viele Server verteilt mittels: 2784 Flu ALTER TABLE ci MOVE TO ’severname’ PHYSICAL. 2784 Asthma 8765 Asthma Fracture PatientID Diagnosis 5. WIEDERHERSTELLUNG 2784 brokenLeg Passend zum Replikationsverfahren müssen im Falle ei- 1055 brokenArm nes Serverausfalls einige Fragmente wiederhergestellt wer- Zum Zweiten kann dieselbe Tabelle auch anhand der IDs den. Dazu werden der Originaltabelle Spalten für die jewei- der Patienten fragmentiert werden. ligen Cluster-Identifikatoren hinzugefügt. Anhand der IDs IDlow PatientID Diagnosis können die entsprechenden Fragmente rekonstruiert werden: 2784 Flu INSERT INTO ci SELECT * FROM rj WHERE clusterid=i 2784 brokenLeg Alternativ ist die Erstellung einer sogenannten Lookup- 2784 Asthma Tabelle [TCJM12] möglich, die zu jeder Cluster-ID die be- 1055 brokenArm teiligten Tupelidentifikatoren abspeichert. Diese benötigt je- IDhigh PatientID Diagnosis doch einen JOIN-Operator: 8765 Asthma INSERT INTO ci SELECT * FROM ill JOIN lookup 8457 Cough ON (lookup.tupleid= rj .tupleid) Dabei gilt, dass Respiratory ∩ IDlow 6= ∅, Respiratory WHERE lookup.clusterid=i ∩ IDhigh 6= ∅ und Fracture ∩ IDlow 6= ∅. Die Lookup-Tabelle hat sich daher als ineffizienter heraus- Im Sinne der Minimierung der benutzten Server sollten gestellt. nicht alle α Fragmentierungen m-fach kopiert werden, da dies zu α · m Kopien jedes Tupels führt, obwohl m Kopien 6. DATENLOKALITÄT FÜR ABGELEITE- ausreichen würden. Das bedeutet, dass das hier vorgestellte Verfahren weniger Speicherplatzbedarf hat als eine konven- TE FRAGMENTIERUNGEN tionelle Replikation aller ontologie-basierter Fragmente. Wenn auf mehrere Tabellen innerhalb einer Anfrage zu- Um eine m-fache Replikation pro Tupel zu erreichen, wer- gegriffen wird und diese Tabellen Join-Attribute gemeinsam den daher die Überschneidungen berücksichtigt. Wir gehen haben, kann durch abgeleitete Fragmentierung die Datenlo- im Folgenden (ohne Beschränkung der Allgemeinheit) davon kalität für die Anfragen erhöht werden. Zum Beispiel sei zu- aus, dass α = m – andernfalls werden einige Fragmentie- sätzlich zur Tabelle ill eine Tabelle info gegeben, die zu jeder rungen dupliziert bis die entsprechende Anzahl erreicht ist. Patienten-ID Adressangaben enthält. Eine mögliche Anfra- Damit ist also jedes Tupel in m Fragmenten enthalten. ge wäre daher, die Angaben zu Krankheiten und Adressen Das Fragmentverteilungsproblem lässt sich daher erwei- zu kombinieren: tern um die Bedingung, dass überlappende Fragmente (i ∩ SELECT a.disease, a.patientid, b.address i0 6= ∅) auf verschiedenen Server platziert werden (Gleichung FROM ill AS a,info AS b WHERE disease=’cough’ (9)). Im Beispiel kann also Fracture nicht mit IDlow auf ei- AND b.patientid= a.patientid nem Server platziert werden; jedoch können Fracture und Anhand der vorgegebenen primären Fragmentierung der IDhigh auf demselben Server liegen. Generell handelt es Tabelle ill wird dann auch die Tabelle info fragmentiert, sich dann dabei um ein Bin Packing Problem with Conflicts zum Beispiel für das Fragment Respiratory: 16 INSERT INTO inforesp Distributed caching protocols for relieving hot SELECT a.patientid, b.address spots on the world wide web. In Proceedings of FROM respiratory AS a, info AS b the twenty-ninth annual ACM symposium on WHERE b.patientid = a.patientid Theory of computing, pages 654–663. ACM, Daher kann dann im Folgenden auch die Anfrage, die An- 1997. gaben zu Krankheiten und Adressen kombiniert, entspre- [Mic83] Ryszard S. Michalski. A theory and chend umgeschrieben werden: methodology of inductive learning. Artificial SELECT a.disease, a.patientid, b.address Intelligence, 20(2):111–161, 1983. FROM respiratory AS a [ÖV11] M. Tamer Özsu and Patrick Valduriez. JOIN inforesp AS b ON (a.patientid=b.patientid) Principles of Distributed Database Systems, Third Edition. Springer, Berlin/Heidelberg, 7. ZUSAMMENFASSUNG UND AUSBLICK Germany, 2011. Flexible Anfragebeantwortung unterstützt Benutzer bei [QKD13] Abdul Quamar, K. Ashwin Kumar, and Amol der Suche nach relevanten Informationen. In unserem Ver- Deshpande. Sword: scalable workload-aware fahren wird auf eine Ontologie zurückgegriffen aufgrund de- data placement for transactional workloads. In rer semantisch ähnliche Werte in einem Cluster zusammen- Giovanna Guerrini and Norman W. Paton, gefasst werden können. Eine Fragmentierung der Original- editors, Joint 2013 EDBT/ICDT Conferences, tabelle anhand der Cluster ermöglichst ein effizientes Lauf- pages 430–441, New York, NY, USA, 2013. zeitverhalten der flexiblen Anfragebeantwortung. Durch ei- ACM. nige Metadaten (Root-Tabelle, Similarities-Tabelle, zusätzli- [SHL07] Myung Keun Shin, Soon-Young Huh, and che Spalte für Cluster-ID) werden alle typischen Datenbank- Wookey Lee. Providing ranked cooperative operationen unterstützt. query answers using the metricized knowledge Zukünftig soll insbesondere das dynamische Anpassen der abstraction hierarchy. Expert Systems with Fragmente untersucht werden: da sich durch Einfügungen Applications, 32(2):469–484, 2007. und Löschungen die Größen der Fragmente stark ändern [TCJM12] Aubrey Tatarowicz, Carlo Curino, Evan P. C. können, müssen zur Laufzeit Fragmente verschoben werden, Jones, and Sam Madden. Lookup tables: sowie gegebenenfalls zu kleine Fragmente in ein größeres ver- Fine-grained partitioning for distributed einigt werden beziehungsweise zu große Fragmente in klei- databases. In Anastasios Kementsietsidis and nere aufgespalten werden. Marcos Antonio Vaz Salles, editors, IEEE 28th International Conference on Data Engineering 8. REFERENCES (ICDE 2012), pages 102–113, Washington, DC, [BDIW14] Maheen Bakhtyar, Nam Dang, Katsumi Inoue, USA, 2012. IEEE Computer Society. and Lena Wiese. Implementing inductive [Wie13] Lena Wiese. Taxonomy-based fragmentation for concept learning for cooperative query anti-instantiation in distributed databases. In answering. In Data Analysis, Machine Learning 3rd International Workshop on Intelligent and Knowledge Discovery, pages 127–134. Techniques and Architectures for Autonomic Springer, 2014. Clouds (ITAAC’13) collocated with IEEE/ACM [CYC+ 96] Wesley W. Chu, Hua Yang, Kuorong Chiang, 6th International Conference on Utility and Michael Minock, Gladys Chow, and Chris Cloud Computing, pages 363–368, Washington, Larson. CoBase: A scalable and extensible DC, USA, 2013. IEEE. cooperative information system. JIIS, [Wie14] Lena Wiese. Clustering-based fragmentation 6(2/3):223–259, 1996. and data replication for flexible query [CZJM10] Carlo Curino, Yang Zhang, Evan P. C. Jones, answering in distributed databases. Journal of and Samuel Madden. Schism: a workload-driven Cloud Computing, 3(1):1–15, 2014. approach to database replication and partitioning. Proceedings of the VLDB Endowment, 3(1):48–57, 2010. [Gon85] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985. [HTGC10] J. Hill, J. Torson, Bo Guo, and Zhengxin Chen. Toward ontology-guided knowledge-driven xml query relaxation. In Computational Intelligence, Modelling and Simulation (CIMSiM), pages 448–453, 2010. [IW11] Katsumi Inoue and Lena Wiese. Generalizing conjunctive queries for informative answers. In Flexible Query Answering Systems, pages 1–12. Springer, 2011. [KLL+ 97] David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. Consistent hashing and random trees: 17 Automated Silhouette Extraction for Mountain Recognition Daniel Braun Michael Singhof Heinrich-Heine-Universität Heinrich-Heine-Universität Institut für Informatik Institut für Informatik Universitätsstraße 1 Universitätsstraße 1 40225 Düsseldorf, Deutschland 40225 Düsseldorf, Deutschland braun@cs.uni-duesseldorf.de singhof@cs.uni-duesseldorf.de ABSTRACT 1. INTRODUCTION With the rise of digital photography and easy sharing of Sharing our experiences with digital images is a significant images over the internet, a huge amount of images with no part of our today’s life, which is partly a result of the high notion of what they are showing exists. In order to overcome availability of digital cameras, like in smartphones, and the this problem, we – for the example of mountain recognition – high use of social networks, that simplifies the publication introduce a method, that is able to automatically recognise and sharing of images. As a consequence, the number of a mountain shown in a photography. images in the world wide web increases significantly. For Our method does not require GPS information stored in example, this can be seen on the image sharing platform the image, since most images are not GPS tagged, either Instagram, where users share an average of 70 million new because of the absence of a GPS sensor in the device or photos per day [1]. because it has been deactivated for a lesser power consump- As a result of such high numbers of images, searching tion, which often is the case with smartphones. Instead, we photos which show specific objects is challenging, because propose a method that is able to automatically extract the the majority of these images is not properly tagged with the mountain’s silhouette from a given image. This silhouette names of every object seen in them. So the need for efficient is then cleaned by removing artefacts and outliers, such as algorithms for automatic object recognition rises. In the last trees and clouds, with a histogram based approach. Finally, decades there were many advances in this research field, but the cleaned silhouette can be compared to reference data in especially the automatic identification of landmarks, which order to recognise the mountain that is shown in the pic- are subject to weather changes, areal erosion and vegetation, ture. For this, time series comparison techniques can be is still a challenging task, even if the amount of images with used to find matching silhouettes. However, because of the attached GPS data, which marks the geo-position of the huge number of reference silhouettes to compare against, we camera when the photo was shot, is rising. argue, that a preselection of those silhouettes is necessary The growing spread of devices with the capability of gen- and point out approaches to this problem. erating GPS tags for the images, like smartphones and dig- ital cameras with GPS units, enables many possibilities for Categories and Subject Descriptors an subsequent geo-localisation of images, due to the fact that GPS tags can significantly reduce the number of pos- I.4.8 [IMAGE PROCESSING AND COMPUTER VI- sible sights, buildings or landmarks to compare with. How- SION]: Scene Analysis—Object recognition; I.4.6 [IMAGE ever, there exist too many images without the advantage PROCESSING AND COMPUTER VISION]: Seg- of GPS tags, so that an automatic geo-localisation without mentation—Edge and feature detection; H.2.8 [DATABASE prior knowledge of the camera position is still a valuable MANAGEMENT]: Database Applications —Data min- aim. ing Our focus lies on the automatic landmark recognition, which we will describe by using the example of mountain Keywords recognition in images. To solve the question, which moun- tain can be seen on an given image, we match the skyline Object Recognition, Image Annotation, Outlier Detection, of the mountain in the image with silhouettes of mountains Image Segmentation, Skyline Recognition, Mountain Recog- in our database. For this purpose, we have to automatically nition, Time Series extract the exact skyline from the image, which is a diffi- cult 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 algo- rithm, 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 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- consists of the three steps silhouette extraction, silhouette banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. cleaning and silhouette matching. The section of the latter Copyright is held by the author/owner(s). 18 one will be a perspective of how to use the cleaned silhouette 3. SILHOUETTE RECOGNITION in further steps. The last chapter summarises this paper and The silhouette recognition process is basically a process in outlines future work. three steps. The first step is the extraction of the silhouette from a given picture. This silhouette is stored as a polygonal 2. RELATED WORK chain. During the second step, this silhouette is cleaned by The amount of publications for automated mountain re- identifying and removing outliers. The cleaned silhouette cognition increased significantly in the last two decades. is then used as the input to the third and final step, which Given a high number of publicly available digital elevation consists of matching the silhouette against the reference data maps (DEM), the consensus in many publications [2, 3, 4, 5, in order to be able to identify the structure in the picture. 10] is to use image-to-model matching for mountain recog- nition and orientation identification. 3.1 Silhouette Extraction Many approaches, like [3, 4, 10], make use of known GPS Extracting the silhouette is the first step in the mountain data for the image to align in the terrain. This reduces the identification process described in this paper. The task of search space for possible mountain silhouettes significantly, this step is the separation of the sky from the rest of the because the search of the correct mountains is limited in processed image. We therefore have a binary segmentation checking the surrounding of the camera’s position. task to solve, in which we check every pixel p of an image and Baboud et al. [3] need an estimated field-of-view to cal- decide if p shows a part of the sky or not. For a human this culate the rotation which maps the image to the terrain. would be easy to do in most cases, even though it would Therefore, the authors introduce a robust matching metric, be too much work and time to segment great numbers of using extracted edges in combination with a search space pictures manually. Because of that, we use a growing seed reduction to further reduce computation time. [10] uses a algorithm, like the algorithm described in [11], for which we standard Sobel-filter for the edge extraction. To identify the use the fact, that in most cases the pixels at the upper bound edges which are part of the mountain’s contours, the authors of the image are part of the sky. In the following section, propose the use of the Random Ferns classifier. Afterwards we will first describe some difficulties, which can make the they match the emerged contour map with the contour map segmentation task more complex. After that, our baseline extracted from the DEM. In [4] a 360-degree panorama of segmentation algorithm will be further explained. the surroundings of the image location is synthesized out of The segmentation of an image generally suffers from dif- a given DEM and used for matching the skyline extracted ferent problems, like under-/overexposure, which results in from the image. For that, they use a vector cross correlation a smaller difference between the pixel colours, or blur, which (VCC) technique to find the candidate matches. After fur- can be, for example, a result of a lossy compression of the ther refinement and recalculation of the VCC for each peak image. In addition, our binary segmentation task has even they can label the peaks with a high precision. some own problems to deal with. The first difficulty is a con- All three approaches show good results for their issue, sequence of the motif itself, because the weather in moun- but the need for GPS data for the processed image does tainous terrain is very volatile. This and the fact that, for not match our problem specifications, different from Baatz example in the alps, many mountain peaks are covered with et al. [2], in which the focus lies on images without GPS snow, can make the extraction of the mountain silhouette tag. They use an approach based on a cost function for out of an image imprecise. Furthermore differently coloured the belonging of a pixel to the sky respectively foreground. bands of cloud can lead to an extracted silhouette which lies They combine this approach with a relevance feedback-like in the sky and is therefore not part of the real skyline. The user interference, where the user can mark parts of the sky or second one is a result of possible obstacles, which hide the the foreground. This user intervention was needed for 49% of real silhouette of the mountain or lead to smaller segments the images in their dataset, which was collected during there within the sky segment. research. Thankfully, they published this dataset, so that Even though we are aware of these problems, our naive it will be used in this paper. After the contour extraction, segmentation algorithm cannot handle all of them. For the they match the coded contourlet with the contours extracted identification of artefacts as result of segmentation errors, from a DEM at several points on a predefined grid. At we use the second step of our chain, which is described in last, when they find a suitable match, they recalculate the section 3.2. Our segmentation algorithm uses the upper row geo-position of the camera. Naval et al. [5] also try to of pixels as seed for the sky segment. This means that we find the camera position and orientation, using a DEM to mark the upper pixels as sky and process every neighbouring position the camera on the world. For this purpose they pixel to let this segment grow. For this purpose we first match the extracted skyline from an image with a synthetic convert the processed photo to a gray-scale image G. Now skyline from a DEM. Different to both works we try to get we can define VG as overall variance of the brightness values. an automatically cleaned silhouette, thus removing obstacles Having VG , we now process every pixel p(x,y) which is not a or other artefacts, out of the processed image. part of the sky segment and mark it as sky candidate, if for Tao et al. [12] focus on the identification of the sky seen p(x,y) it holds that in an image and the search for images with a specific sky √ appearance. Therefore they define different sky attributes, Bp(x,y) − meanrp(x,y) < γ · VG like for example the sun position, which they extract in- dividually afterwards. At last they present their complete with Bp(x,y) the brightness of the pixel p(x,y) , meanrp(x,y) as system SkyFinder, in which an attribute based search is im- the mean of the brightness in an neighbourhood of the pixel plemented. On top of that, they provide a sky replacement with the radius of r and γ as a factor to scale the impact algorithm for changing the sky in an image. However, the of the standard derivation. This means that we mark a recognition of the skyline is not part of this system. pixel, if its distance to a local mean of brightness values 19 Figure 2: The result of the segmentation algorithm. (Left) The original image out of the dataset from [2]. (Right) The binary image after the segmentation. White pixels mark the ground segment. is smaller than a fixed percentage of the global standard describes the y-coordinate of that point in the picture. We derivation of all brightness values. The idea behind this start at the upper left pixel p(0,0) and search for the first non- term is, that the border between sky and ground has in sky pixel as start vertex v1 for our polygonal chain, which most cases a stronger contrast than the rest of the image, lies on the left pixel column with x1 = 0. Now, we have especially the sky. Therefore, the distance to the mean will two possibilities: First, we can find no pixel, which results be higher at the skyline as it will be at the border of possible in checking the next column until we find a pixel or we have clouds. With the connection of the upper bound to the reached the lower right pixel of the image. Otherwise, if a standard derivation, we want to take into account the images possible skyline pixel was found, the algorithm tracks the where the brightness is very homogenous, for example due transition between the sky and the ground in the following to overexposure, and therefore the contrast of the skyline manner. decreases. Having vi as the last extracted vertex of the silhouette, the In our experience this naive assumption shows good re- algorithm checks the 8-connected neighbours of this point sults for r = 5 and γ = 0.1 on most images out of the swiss (see the right side of figure 1) and chooses the non-sky point dataset published in [2]. In the future we will test more as next vertex which has the lowest angle between the in- complex algorithms, like for instance the skyline extraction coming line, defined by the two last vertices vi−1 and vi , algorithm proposed in [8], with the expectation that they and the outgoing line, defined by vi and the neighbouring will yield even better results. After we have marked all pos- point. This can easily be done, as shown in figure 3, by checking the 8-connected neighbours from vi in clockwise y direction, starting at the predecessor. The only exception is −1 the start point v1 , where we set v0 = (−1, y1 ). This means that we choose in this case the left direct neighbour, which p 0 p lies outside of the image, as predecessor. 1 x 2 3 4 −1 0 1 −1 0 1 1 vi 5 Figure 1: Two possible neighbourhoods of a pixel. (Left) 4-connected neighbourhood of the pixel p. vi−1 0 7 6 (Right) 8-connected neighbourhood of the pixel p. Figure 3: An example how to choose the next silhou- sible candidates, we can finally let the sky segment grow. For ette point. Starting at vi−1 as predecessor of the cur- that, we check for every pixel p(x,y) , if it is a 4-connected rent vertex vi , the algorithm searches in clockwise neighbour, for explanation see the left side of figure 1, to a direction for the next ground pixel (blue). Therefore pixel of the sky segment and marked as sky candidate (see the third pixel will be chosen. 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 Now, we have the border of the mountain as chain of and the ground, like the one shown in figure 2. neighbouring pixels. To reduce the amount of vertices with- For the silhouette extraction, we search a silhouette S = out loosing any information, we eliminate all vertices which (v1 , . . . , vn ) where every vertex vi = (xi , yi ) is a two di- bring no further information gain to the final silhouette in mensional point where xi describes the x-coordinate and yi the last step of the extraction phase. For this, we define the 20 Figure 4: Silhouette as black line with outliers in red on original image. information gain I of a vertex vj , with 1 < j < n, as get recognised as mountain. Since the outline of this outlier ( is not atypical for a mountain silhouette, this outlier is not 1, if ∠vj−1 vj vj+1 6= 180◦ recognised. Farther to the right, there are two other outliers Ivj = 0 otherwise. where clouds are recognised as mountain by the extraction step. These are, in this case, marked red and such detected This means that every vertex which lies on one line with his by the silhouette cleaning step. predecessor and successor carries no further information for Note, that there are a few parts of the silhouette that the extracted silhouette. After deleting every vertex with get marked as outliers but are not described above. These Ivj = 0, we obtain our final polygonal chain, which can are false positives. However, since the image here is used now be analyzed in the the cleaning phase described in the to showcase the different kind of outliers, these are not dis- following section. cussed here. The silhouette cleaning part of our algorithm is, again, 3.2 Silhouette Cleaning divided into three parts. As an input, it gets the silhouette The extracted silhouette from the previous step may con- S = (v1 , . . . , vn ) extracted from a picture. tain different disturbances. In this step, we try to get rid For the recognition of patterns inside the polygonal chain, of those, so that they cannot affect the step of silhouette this representation has disadvantages, because all vertices matching that gets described in section 3.3. Examples for are given in absolute positions. For outlier detection, a such disturbances are manifold, ranging from objects in front model where similar structures do look similar in their rep- of the mountain, such as trees, to errors produced during resentation is beneficial. Therefore, we convert S to a rep- the extraction process that can be caused by a low contrast resentation AP = (ap1 , . . . , apn ), with api = (li , ai ). Here, between the mountain line and the sky. Essentially, after we set finding an outlier, we currently cut elevations within this ( part of the silhouette away. |vi − vi−1 |, if i > 1 li = Some of such outliers are showcased in figure 4. Here, the 0 else black line is the silhouette that has been extracted by the extraction step as described in section 3.1. The red parts are and ai as the angle between the vector vi+1 − vi , and the those parts of the silhouette, that are automatically detected x-axis for i < n and an = 0◦ . Figure 5 illustrates this. as outliers. Examples for outliers are the tree tops to the During this step, points where the angle does not change left, that have correctly been marked as outliers. In the are removed. Also, artefacts consisting of angles of 180◦ center of the picture, there is a part of the mountain, that between two following segments get removed. has been cut out. Here the contrast between rock and blue The basic idea of the outlier detection method itself is sky gets to low for the extraction step to distinguish them. to compare histograms created from parts of the polygonal Right next to this, clouds around the lower peak in the back chain AP to a reference histogram. The latter hereby is created from the silhouettes of the ground truth data as given in [2]. v2 The mentioned histograms consist of the two dimensions a2 = −45◦ segment length and angle size, just as the points in the | transformed polygonal chain AP , and are normalised. This v1 − l3 means, that the sum of the frequencies of each bucket is 1. 2 = |v |v 3 = For the reference data, we compute one histogram from each l2 − image’s silhouette. Finally, the mean of all these histograms v2 | a1 = 45◦ is computed and becomes the reference histogram Hr . l1 = 0 v1 v3 a3 = 0◦ In order to find outliers, we use a sliding window ap- proach over the polygonal chain APi of a given input im- Figure 5: Conversion of polygonal chain for better age. We therefore use a section of m successive segments pattern recognition. api , . . . , api+m−1 in order to compute a histogram Hi with the same bucket distribution as in Hr . Then, for every point 21 used to compute Hi , we store the distance between Hi and so that we find a vertex ve . This results in four vertices’ Hr . By this approach, for most points, multiple distance indices j ≤ s < e ≤ j 1 . From this, the part between vs and values get stored when the sliding window is moved on. The ve is now finally replaced by a straight line between these final distance di for a point api is now computed as the two vertices. average distance of all distances stored for this point. By this, we obtain a cleaned silhouette that can be used As distance function in this case we use the one given in in further steps for the silhouette matching. the following 3.3 Silhouette Matching Definition 1. Let G = (g1 , . . . , gk ), H = (h1 , . . . , hk ) be Once the silhouette is extracted and cleared of outliers, normalised histograms with the same bucket distribution. it is now time to match it to the reference data in order to The above average distance of G to H is defined by determine the mountain that is shown by the picture. Cur- D(G, H) := max(|aab(G)|, |aab(H)|) − |aab(G) ∩ aab(H)|, rently, we have not implemented any method, yet. However, we will introduce some methods that we are going to test in where the future. 1 The converted silhouettes AP = (ap1 , . . . , apn ) from the aab(F ) := i ∈ {1, . . . , k} fi ≥ k previous section can be easily changed to be interpreted as time series by setting AP 0 = (ap01 , . . . , ap0n ) where with F being a normalised histogram with k buckets. Xi This can be implemented to compute in linear time to the ap0i = (li0 , vi ) = ( li , v i ) number of buckets, or, for histograms of a fixed length, in j=1 constant time. Based on a number of images used as training data, in for api = (li , vi ). By this conversion, every point ap0i has the same way as described above, the medium distance µ the length of the polygonal chain until that point as its first and the standard deviation σ can be determined. We use component. Since li > 0 for all i > 1, the length component these precomputed values in order to find two thresholds of AP 0 is strictly monotonic increasing, just as the time τin > τout , such that we can characterise a point api as a dimension in a time series. This is because we do not allow strong anomaly if it holds that its distance identical points in our silhouette. With this, it is possible to compare different silhouettes for similarity by using time di ≥ µ + τin · σ series comparison techniques such as [6, 9]. These methods and a weak anomaly if have the advantage of being rotation invariant which, in our case, means that the image does not have to have the same di ≥ µ + τout · σ. image section as our reference data. We also determine a length threshold l. For a part of the Due to the great number of mountains and peaks that ex- polygonal chain, to be recognised as an outlier, it must hold ist and on the notion, that every peak can be photographed that at least l successive points api , . . . , api+l−1 must be from different angles, there are hundreds of thousands of sil- strong anomalies. An outlier can have any length that is houettes to match for each query image. Due to this it is equal to or bigger than l. Finally, if we find such an outlier, clear, that even with a high-performance matching method we expand it by adding points to it that are adjacent to a preselection is necessary. the outlier and weak anomalies. By this, it is possible for There exist many methods suitable for this, such as the outliers to merge. technique presented in [7] that uses the position of the sun As an example, say, ap7 , . . . , ap20 are strong anomalies and the time of day, at which the photo has been taken, in because their distances d7 , . . . , d20 are bigger than µ+τin ·σ. order to compute the approximate location on earth. How- If we set l = 4 for this example, these thirteen points are ever, this method has an average localisation error of about recognised as an outlier o = {7, . . . , 20}. Now, let us assume 100 km. Because of this, it is useful for a rough preselection, that ap5 and ap6 are weak anomalies as well as ap22 . Then however not sufficient in our case. ap6 and ap5 belong to the extended outlier, because they Therefore, we aim to reuse the idea of our outlier de- are both adjacent to the outlier. On the other hand, ap22 tection method for matching. Instead of computing his- does not belong to the extended outlier, because ap21 is not tograms of short sequences of the silhouette, in this case the part of the outlier since it is not a weak anomaly. histogram HS over the whole silhouette AP is computed. Once all outliers have been detected, the next step is to This is then compared to the reference images’ histograms remove them. Currently, we use a very simple approach for HRi , i ∈ {1, . . . , nref } with nref the number of the reference this where, in the original silhouette S, the overhanging part image, which we, as discussed in section 3.2, have to compute of the outlier is replaced by a straight line. This is based on anyway. The comparison between two histograms, with our the notion, that the reasons for most outliers in the silhou- distance function, is linear to the number of buckets in the ette are either trees or clouds. By just removing them, in histograms, or, since this number is fixed, constant. Now, many cases, we get results that resemble the original shape let d(HS , HRi ) denote the distance between the histogram of the mountain in an easy way. of the new silhouette S and the ith reference histogram. If Let o = {i, . . . , j} with i + l ≤ j be an outlier. Then we d(HS , HRi ) is small, this does not necessarily mean, that draw a straight line from vi to vj . Now, while the distance the silhouettes are identical or even really similar, because between vs , starting with s = i + 1, and that straight is the histogram representation does not preserve the order of smaller than a preset value d, we find the vertex vs with the the contained elements. On the other hand, if the distance largest index, that is close enough to the original straight 1 In general, it is possible, that s ≥ e. In this case, no line. The same is done from the other end of the outlier substitution is performed. 22 between two silhouettes is large, we can say that those sil- buildings are mostly photographed with the sky as back- houettes are not similar. ground, too. Furthermore, we aim to test our method on Due to this, we plan to only use the time series compar- more diverse areas, such as the recognition of certain ob- ison methods from the beginning of this section on those jects in MRT screenings or X-rays. These tasks will make reference silhouettes, that yield small histogram distances. it necessary to change some parts of our approach, natu- Further on, we will evaluate if the position determination rally, because there, it will be interesting to be able to tell, method presented in [7] is able to boost the performance of for example, which organs are shown in a picture, or, as a our solution. next step, to be able to identify different kinds of tumours automatically. 4. CONCLUSION AND FUTURE WORK In this work we presented a new approach to motif recog- 5. REFERENCES nition based on silhouettes on the example of mountains. [1] Instagram @ONLINE, accessed April 7, 2015. Our method consists of three steps, of which the first two https://instagram.com/press/. have already been implemented while we are working on the [2] G. Baatz, O. Saurer, K. Köser, and M. Pollefeys. third step. First results show that we are able to extract sil- Large Scale Visual Geo-Localization of Images in houettes with relatively few errors from images and that our Mountainous Terrain. In Computer Vision - ECCV outlier detection step does indeed find meaningful anoma- 2012, Lecture Notes in Computer Science, pages lies. We have currently tested the first two steps of our 517–530. 2012. [3] L. Baboud, M. Čadı́k, E. Eisemann, and H.-P. Seidel. Automatic Photo-to-terrain Alignment for the Annotation of Mountain Pictures. In Proc. of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR ’11, pages 41–48, 2011. [4] R. Fedorov, P. Fraternali, and M. Tagliasacchi. Mountain Peak Identification in Visual Content Based on Coarse Digital Elevation Models. In Proc. of the 3rd ACM International Workshop on Multimedia Analysis for Ecological Data, MAED ’14, pages 7–11, 2014. [5] P. C. N. Jr, M. Mukunoki, M. Minoh, and K. Ikeda. Estimating Camera Position and Orientation from Geographical Map and Mountain Image. In 38th Research Meeting of the Pattern Sensing Group, Society of Instrument and Control Engineers, pages 9–16, 1997. [6] E. J. Keogh, L. Wei, X. Xi, S.-H. Lee, and M. Vlachos. Figure 6: Silhouette as black line with outliers in LB Keogh Supports Exact Indexing of Shapes under red on original image. Rotation Invariance with Arbitrary Representations and Distance Measures. In VLDB, pages 882–893, 2006. approach as described in sections 3.1 and 3.2 on 18 images [7] J.-F. Lalonde, S. G. Narasimhan, and A. A. Efros. from the reference dataset. Results for the first of these im- What Do the Sun and the Sky Tell Us About the ages can be seen in figures 2 and 4. Of these 18 images, 17 Camera? International Journal of Computer Vision, result in good silhouettes, i.e. silhouettes with relatively few 88(1):24–51, 2010. outliers of which most get marked and are correctable. The [8] W.-N. Lie, T. C.-I. Lin, T.-C. Lin, and K.-S. Hung. A last image, though, does not get recognised correctly due to robust dynamic programming algorithm to extract low contrast in terms of brightness. This is illustrated by skyline in images for navigation. Pattern Recognition figure 6. We do, however, notice this, because most of the Letters, 26(2):221–230, 2005. silhouette gets marked as outlier. [9] J. Lin, R. Khade, and Y. Li. Rotation-invariant The next step is to implement a silhouette matching al- similarity in time series using bag-of-patterns gorithm. This has already been outlined in section 3.3. Of representation. J Intell Inf Syst, 39(2):287–315, 2012. course, it is necessary, to benchmark the parts of that step in order to find weaknesses early on. Once the system is [10] L. Porzi, S. R. Buló, P. Valigi, O. Lanz, and E. Ricci. complete we aim to evaluate it on the whole of the dataset Learning Contours for Automatic Annotations of of [2]. Based on these result, we will tune the parameters of Mountains Pictures on a Smartphone. In Proc. of the our method to find settings, that do work well generally. International Conference on Distributed Smart We also aim to create a mountain recognition corpus of our Cameras, ICDSC ’14, pages 13:1–13:6, 2014. own since [2] focuses on images of mountains in Switzerland [11] F. Y. Shih and S. Cheng. Automatic seeded region only. Our corpus is aimed to be international and should growing for color image segmentation. Image and feature images from mountains from all over the world. Vision Computing, 23(10):877–886, 2005. Another interesting perspective is to test, whether our [12] L. Tao, L. Yuan, and J. Sun. SkyFinder: framework will work on other types of images, such as city Attribute-based Sky Image Search. In ACM skylines or pictures of single buildings. With these tasks SIGGRAPH 2009 Papers, SIGGRAPH ’09, pages the method itself could be quite similar, since skylines and 68:1–68:5, 2009. 23 Slicing in Assistenzsystemen Wie trotz Anonymisierung von Daten wertvolle Analyseergebnisse gewonnen werden können Hannes Grunert Andreas Heuer Lehrstuhl für Datenbank- und Lehrstuhl für Datenbank- und Informationssysteme Informationssysteme Universität Rostock Universität Rostock 18051 Rostock 18051 Rostock hg(at)informatik.uni-rostock.de ah(at)informatik.uni-rostock.de Kurzfassung mit weiteren Informationen, beispielsweise dem Nutzerprofil Datenschutz stellt eine große Herausforderung für die eines sozialen Netzwerkes verknüpft. Aus den so gewonne- Entwicklung von Informationssystemen dar. Obwohl nen Informationen lassen sich Verhaltensmuster, Präferen- viele Konzepte zur Wahrung des Datenschutzes beste- zen und zukünftige Ereignisse ermitteln. Auf Basis dieser hen, werden Datenschutztechniken in der Regel nicht in Daten reagiert das Assistenzsystem eigenständig auf die Be- Datenbankmanagement- und Assistenzsysteme integriert. dürfnisse des Nutzers und regelt Raumtemperatur, Lüftung In diesem Artikel stellen wir eine SQL-Implementierung und weitere vernetzte Geräte. des Slicing-Konzeptes von Li et al. [10] vor. Es erfolgt eine Assistenzsysteme sammeln häufig wesentlich mehr Infor- detaillierte Betrachtung hinsichtlich der Parametrisierung mationen als sie für die Ausführung ihrer Funktionen benö- des Algorithmus und dessen Auswirkung auf Informations- tigen. Der Nutzer hat dabei meist keinen oder nur einen un- verlust und Grad des Datenschutzes. wesentlichen Einfluss auf die Speicherung und Verarbeitung seiner personenbezogenen Daten. Dadurch ist sein Recht auf informationelle Selbstbestimmung verletzt. ACM Klassifikation Die Einführung von Datenschutzmechanismen wird sei- H.2.4 [Database Management]: Systems—Query Proces- tens der Entwickler von Assistenzsystemen skeptisch an- sing; K.4.1 [Computer and Society]: Public Policy Issu- gesehen. Es wird befürchtet, dass durch die Anonymisie- es—Privacy rung der Daten die Entwicklung des Systems zurückgewor- fen wird. Durch die Anonymisierung bzw. Pseudonymisie- Stichworte rung der Nutzerdaten gehen Detailinformationen verloren, wodurch Analysefunktionen ungenauere Ergebnisse zurück- Datenbanken, Datenschutz, Datensparsamkeit liefern und im Extremfall unbrauchbar werden. Im Rahmen des Graduiertenkollegs MuSAMA1 werden 1. EINLEITUNG Datenschutzkonzepte für die Anfrageverarbeitung in Assis- Zwei Kernaspekte des Datenschutzes sind Datensparsam- tenzsystemen entworfen. Diese werden allerdings nicht on- keit und Datenvermeidung. §3a des Bundesdatenschutzge- top auf die bestehenden Analysefunktionen aufgesetzt, son- setzes [1] definiert diese als Forderung, dass Informations- dern in enger Zusammenarbeit während der Entwicklung systeme möglichst wenig personenbezogene Daten erheben, integriert. Ein Beispiel für dieses Zusammenwirken ist die verarbeiten oder nutzen sollen. Dies betrifft neben der Kon- Umsetzung des Slicing-Konzeptes von Li et al. [10] zusam- zeption von Informationssystemen auch den Prozess der Da- men mit der Regressionsanalyse [6] auf hochdimensionalen tenverarbeitung. Sensordaten. Assistenzsysteme sollen den Nutzer bei der Bewältigung seines Alltags, sei es im Beruf oder zu Hause, unterstüt- 1.1 PArADISE zen. Über verschiedene Sensoren, wie Bewegungssensoren Für die Umsetzung von Datenschutzrichtlinien in smar- und Wärmemessgeräte, werden Informationen über die mo- ten Umgebungen wird derzeit das PArADISE2 -Framework mentane Situation und die Aktivitäten des Anwenders ge- [7] entwickelt, welches insbesondere die Aspekte der Da- sammelt. Diese Daten werden im System gespeichert und tensparsamkeit und Datenvermeidung in heterogenen P2P- Systemen realisieren soll. PArADISE ist Werkzeug, welches den Entwicklern und Nutzern von Assistenzsystemen helfen soll effizient und da- tenschutzkonform Anfragen auf Sensordaten zu formulieren. Der Kern des Frameworks ist ein datenschutzfreundlicher 1 Multimodal Smart Appliance Ensembles for Mobile Applications 2 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- Privacy-Aware Assistive Distributed Information System banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. Environment Copyright is held by the author/owner(s). 24 Anfrageprozessor (siehe Abbildung 1). Dieser Prozessor er- spiels. Das letzte Kapitel fasst den Beitrag zusammen und hält als Eingabe zum einen die Datenschutzeinstellungen der gibt einen Ausblick auf zukünftige Arbeiten. Nutzer, zum anderen den Informationsbedarf des Systems anhand von Anfragen an das Datenbanksystem. Als Aus- 2. SLICING gabe wird ein anonymisierter, annotierter Teil des Daten- In [10] stellen Li et al. ein neues Anonymisierungskonzept bestandes zurückgeliefert. In den Annotationen wird ange- vor, welches auf der Permutation von Daten beruht. Im Ge- geben, wie der Datenbestand anonymisiert wurde und ob gensatz zu den bisher gängigen Anonymisierungsverfahren bereits die erforderlichen Analysen der Daten auf dem aus- wie k-Anonymität [11] verzichtet dieses Verfahren auf Ge- führenden Knoten umgesetzt wurden. Falls keine Analyse neralisierungstechniken. durchgeführt wurde, muss der Knoten, welcher das Ergebnis Eine Relation ist k-anonym, wenn, auf Basis der identifi- erhalten hat, die weitere Verarbeitung der Daten überneh- zierenden Attributmengen der Relation, ein Tupel von k-1 men. anderen Tupeln nicht unterscheidbar ist. In der Regel wird Der Anfrageprozessor arbeitet in zwei Stufen. Ziel der ers- eine Person durch ein Tupel in der Relation dargestellt. In ten Stufe, der Vorverarbeitungsphase, ist die Modifikation Assistenzsystemen werden, je nach Anwendungsgebiet, nur der eingehenden Anfragen, sodass möglichst wenige Daten Informationen über eine Person gesammelt. Dies gilt z. B. aus der Datenbank ausgelesen werden. Dazu wird die Anfra- bei der Überwachung von Demenzpatienten. Dort lassen sich ge analysiert. Durch die Analyse lässt sich erkennen, welche mittels der aufgenommenen Daten einzelne Handlungen ei- Attribute angefragt werden, wie diese hinsichtlich ihres Wer- ner Person identifizieren. Diese gilt es ebenfalls zu anonymi- tebereichs gefiltert und ggf. aggregiert und gruppiert wer- sieren. den. Bei der Generalisierung von Daten kommen Detailinfor- Die so erhaltenen Informationen über die Anfrage werden mationen abhanden, die bei vielen Analysefunktionen benö- mit den vorformulierten Privatheitsansprüchen [4] des Nut- tigt werden. Das Slicing-Verfahren verspricht einen höheren zers verglichen. Treten an dieser Stelle Widersprüche auf, Datennutzen, indem es die Verbindung von stark korreli- wie beispielsweise der Zugriff auf ein Attribut, welches der erenden Attributen bewahrt. Auf dieser Grundlage ist es Nutzer nicht von sich preisgeben möchte, wird die Anfrage trotz Anonymisierung weiterhin möglich Data-Mining- und angepasst. Dabei werden verschiedene Techniken, wie An- Analyse-Techniken, wie Regressionsanalysen, anzuwenden. frageumschreibungen und Abbildungen auf Sichten, ange- Das Konzept permutiert nicht den kompletten Datenbe- wandt. stand, sondern partitioniert die Daten sowohl horizontal als In der Nachverarbeitungsphase erfolgt, sofern erforder- auch vertikal. Bei der horizontalen Partitionierung (Tuple lich, die Anonymisierung der Daten. Dabei wird überprüft, Partition) wird der Datenbestand nach festgelegten Filter- ob spezielle Kriterien wie k-Anonymität [11] zutreffen. An- kriterien (Selektion nach einem bestimmten Attribut, An- schließend erfolgt die Anonymisierung der Daten unter Be- zahl an Partitionen, ...) in mehrere Mengen von Tupeln zer- rücksichtigung des Grades der benötigten Anonymität und legt. des Informationsverlustes [8] zur Wahrung von Funktionali- Die vertikale Partitionierung (Attribute Partition) unter- tät und Datenschutz. teilt den Datenbestand spaltenweise, indem aus der vorhan- Durch die Vorverarbeitung der Anfrage müssen weniger denen Attributmenge mehrere kleine Attributmengen gebil- Daten in der Nachverarbeitungsphase anonymisiert werden. det werden. Eine mögliche vertikale Zerlegung besteht im Dadurch erfolgt nur eine geringe Erhöhung der Antwortzeit Aufteilen der Attribute eines Quasi-Identifikators [2] auf auf die Anfrage. mehrere Partitionen. 1.2 Laufendes Beispiel Aus einem Datenbestand der durch n horizontale und m vertikale Partitionsvorgaben zerteilt wird, entsteht ein Ras- Die Umsetzung des Slicing-Konzeptes wird in diesen Ar- ter aus n*m kleineren Relationen. Jede dieser Teilrelationen tikel anhand eines laufenden Beispiels erläutert. Für die Im- wird anschließend permutiert, indem die Reihenfolge der Tu- plementation und Evaluation des Algorithmus wurde die pel vertauscht wird. Die permutierten Relationen werden Adult-Relation aus dem UCI Machine Learning Reposito- anschließend wieder zu einer einzelnen Relation verknüpft. ry [9] verwendet. Die Relation besteht aus personenbezoge- nen Daten, bei denen Schlüssel sowie Vor- und Nachname der betroffenen Personen entfernt wurden. Die verbleiben- 3. UMSETZUNG IN DER RELATIONALEN den 15 Attribute enthalten weitere personenbezogene Anga- ALGEBRA ben, wie beispielsweise Alter, Ehestand, Staatsangehörigkeit Für das Slicing-Konzept wird von Li et al. eine grobe Me- und Schulabschluss. thodik für die Implementierung vorgestellt. In diesem Ab- Tabelle 1 zeigt einen Ausschnitt der gesamten Relation. In schnitt demonstrieren wir die Adaption des Verfahrens auf diesem Artikel wird gezeigt, wie diese Relation schrittweise die relationale Algebra. Konkrete Implementierungsdetails in eine anonymisierte Relation (siehe Tabelle 3) überführt werden im nachfolgenden Kapitel vorgestellt. wird. Der Rest des Artikels ist wie folgt strukturiert: Kapitel 2 3.1 Schritt 1: Horizontaler Split gibt einen Überblick über das Anonymisierungskonzept von Im ersten Schritt wird die Relation R in n disjunkte Par- Li et al. Im folgenden Kapitel gehen wir detailliert darauf titionen R1 , ..., Rn zerlegt. Für jede Partition Ri wird eine ein, wie das Konzept durch Operationen aus der Relationen- Selektionsbedingung ci angegeben, welche die Tupel aus R algebra realisiert werden kann. In Kapitel 4 wird beschrie- den Partitionen zuordnet: ben wie die Implementation des Konzeptes in SQL erfolgt. Kapitel 5 evaluiert den Ansatz anhand des laufenden Bei- R1 := σc1 (R), ..., Rn := σcn (R). (1) 25 Abbildung 1: Das Konzept des datenschutzfreundlichen Anfrageprozessors Age Workclass Occupation Relationship Race Sex 39 State-gov Adm-clerical Not-in-family White Male 50 Self-emp Exec-managerial Husband White Male 38 Private Handlers-cleaners Not-in-family White Male 53 Private Handlers-cleaners Husband Black Male 28 Private Prof-speciality Wife Black Female 34 Private Sales Husband White Female Tabelle 1: Die Beispielrelation vor der Anonymisierung Die Auswahl der Selektionsbedingungen muss dabei ge- auf unterschiedliche Partitionen zu verteilen. Die Ermittlung schickt gewählt werden. Eine Möglichkeit besteht aus der von identifizierenden Attributmengen, sogenannten Quasi- Selektion nach einem bestimmten Attribut, wobei für jeden Identifikatoren [2], lässt sich mit geringem Aufwand [5] vor einzelnen auftretenden Attributwert (oder eine Menge von der Anonymisierung realisieren. Attributwerten) eine Selektionsbedingung der Form attri- but = ’Wert’ aufgestellt wird. Eine weitere Variante besteht 3.3 Schritt 3: Permutation darin, die Tupel in R zu nummerieren (neues Attribut rank) Nach der Bildung der Teilrelationen Rij erfolgt die ei- und die Selektionen in der Form ’rank between vj and vk ’3 gentliche Anonymisierung. Die Permutation erfolgt durch zu beschreiben. den Ordnungsoperator τ , welcher die Tupel jeder Teilrelati- on sortiert. In Abschnitt 4.2 wird genauer erklärt wie eine 3.2 Schritt 2: Vertikaler Split zufällige Sortierung erfolgen kann. Das Resultat der Permu- Nachdem die Relation R in mehrere kleinere Relationen tation wird in der Liste Lij hinterlegt: Ri zerlegt wurde, wird jede Ri durch Projektionen weiter unterteilt. Jede Projektion πattributmengej (Ri ) wählt dabei Lij := τ(Rij ). (3) ein oder mehrere Attribute aus der Relation R aus. Für jede An dieser Stelle geschieht ein kleiner Bruch mit der rela- Partitionen Ri werden dabei die gleichen m Projektionen tionalen Algebra. Der Ordnungsoperator τ darf zwar auf angewandt um die m Teilrelationen Rij aus Ri zu bilden: Relationen angewandt werden, liefert allerdings keine Rela- Ri1 := πattributmenge1 (Ri ), ..., Rim := πattributmengem (Ri ). tion, sondern eine Liste zurück. τ darf somit nur als letzter Operator angewandt werden [3]. Dies stellt ein Problem dar, (2) weil für den Slicing-Algorithmus die permutierten Listen im Die Attributmengen in den Projektionen müssen dabei nicht zwangsweise disjunkt sein4 . Sie dürfen keine identifizierende letzten Schritt wieder zusammengefügt werden müssen. Attributmenge enthalten, da ansonsten Rückschlüsse auf die Die Listen müssen entsprechend wieder zurück in Rela- Identität einer Person gezogen oder Handlungen eindeutig tionen überführt werden. Um die Ordnung zu bewahren, wird jedes Tupel mit einer Ordnungszahl Ord (siehe Tabelle bestimmt werden können. Die Auswahl der Attributmengen sollte dabei in Abstimmung mit den Analysefunktionen ge- 2) versehen, welche ihre Position in der Liste widerspiegelt. troffen werden, um z. B. stark korrelierende Attribute nicht Die Ordnungszahl wird für die folgenden Verbundoperatio- nen benötigt. Die permutierten Relationen werden mit Rij 0 3 vj , vk nummerische Werte bezeichnet. 4 Im grundlegenden Algorithmus von Li et al. [10] wird Dis- junktheit vorausgesetzt. Erweiterungen setzen Disjunktheit 3.4 Schritt 4: Zusammenfügen nicht voraus. Im letzten Schritt erfolgt das Zusammenfügen der permu- 26 Ord Age Workclass Ord Occupation Relationship Ord Race Ord Sex 1 39 State-gov 1 Adm-clerical Not-in-family 1 White 1 Male 2 50 Self-emp 2 Exec-managerial Husband 2 White 2 Male 3 38 Private 3 Handlers-cleaners Not-in-family 3 White 3 Male Ord Age Workclass Ord Occupation Relationship Ord Race Ord Sex 1 53 Private 1 Handlers-cleaners Husband 1 Black 1 Male 2 28 Private 2 Prof-speciality Wife 2 Black 2 Female 3 34 Private 3 Sales Husband 3 White 3 Female Tabelle 2: Beispielrelation nach horizontalem und vertikalem Split. Der horizontale Split erfolgte auf dem internen Attribut ROW_ID. Für den vertikalen Split wurden die Attribute Age und Workclass sowie Occupation und Workclass zusammenge- fasst. Race und Sex wurden in jeweils einzelne Partitionen zusammengefasst. Age Workclass Occupation Relationship Race Sex 39 Private Exec-managerial Husband White Male 38 State-gov Adm-clerical Not-in-family White Male 50 Self-emp Handlers-cleaners Not-in-family White Male 28 Private Handlers-cleaners Husband Black Female 34 Private Sales Husband Black Female 53 Private Prof-speciality Wife White Male Tabelle 3: Beispielrelation nach Anwendung des Slicing-Konzeptes tierten Teilrelationen Rij 0 zur permutierten Gesamtrelation SELECT ∗ R . Das Zusammenfügen geschieht dabei in zwei Teilschrit- 0 FROM