Big Data PraktikumAbteilung Datenbanken

Sommersemester 2016

Orga

Ziel: Entwurf und Realisierung einer Anwendung / eines Algorithmus unter Verwendung existierender Big Data Frameworks

Ablauf

Anwesenheitspflicht der Gruppe zu allen Testaten

Bis Ende April Erstes Treffen mit Betreuer (Terminanfrage per Mail)

Ende Mai Testat 1: System kennenlernen / Datenimport / Lösungsskizze

Ende Juli Testat 2: Implementierung und Ergebnisse vorstellen

Anfang August (04. und 05.08.2016) Testat 3: Präsentation

15 Minuten pro Gruppe

Anwesenheitspflicht aller Praktikumsteilnehmer

Technische Details

Quellcode: GitHub Repository Gruppe => Collaborators

Werden nach Praktikum zu https://github.com/leipzig-bigdata-lab geforked

Java: Apache Maven 3 für Projekt Management

Test Driven Development erwünscht Siehe Dokumentation zu Unit Tests in jeweiligen Frameworks

Quellcode Dokumentation zwingend erforderlich!

Stabile Versionen verwenden (ggf. Rücksprache) z.B. Flink 1.0.1 statt 1.1-SNAPSHOT

Lokal lauffähige Lösungen können auf dediziertem Cluster ausgeführt werden Terminabsprache Anfang Juli mit junghanns@informatik.uni-leipzig.de

Datensätze https://github.com/caesar0301/awesome-public-datasets

Recommendation & MachineLearning mit Flink

Eric Peukert

Recommendation & MachineLearning mit Flink

• Collaborative filtering with Alternating Least Squares

• Apache Flink Machine Learning Library

Rambo Star Trek Pocahontas

Alice

Bob

Peter ??

Recommendation & Machine Learning mit Flink (2)• Workflow

1. Parse data from Movielens -> http://grouplens.org/datasets/movielens/ - or IMDb(if suffient) to get Movies and ratings

2. Import into Flink

3. Train a Model with ALS within Flink

4. Apply Model

5. Small web-based application• search 3 movies from Movielens, give rating

• show rating coming from the collaborative filtering

• optional show visual graph of movies and their distances

Text-Reuse Analysis with Gradoopand Apache Flink

Eric Peukert

Text-Reuse Analysis with Gradoopand Apache Flink

• Analyze text-reuse in large text corpus (German Text Archive or Bible Corpus or EU-Legal Texts)

Text-Reuse Analysis with Gradoop and Apache Flink (2)• Workflow

• Import/Parse Data, build textfragments as nodes (Import text in graph-format)

• compute cross-wise similarity based on simple measure with gradoop

• provide a simple web-based visualization of citation graph

Big Data Image Processing withOpenCV and Apache Spark

Eric Peukert

Big Data Image Processing withOpenCV and Apache Spark

• Image Processing with OpenCV• face recognition

library

• Combination with Apache Spark

Big Data Image Processing with OpenCV and Apache Spark (2)

• Workflow1. Set up Spark with OpenCV2. Load test image/video data for image regognition

(http://pascal.inrialpes.fr/data/human/ )3. Optional – produce test data4. Implement distributed image regognition task5. Visualize results of regognition6. Optional (search by photo)

PPRL on FlinkZiad Sehili

Privacy Preserving Record Linkage

• Object matching with encrypted data to preserve privacy• Data exchange / integration of person-related data

• Many uses cases: medicine, sociology, business, …

Privacy Preserving Record Linkage

• General Protocol

Owner 1

Linkage Unit

matches

Owner 2parameters

Dataset Dataset

encoding encoding

Linkage algorithm

Pairs of IdsPairs of Ids

PPRL on Flink

• 1- Coding with Bloom Filter

select relevant fields for matching

recordGenerate

tokens

Use a family of hash functions to map each token to the same fixed-size bit vector

Bit vector/ fingerprint

first name, last name, address

set of tokens (e.g. trigrams)

(T)

(T)

(T)

each token T

0

0

0

0

0

0

0

0

0

1

1

0

1

1

0

1

r1

1

1

1

h1

h2

hn

PPRL on Flink

• 1- Using LSH for Blocking

0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0

1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0

0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0

0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1

1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0

1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0

Min-hashFunctions

key3

key1

key2

key3

key1

key4

id3

id1

id2

id6

id4

id5

Key1: id1 id4

Key3: id3 id6

Key2: id2

Key4: id2

Tweet Analyse von NewsVictor Christen

Tweet Analyse von News

„Aufsichtsratschef

Michael Müller rückt von

Geschäftsleitung ab“

„Konzept- und ahnungslos

Beschulung von

Flüchtlingskindern: Politik setzt

auf Aktionismus“

„Viertelmillion gegen TTIP “

12.10.2015 14.10.2015

Über welche Themen wird häufig berichtet?

Welche Nachrichtendienste sind sich ähnlich?

Findet ein zeitgleicher Themenwechsel von allen Diensten statt?

Aufgabenstellung

1. Speicherung der Tweets von Nachrichtendiensten für Deutschland

2. Identifikation der Topics für definierte Zeitabschnitte1. Analysegeeignete Speicherung der Topic-Vektoren

3. Evaluierung der Hypothesen mittels Clustering und Präsentation1. Identifikation der Hot- Topics2. Identifikation ähnlicher Dienste Dienste berichten über die

selben Themen3. Identifikation der Themen, die die Community interessieren

Ähnlichkeit zwischen Topic-Vektoren der Community und der Dienste

Technologien und Hinweise

• Flink

• Verwendung der Streaming API oder der Rest API von Twitter • Eingrenzung auf Deutschland

• Clustering• Erstellung der Topics mittels TF/IDF und Filterung

• Erstellung von Clustern ähnlicher Tweets basierend auf den Top-K TF/IDF Vektoren für einen Tweet• Community Detection von Flink

Entity-Resolution on FlinkVictor Christen

Entity-Resolution on Flink

• Essentieller Bestandteil für die Integration mehrerer Datenquellen

• Use Cases• Produktportale

• Publikationsanalyse

• Klinische Forschung Integration von Patientendaten

• ….

Entity-Resolution

• Identifikation einer Menge von Korrespondenzen zwischen Objekten mehrerer Datenquellen, die gleich sind.

Probleme

• Großer Suchraum

• Fehlerhafte Daten, unterschiedliche BeschreibungQualität des Object-Mappings

Ziel

• Semi -automatische Verfahren für die effektive und effiziente Identifikation eines Object-Mappingszwischen mehreren Datenquellen

Aufgabenstellung

• Implementierung eines allgemeinen Match-Workflows für Publikationsdatensätze

Workflow

Preprocessing Matching Postprocessing

• Normalisierung• Textuelle

Normalisierung• Vorberechungen

• Blocking

• Generierung eines Mappingsmittels einer Kombination mehrerer Match-Verfahren

• Aggregation und Selektion der Matchergebnisse der einzelnen Match-Verfahren

PublikationenDBLP

PublikationenACM

Technologien und Hinweise

• Umsetzung in Flink

• Einlesen • Publikationsdatensätze im CSV Format• [id, title, authors, Venue, year]• Normalisierung der Autoren

• Preprocessing• Kleinschreibung

• Blocking• Sorted Neighborhood Blocking basierend auf dem Jahr

• Matching• Jaro-Winkler, Soft-TF/IDF Realisierung

String Similarity on FlinkMarkus Nentwig

Einfacher Match WorkflowPreprocessing Matching Postprocessing

- Vergleich von Ähnlichkeiten auf Objekteigenschaften- Spezielle Metriken für String-Vergleiche, etwa Trigram + Dice:

• similiarity(‘TRUNK’, ‘TRUNCUS’)

1. Token sets

• {TRU, RUN, UNK}

• {TRU, RUN, UNC, NCU, CUS}

2. Intersect

• {TRU, RUN}

3. Dice metric

• 22 / (3+5) = 4/8 = 0.5

Mögliche Lösungen

• Naïve: vergleiche Tokens der beiden Strings über Schleife• Viele Vergleiche nötig

• “Sort-Merge” Lösung [1]: • Vermeide String-Vergleiche: Dictionary für Token Integer Werte

• Vermeide Schleifenkomplexität: Sortiere Tokens für folgenden Intersect

• Tokenization integer conversion sorting• TRUNK {TRU, RUN, UNK} {1, 2, 3}

• TRUNCUS {TRU, RUN, UNC, NCU, CUS} {1, 2, 4, 5, 6}

[1] Hartung et al. Optimizing Similarity Computations for Ontology Matching -Experiences from GOMMA

Aufgabenstellung

• Datensatz (HDFS) -> Flink• Geo Daten: Dbpedia, GeoNames, LinkedGeoData

• Vergleich 3 Ähnlichkeitsmetriken• Simmetrics (library)

• Naive Eigenimplementierung

• Optimierte „Sort-Merge“ Implementierung• Verteiltes Dictionary auf Flink, Alternative?

Large-scale Publikationsanalyse und Geodaten-Visualisierung

Anika Groß

Large-scale Publikationsanalyse und Geodaten-Visualisierung

• Visualisierung der Beziehungen zwischen Arbeitsgruppen in verschiedenen Orten (Ko-Autoren-Beziehung)

• Häufige Topics an einem Standort

• Standorte, mit häufig zitierten Publikationen …

Geographic distribution of affiliations publishing in the top database venues in the last decade

Intra- and cross-country co-operations

Quelle: Aumueller, Rahm: Affiliation analysis of database publications. ACM SIGMOD Record, Vol. 40, No. 1, pp 26-31, March 2011

Microsoft Academic Graph

• Heterogener Graph aus wissenschaftlichen Publikationen• Autoren

• Institutionen

• Journals, Conference venues

• Zitierungsbeziehungen

• Daten als csv• ~27GB (.rar)

http://research.microsoft.com/en-us/projects/mag/

Affiliations FieldsOfStudy PaperAuthorAffiliations

Affiliation ID Field of study ID Paper ID

Affiliation name Field of study name Author ID

Affiliation ID

Authors FieldOfStudyHierarchy Original affiliation name

Author ID Child field of study ID Normalized aff.name

Author name Child field of study level Author sequence nr.

…

Short name (abbr.) Keyword name

Full name JournalsField of study ID mapped to keyword

Journal ID

ConferenceInstances Journal name Papers

Conference series ID Paper ID

Conference instance ID PaperReferences Original paper title

Short name (abbr.) Paper ID Normalized paper title

Full name Paper reference ID Paper publish year

Location Paper publish date

Conference start date PaperUrls Normalized venue name

… Paper ID …

URL Paper rank

Open Streetmap / OpenLayers

• JavaScript API for Open Streetmap

<!DOCTYPE HTML>

<title>OpenLayers Simplest Example</title>

<div id="demoMap" style="height:250px"></div>

<script src="OpenLayers.js"></script>

<script>

map = new OpenLayers.Map("demoMap");

map.addLayer(new OpenLayers.Layer.OSM());

map.zoomToMaxExtent();

</script>

Workflow

Import• Speicherung der CSV-Dateien im HDFS• Laden in Spark

Analysen• Datenaggregation und Analysen mittels Spark,

ggf. Spark GraphX

Visualisierung • Open Street Map, Open Layers

• Material• http://research.microsoft.com/en-us/projects/mag/

• Oder Daten von mir (USB-Stick mitbringen)

• http://spark.apache.org/docs/latest/• http://www.openstreetmap.org• http://wiki.openstreetmap.org/wiki/OpenLayers

Temporale Analyse von News-Daten und Kursentwicklung

Anika Groß

Temporale Analyse von News-Daten und Kursentwicklung

Bild: https://www.quandl.com/collections/markets/bitcoin-data

https://www.google.de/trends/explore#q=Bitcoin

• Welche Auswirkungen hat die Berichterstattung auf die Kursentwicklung?

• Kann mithilfe der Historie eine Prognose erstellt werden, z.B. für aktuelle Ereignisse?

• Am Beispiel von „Bitcoin“

Daten• Google Trends Report für „Bitcoin“

• Pressemittelungen zum Suchbegriff „Bitcoin“• Cryptocoinsnews• Reuters

• Sammeln von Tweets über 4 Wochen

• Kurse• Bitcoin-USD• Bitcoin-Transaction-Number• …

Datenanalyse mit

• Discretized Streams (DStreams)

• Transformations on Dstreams• map, flatMap, filter, reduceByKey…

• Window Operationen• window,

countByWindow, reduceByWindow, …

• MLlib MachineLearning für Streaming Daten• Streaming Linear Regression, …

http://spark.apache.org/docs/latest/streaming-programming-guide.html

WorkflowImport• Speicherung der verschiedenen CSV-Dateien im HDFS• Nutzen der TwitterAPI via SparkStreaming

• Sammeln von Daten für #bitcoin

• Laden der temporalen Daten in SparkStreaming

Analysen• Datenaggregation und Analysen mittels SparkStreaming

• SlidingWindow Analysen…• Streaming Linear Regression, Korrelationsanalyse … (Mllib, SparkR)

Visualisierung • Diagramme, Plots etc.

• Material• https://www.quandl.com/collections/markets/bitcoin-data

• http://spark.apache.org/docs/latest/streaming-programming-guide.html

Graph TopicsMartin Junghanns / Andre Petermann

Extended Property Graph Model• Vertices and directed Edges

41

Extended Property Graph Model• Vertices and directed Edges

• Logical Graphs

42

Extended Property Graph Model• Vertices and directed Edges

• Logical Graphs

• Identifiers

43

1 3

4

5

21 2

3

4

5

1

2

Extended Property Graph Model• Vertices and directed Edges

• Logical Graphs

• Identifiers

• Type Labels

44

1 3

4

5

21 2

3

4

5

Person Band

Person

Person

Band

likes likes

likes

knows

likes

1|Community

2|Community

Extended Property Graph Model• Vertices and directed Edges

• Logical Graphs

• Identifiers

• Type Labels

• Properties (schema-free)

45

1 3

4

5

21 2

3

4

5

Personname : Aliceborn : 1984

Bandname : Metallicafounded : 1981

Personname : Bob

Personname : Eve

Bandname : AC/DCfounded : 1973

likessince : 2014

likessince : 2013

likessince : 2015

knows

likessince : 2014

1|Community|interest:Heavy Metal

2|Community|interest:Hard Rock

Task 1: EPGM CSV Import/Export

Goals Understanding the Extended Property Graph Model Design of a schema-flexible, distributed CSV Import/Export Implementation in Apache Flink / Gradoop Unit Testing

Requirements

Knowledge in Java / Junit / Maven

Frameworks Apache HDFS Apache Flink Gradoop

2 Students

Task 2: Distributed Graph Data Generation

Task 2: Distributed Graph Data Generation

Goals Understanding the „Foodbroker“ Graph Generator

Design of a distributed algorithm

Implementation in Apache Flink / Gradoop

Unit Testing

Requirements

Knowledge in Java / Junit / Maven

Frameworks Apache Flink

Gradoop

2 Students

Task 3: Pattern-dependent Graph Mining

Goals Understanding distributed Frequent Subgraph Mining

Extending an existing FSM kernel (gSpan) by pattern constraints Implementation in Apache Flink / Gradoop Unit Testing

Requirements

Understanding the Frequent Subgraph Mining problem

Knowledge in Java / Junit / Maven

Frameworks Apache Flink Gradoop

2 Students

Problem

Finding subgraphs supported above a given threshold

Transactional Setting

Input is a collection of graphs

Support Based Counting

A subgraph will be considered to be frequent, if a minimum number (threshold) of graphs contain it

Iterative Pattern Growth Approach

Count support of n-edge subgraphs (start n=1), filter by threshold, grow them to n+1-edge subgraphs, repeat until all frequent ones are discovered

50

Task 3: Pattern-dependent Graph Mining

51

Threshold 2/3

Task 3: Pattern-dependent Graph Mining

52

Discover 1-edge subgraphs

Task 3: Pattern-dependent Graph Mining

53

3

1

1

1

1

Count support of 1-edge subgraphs

Task 3: Pattern-dependent Graph Mining

54

3

Identify frequent 1-edge subgraphs

Task 3: Pattern-dependent Graph Mining

55

3

Filter frequent embeddings of 1-edge subgraphs

Task 3: Pattern-dependent Graph Mining

56

3

Grow frequent subgraphs by 1 edge

Task 3: Pattern-dependent Graph Mining

57

3

3

1

1

Count support of 2-edge subgraphs

Task 3: Pattern-dependent Graph Mining

58

3

3

Identify frequent 2-edge subgraphs

Task 3: Pattern-dependent Graph Mining

59

3

3

Continue growing instances until all are infrequent

Task 3: Pattern-dependent Graph Mining

60

Task 3: Pattern-dependent Graph Mining

Maximum frequent subgraph The result may only contain frequent subgraphs

which are not contained in a larger frequent subgraph

Closed frequent subgraph The result may only contain frequent subgraphs which are not

contained in a larger subgraph with the same support

Constrained pattern mining Every frequent subgraph must also satisfy given predicates

(e.g., contain a least one edge with label „knows“)

The predicate must not be applied on the result but used accelerate the mining process

Task 3: Pattern-dependent Graph Mining

Goals Understanding distributed Frequent Subgraph Mining Extending an existing FSM kernel (gSpan) by pattern constraints Implementation in Apache Flink / Gradoop Unit Testing

Requirements

Understanding the Frequent Subgraph Mining problem

Knowledge in Java / Junit / Maven

Frameworks Apache Flink Gradoop

3 Students

ThemenübersichtThema FW #Studenten Betreuer

Recommendation and ML Flink 2 Peukert

Text-Reuse Analysis Gradoop, Flink 2-3 Peukert

Face Recognition, Matching Spark, OpenCV 2-3 Peukert

Privacy Preserving Record Linkage Flink 2-3 Sehili

Entity-Resolution on Flink Flink 2 Christen

Tweet Analyse von News Flink 2 Christen

String Similarity on Flink Flink 2 Nentwig

Large-scale Publikationsanalyse und Geodaten-Visualisierung

Spark, OpenLayers, (GraphX)

2 Groß

Temporale Analyse von News-Daten und Kursentwicklung

SparkStreaming, MLlib 2 Groß

EPGM CSV Import/Export Gradoop, Flink, HDFS 2 Junghanns

Distributed Graph Data Generation Gradoop, Flink 2 Junghanns

Pattern-dependent Graph Mining Gradoop, Flink 3 Petermann