Large Scale Computing for Semantic Web Technologies

Large Scale Processing for Semantic Web Technologies

SeminarDr. Harald Sack / Dr. Peter Tröger

Jörg Waitelonis / Magnus Knuth / Nadine LudwigHasso-Plattner-Institut für Softwaresystemtechnik

Universität PotsdamWintersemester 2010/11

Die nichtkommerzielle Vervielfältigung, Verbreitung und Bearbeitung dieser Folien ist zulässig (Lizenzbestimmungen CC-BY-NC).

Dienstag, 19. Oktober 2010

http://creativecommons.org/licenses/by-nc/3.0/deed.de

http://creativecommons.org/licenses/by-nc/3.0/deed.de

1. Dozenten / Tutoren

2. Semantic Web und Linked Data

3. Large Scale Processing im FutureSOC Lab

4. Administratives

Seminar: Large Scale Computing 4 Semantic Web Technologies, Dr. Harald Sack et. al., Hasso-Plattner-Institut, Universität Potsdam

2




Dr. Harald Sack■ seit 1.1.2009 Senior Researcher am HPI und Leiter

der Forschungsgruppe ,Semantische Technologien‘

■ Forschungsschwerpunkte:

□ Semantic Web Technologien

□ Multimedia Retrieval

□ Wissensrepräsentation

■ Videosuchmaschine yovisto.com

3

Large Scale Processing for Semantic Web TechnologiesDozenten / Tutoren



Dr. Peter Tröger

■ Seit Februar 2010 Senior Researcher am HPIim Bereich „Verlässliche Many-Core Systeme“

■ Forschungsschwerpunkte:

□ Verlässliche Systeme, Fehlervorhersage

□ Skalierbare Programmierung paralleler Systeme

■ Intel Single Chip Cloud Computer (SCC)

■ CiteMaster.net

4


MC0

MC1

MC2

MC3

System InterfaceVRC

Router

IA-32 Core0

L2$0256KB

L2$1256KB

IA-32 Core1

MPB16KB

Router Tile

2 core clusters in 6x4 2-D mesh

16B



Dipl. Inform. Jörg Waitelonis

■ Studium Informatik Uni-Jena bis 2006

■ 2006-2007 Exist-Seed Projekt Osotis

■ seit 2007 Gründer von yovisto.com

■ Entwickler von REPLAY (ETH-Zürich)

■ Forschung: Semantic Web, Multimedia-Retrieval, Suchmaschinen Technologien

5




Dipl.-Inf. Nadine Ludwig

■ Studium Informatik TU Ilmenau bis 2005

■ 2005-2010 TU Berlin:

□ kooperative Lernszenarien

□ Integration von Semantic Web Technologien in kooperative Lernplattformen

■ seit 05/2010 HPI:

□ Semantische Analyse, Entity Mapping, Disambiguierung

6




Dipl. Inform. Magnus Knuth

■ Studium Informatik Uni Leipzig bis 2007

■ 2007-2010 Institut für Medizinische Informatik, Statistik und Epidemiologie Leipzig

■ Forschung: Semantic Web, Multimedia-Retrieval, Suchmaschinen Technologien

7




8


Bereitstellung der wissenschaftlichen Präsentation im Internet

yovisto.com• Videosuchmaschine mit dem

Schwerpunkt akademischer Lehrveranstaltungen

• aktuell mehr als 10.000 Vorlesungen und wissenschaftliche Vorträge aus der ganzen Welt

• automatische Segmentierung und Videoanalyse

• benutzergenerierte Co-Annotation

• Social Tagging• Diskussionen• Rezensionen• Wikis• Lernmaterialien

• Zielgenauer Zugriff auf gesuchte Videoinhalte

www.yovisto.com


http://www.yovisto.com

http://www.yovisto.com


9

■ THESEUS Forschungsprogramm: Neue internetbasierte Wissensinfrastruktur.

■ UseCase Contentus: Technologien für die Mediathek der Zukunft.

■ Projekt Mediaglobe: Effizientes Arbeiten mit Mediadaten in Medienarchiven und Rundfunkanstalten.

■ effiziente Suche nach/in AV-Inhalten in Medienarchiven und Rundfunkanstalten

■ Arbeitsprozesslösung für die effiziente Erfassung, Aufbereitung und Verwertung von AV-Inhalten






4. Administratives


10




11

The Web is huge....

To be more precise, the WWW is rather huge...•more than 25 x 109 documents in

Search engine indexes (TNL Blog: Google has 24 billion items index, considers MSN search nearest competitor, September 2005)

•Google Web Crawler found more than 1012 documents(The Official Google Blog: We knew the Web was Big....., Juli 25, 2008)

•New Google Search Index Caffeine comprises 100 Million Gigabytes of datai.e. 1017 Byte (SMX Video: Google’s Matt Cutts On Caffeine Launch, June 9, 2010,http://searchengineland.com/smx-video-googles-matt-cutts-on-caffeine-launch-43933)

•And then, there is also the DeepWeb (Darkweb) ...and it is supposed to be up to 500 time larger than the Surface Web(Bergman, 2001)


http://www.tnl.net/blog/2005/09/27/google-has-24-billion-items-index-considers-msn-search-nearest-competitor/




http://googleblog.blogspot.com/2008/07/we-knew-web-was-big.html

http://googleblog.blogspot.com/2008/07/we-knew-web-was-big.html


12

The Web is growing...

Multimedia, Real-Time Data, Sensor Data, ....

in 06/2010: 7 TB/day

in 05/2010: •24 h of video upload / minute•2 billion streamed videos per day

in 06/2010: 7 TB/dayDienstag, 19. Oktober 2010


12

The Web is growing...

Multimedia, Real-Time Data, Sensor Data, ....

in 06/2010: 7 TB/day

in 05/2010: •24 h of video upload / minute•2 billion streamed videos per day

in 06/2010: 7 TB/dayDienstag, 19. Oktober 2010


13

How to find something on the Web?



14

The ‘Web of Data‘

Semantic Web Technologies

• Interoperable and machine understandabledata semantics

• Based on formal knowledge representations

• Creating a ‘Web of Data‘



15

Semantic Web and Linked Data

From World Wide Web to Web of Data„The Web was designed as an information space, with the goal that it should be useful not only for human-human communication, but also that machines would be able to participate and help… “

Prerequisites:

• Content can be read and interpreted correctly (=understood) by machines

Tim Berners-Lee, Semantic Web Roadmap, Sept 1998

Semantic Web• (natural language) web content is

explicitely annotated with semantic metadata

• semantic metadata encode the meaning (semantics) of web content and can be read andinterpreted correctly my machine

Natural Language Processing• Technology from traditional Information

Retrieval (WWW Search Engines)



16


Understanding Web Content - I





16







16





?...

?

text: „FAB“

fabulous

Entity MappingDisambiguation

?



16





Fabio CapelloManager ofUK National

Football Team

?...

?

text: „FAB“

fabulous


?



16





Fabio CapelloManager ofUK National

Football Team

?...

?

text: „FAB“

fabulous


?

David JamesGoal Keeper of

UK NationalFootball Team



17


Understanding Web Content - II

text: „FAB“

Fabio Capello

Entity Mapping



17



text: „FAB“

Fabio Capello

Entity Mapping

Soccer Manager

is a



17



text: „FAB“

Fabio Capello

Entity Mapping

Soccer Manager

is a

Person

is a



18


Understanding Web Content - III

Fabio Capello (entity)



18




Soccer Manager

is a

(class)

Class-membership has type



18




Soccer Manager

is a

(class)

Class-membership has type

Person

is a

(class)

superclass

subclass

is subclass of



19


Understanding Web Content - IV

Fabio Capello

Soccer Manager

Person

is a

is aEntities

Classes



19



Fabio Capello

Soccer Manager

Person

is a

PlacehasBirthPlace

is aEntities

Classes



19



Fabio Capello

Soccer Manager

Person

is a

PlacehasBirthPlaceDate hasBirthDate

is aEntities

Classes



19



Fabio Capello

Soccer Manager

Person

is a


is a

hasBirthDate1946-06-18

is a

Entities

Classes



19



Fabio Capello

Soccer Manager

Person

is a


is a


is a

San Canzian d‘IsonzohasBirthPlace

is a

Entities

Classes



20




21


Fabio Capello http://dbpedia.org/resource/Fabio_Capello

URI - Uniform Resource Identifier


http://dbpedia.org/page/Fabio_Capello



22


http://dbpedia.org/resource/Fabio_Capello

http://en.wikipediapedia.org/resource/Fabio_Capello







23

Semantic Web and Linked Datahttp://dbpedia.org/resource/Fabio_Capello





24


http://dbpedia.org/resource/Fabio_Capello

RDF Resource Description Framework

:Fabio_Capello dbpp:birthPlace :San_Canzian_d%27Isonzo .:Fabio_Capello dbpp:birthDate “1946-06-18“ .:Fabio_Capello rdfs:type dbpo:SoccerManager .:Fabio_Capello rdfs:type dbpo:Person ....

:Fabio_Capello rdf:type dbpo:SoccerManager .

RDF Tripel RDF Subject RDF Property RDF Object





25


http://dbpedia.org/ontology/soccer_manager

dbpo:SoccerManager rdf:type owl:class .dbpo:SoccerManager rdfs:subClassOf dbpo:Person .dbpo:SoccerManager rdfs:label “Soccer Manager“ .dbpp:birthPlace rdf:type rdf:Property .dbpp:birthPlace rdfs:domain dbpo:Person .dbpp:birthPlace rdfs:range dbpo:Place .dbpp:birthDate rdf:type rdf:Property .dbpp:birthDate rdfs:domain :Person .dbpp:birthDate rdfs:range xsd:date ....

RDF Schema

Person PlacehasBirthPlaceDate hasBirthDate

Soccer Manager

is a





26

Semantic Web and Linked DataUnderstanding Web Content - V

Fabio Capello

LivingPeople

PersonDate


hasBirthDate

is a

is a

is a

DeadPeople∩ =∅

logical constraint

is a

+ Rules (Description Logics)

∀x.∃y.hasDeathDate(x,y) ∧ Person(x) ∧ Date(y) → DeadPeople(x)



27


SELECT DISTINCT ?l ?l2 ?g FROM <http://dbpedia.org> WHERE { ?s dbpp:nationalteam ?o . ?s rdfs:label?l FILTER langMatches( lang(?l), "EN" ) . ?s dbpp:nationalgoals ?g FILTER(?g>10). ?s dbprop:nationalteam ?nat . ?nat rdfs:label ?l2 FILTER langMatches( lang(?l2), "EN" ).} ORDER BY DESC(?g)

Select all players of a soccer nationalteam that have scored more than 10 goals while inthe team


http://dbpedia.org

http://dbpedia.org

http://dbpedia.org/property/nationalteam

http://dbpedia.org/property/nationalteam


28


Select all players of a soccer nationalteam that have scored more than 10 goals while in the team



29


(RDF)

(URI)

M.Hausenblas, Quick Linked Data Introduction, http://www.slideshare.net/mediasemanticweb/quick-linked-data-introduction

Linked Data■ Term was originally coined by Tim Berners-Lee

(Tim Berners-Lee, Linked Data, 2006, http://www.w3.org/DesignIssues/LinkedData.html)

The Web of data is abouta dataand namingmodel on the Web


http://www.w3.org/DesignIssues/LinkedData.html

http://www.w3.org/DesignIssues/LinkedData.html


30


Linked Data

■ Technical Principles

□ use URIs to identify things uniquely (not only documents...)

□ use HTTP URIs (URLs) so that these things can be referred to and looked up ("dereferenced") by people and user agents

□ use RDF as an universal data model to provide useful information about these things

□ include links to other, related URIs in the exposed data to improve discovery of other related information on the Web.


http://en.wikipedia.org/wiki/Dereferenceable_Uniform_Resource_Identifier

http://en.wikipedia.org/wiki/Dereferenceable_Uniform_Resource_Identifier

http://en.wikipedia.org/wiki/User_agents




31


Linked Data□ The application lf the Linked Data principles leads to the creation of a

,Web of Data‘



32


Linking Open Data■ Public available structured data should be published as Linked Data

■ Various data sources should be interlinked

LOD-WikiPage: http://esw.w3.org/topic/SweoIG/TaskForces/CommunityProjects/LinkingOpenData/


http://esw.w3.org/topic/SweoIG/TaskForces/CommunityProjects/LinkingOpenData/

http://esw.w3.org/topic/SweoIG/TaskForces/CommunityProjects/LinkingOpenData/

Linked Data Challenges■ Coherence

relatively few, expensively maintained links

■ Qualitypartly low quality data and inconsistencies

■ Performancestill substantial penalties compared torelational database technologies

■ Data consumptionlarge scale processing, schema mapping anddata fusion still in its infancy

■ UsabilityMissing direct end user tools and network effect


33


Sören Auer:"Linked Data: Now what?"ESWC2010 Panel Discussion



34

Problems and Experiments



35




36


A. Hoigan et al: Weaving the Pedantic Web, LDOW 2010



37


Experiment Summary (1) Crawling the Semantic Web

(2) Structural Analysis

(3) Content-based Analysis

(4) Data Cleansing

(5) Augmenting Semantic Web Infrastructure



38


So what? ■ Interesting Facts to find out about

Semantic Web & Linked Data

■How big is the Semantic Universe?

■ # tripel

■ # documents

■ # interlinking

■ Linking Open Data is only registered vocabulary/data in the LOD-Wiki→ 14b RDF triples

■What else is out there ... and how much of it?

■ ...and how do we get it?



39


(1) Crawling the Semantic Web■Of course we are not the first to be out there...

■ SwoogleLi Ding et al: Finding and Ranking Knowledge on the Semantic Web, ISWC 2005.

■ Scutter/Slug Leigh Dodds: Slug: A Semantic Web Crawler, 2006

■ Sindice Giovanni Tumarello et al: Sindice.com - weaving the open linked data, ISWC 2007

→ 2.1b RDF triples

■ SWSE Andreas Harth et al: SWSE: Objects before Documents,

Semantic Web Challenge 2008, ISWC 2008


■ FalconsG.Cheng et al.:Falcons: Searching and Browsing Entities on the Semantic Web, WWW17 2008.




40


(2) Analyzing the Semantic Web I - Structural Analysis■ Again we are not the first to be out there...

■ Structural Analysis of the ,early‘ WWW

IN44m nodes

SCC56m nodes

OUT44m nodes

unconnected components

unconnected components

tunnels

appendices

appendices

A. Broder et al.: Graph structure in the Web. In Comput. Netw. 33, 1-6 (Jun. 2000), 309-320.



41


(2) Analyzing the Semantic Web I - Structural Analysis■ Again we are not the first to be there...

■ Structural Analysis of the ,early‘ Semantic Web

Weiyi Ge et al.: Object Link Structure in the Semantic Web, ESWC 2010

■ Experimental Setup

■ 18m RDF documents (Falcons crawl 2009)

■ 110m nodes with 190m edges■ Analysis of RDF link graph

■ average node degree: ≈3.4

■ effective diameter: ≈11.5

■ Largest connected component: ≈88% of all nodes



42


(3) Analyzing the Semantic Web II - Content-Based Analysis■ Again we are not the first to be there...

http://pedantic-web.org/

A. Hoigan et al: Weaving the Pedantic Web, LDOW 2010

■ 150k documents with more than 12m RDF triples

■ Discovered categories of symptoms:

■ incomplete → dead links

■ incoherent → no correct interpretation (local)

■ hijack → no correct interpretation (remote)

■ inconsistent → contradictions


http://pedantic-web.org

http://pedantic-web.org


43



Urbani et al: OWL Reasoning with WebPIE: Calculating the Closure of 100 Billion Triples, ESWC 2010■ Artificial Benchmark dataset used

Leigh University Benchmark (LUBM) with 100b RDF triples

■ Computing the transitive closure (= reasoning)

■ Making implicit knowledge explicit

Fabio Capello San Canzian d‘IsonzohasBirthPlace



43







Fabio Capello

Person

is a




43







Fabio Capello

Person

is a

PlacehasBirthPlace




43







Fabio Capello

Person

is a

PlacehasBirthPlace


class membershipcan be deduced



44


(4) Analyzing the Semantic Web III - Data Cleansing■ trying to clean out Linked Open Data and possibly also (partially) the

Semantic Web...

(1) Identify inconsistencies and ambiguities by (automated) content-based analysis

(2)Solve inconsistencies & ambiguities

■ if possible by reasoning

■ else by crowdsourcing (game-based evaluation, etc.)

Cleaning out the Augean stables...AUGEAN-STABLES: Extremely nasty and smelly warehouses of filth, straw and manure



45


(5) Semantic Web Infrastructure - Tripel Stores■ RDF(S) Data is stored in Triple Stores

■ Basic idea:

■ Use 1 table with 3 columns (s,p,o)

■ For every row / row combinationcreate index structures for fast access(spo, sop, pos, pso, ops, osp)

■ Drawback: many self-joins needed(memory consumption)



46


Experiment Summary (1) Crawling the Semantic Web

(2) Structural Analysis

(3) Content-based Analysis

(4) Data Cleansing

(5) Augmenting Semantic Web Infrastructure





4. Administratives


47




48


„Large Scale“ Processing for Semantic Web Technologies■ Three ways of doing anything faster [Pfister]

■Work harder

■Work smarter

■Get help

■ „A parallel computer is a set of processors that are able to work cooperatively to solve a computational problem.“ (Foster 1995)

■ Linear speedup: n times more resources lead to n times less time for solving the same task

■ Linear scaleup: n times more resources solve an n times larger problem in the same time

CPU 1, Node 1

CPU 2, Node 1

CPU 3, Node 1

CPU 4, Node 2

CPU 5, Node 2

CPU 6, Node 2Sca

ling

Up

Scaling Out



49


FutureSOC Lab■Collaboration with industry for software research on next-generation

X86 hardware

■Hewlett Packard DL980 G7: 8 x X7560 (8 Cores), 2048 GB RAM

■ Fujitsu RX600 S5 1: 4 x E7530 (6 Cores), 256 GB RAM

■ Fujitsu RX600 S5 2: 4x X7550 (8 Cores), 1024 GB RAM

■ Fujitsu RX200 S5 1: 2x E5540 (4 Cores), 36 GB RAM

■ Fujitsu RX300 S5 1: 1x E5540 (4 Cores), 12 GB RAM



50


FutureSOC Lab■ Large scale processing of semantic web data:

■ Speeding up the processing of single work items through parallelization

■ Scaling up the number of processed triplets through distribution

■ Seminar participants will work on parallelization strategies for semantic web processing, practically tested on FutureSOC hardware

■ Parallelized XML parsers

■ Parallelized graph processing

■ I/O - optimized web crawling

■ Speed-up and scale-up of triplet stores




The Problem of Speedup through Parallelization■Well-researched problem in parallel databases (D. DeWitt, J. Gray)

□ Start-Up: Initialization of parallel activity, synchronization of results

□ Interference: Conflicts through access to shared data

□ Dispersion: Overal execution time depends on the slowest process

□ All problems increase with the number of processors

■Amdahls Law

□ P is the portion of the program that benefits from parallelization

□ Maximum speedup by N processors:

□ Maximum speedup tends to 1 / (1-P)□ Parallelism only useful with small amount

of processors or small (1-P)

51

s = (1−P )+P(1−P )+ P

N


1 10 100 1000 1!104

5

10

15

20

P=90%

P=75%

P=50%

P=25%

P=10%

Number of processors

Speedup P=95%


Problems and Experiments52 Amdahl‘s Law





4. Administratives


53




54 Seminar Large Scale Processing for Semantic Web Technologies□Semesterwochenstunden: 4

□ECTS: 6

□Leistungsfeststellung:

□Schriftliche Ausarbeitung zum Vortragsthema (Umfang ca. 20 Seiten)□Umsetzung einer vorgegebenen Implementierungsaufgabe im Team□Präsentation der Ergebnisse

(Zwischenpräsentation, Endpräsentation, Wochenbesprechungen)

□Projektteams mit je 2-3 Studenten bearbeiten eine der vorgeschlagenen Aufgabenstellungen

Large Scale Processing for Semantic Web TechnologiesAdministratives



Administratives■Termine:

□Wöchentliches Seminargruppentreffen

□Termin nach Vereinbarung

□Zwischenpräsentation der Projektergebnisse

□Abschlusspräsentation der Ergebnisse

□Termin in der letzten Semesterwoche

55




56

Literatur

• P. Hitzler, S. Roschke, Y. Sure: Semantic Web Grundlagen, Springer, 2007.

• Grundlegende Materialien via bibsonomy-Bookmarks

• http://www.bibsonomy.org/user/lysander07/lsc1011



http://www.bibsonomy.org/user/lysander07/sw0809-08

http://www.bibsonomy.org/user/lysander07/sw0809-08

Date post:	10-Feb-2017
Category:	Technology
Upload:	harald-sack
View:	480 times
Download:	1 times