Rousset EID06

Information about Rousset EID06

Published on October 19, 2007

Author: Breezy

Source: authorstream.com

Content

Building scalable semantic PDMS: the SomeWhere approach. :  Building scalable semantic PDMS: the SomeWhere approach. Marie-Christine Rousset Joint work with Philippe Adjiman, Philippe Chatalic, François Goasdoué, Gia-Hien Nguyen, Laurent Simon How to make semantic approaches scalable to the web ?:  How to make semantic approaches scalable to the web ? A data centered vision of the Semantic Web viewed as a huge semantic and distributed data management system SomeWhere a peer to peer infrastructure based on simple personalized ontologies and mappings distributed at large scale Focus of this talk P2P Data Management Systems:  P2P Data Management Systems Logical network of peers (≠ physical network) each peer is characterized by its physical address (IP) a description of the stored resources its neighbors in the network the peers to which it can transmit messages (queries,...) Various topologies random and dynamic (Gnutella) fixed (Chord, Hypercube) guided by the semantics SON, Edutella, Piazza, DRAGO, coDB, Somewhere SomeWhere logical networks:  SomeWhere logical networks The topology is not fixed Guided by mappings A peer joins by declaring mappings between its ontology and the ontologies of some peers that it knows leaves by removing the mappings with its acquaintances in the network SomeWhere in a nutshell:  SomeWhere in a nutshell Simple data model based on a propositional language of classes for defining ontologies, mappings, and queries a sublanguage of OWL DL (W3C) Scales up to one thousand peers logical network : « small world » SomeWhere Data Model:  SomeWhere Data Model Data Data Schema+Data SomeWhere Data Model :  SomeWhere Data Model Semantics:  Semantics Standard FO logical semantics one single domain of interpretation a distributed set of formulas interpreted in the same way as if they were not distributed in contrast with some other approaches coDB: epistemic logic DRAGO: distributed semantics of DDL or DFOL based on a collection of domains of interpretations Our assumption: the objects have a unique URI objects stored at different peers and having the same URI are interpreted as being the same Data model: example :  Data model: example Musique Rock Pop Classique Français US St_pop Tchaikovsky St_Français St_US St_Tchaikovsky Mouv Rock P1 P2 Query answering : illustration:  Query answering : illustration Musique Rock Pop Classique Français US St_pop Tchaikovsky St_Français St_US St_Tchaikovsky Music Pop_Rock Classical St_Pop_Rock St_Ru Tchai St_Tchai Ru It St_Pop_Rock Rewritings St_US St_Français St_Mouv St_Pop St_Pop St_Français St_Mouv St_Pop St_US St_Pop P1 P2 Query answering in SomeWhere:  Query answering in SomeWhere Decomposition of queries/recombination of answers only atomic queries are transmitted to peers a complex query is splitted into atomic queries each solicited peer processes a given atomic query q and incrementally sends back intentional answers for it (conjunction of) extensional classes that are rewritings of q intentional answers of different atomic queries resulting from the split of a complex query must be recombined intentional answers can combine extensional classes of different peers Can be reduced to a consequence finding problem in distributed clausal propositional theories Ontologies and mappings are encoded as clauses The maximal conjunctive rewritings of a conjunctive query Q correspond exactly to the negation of the clauses that are proper prime implicates of the negation of Q w.r.t the union of the local theories and the mappings Query answering algorithm:  Query answering algorithm Message based local algorithm running on each peer query, answer, and termination messages Global properties soundness completeness termination (even for cyclic networks) Slide13:  extension Flash demo of the SomeWhere http://www.lri.fr/~adjiman/somewhere/ Slide15:  BenStiller Comedy Friends Humor Classes extensions Slide16:  Friends Humor Action Suspense Thriller BenStiller Comedy Slide17:  BenStiller Comedy Friends Humor Action Suspense Thriller Slide18:  P3:Thriller P1:Action P1:Suspence P5:Drama P6:DramaComedy P2:BruceWillis P1:Suspense Rewritings of Thriller: evaluation Local Integration SomeWhere infrastructure:  SomeWhere infrastructure SomeWhere infrastructure:  SomeWhere infrastructure Zoom on one machine 100 % JAVA 1.5 somewhere.jar ~ 250 Ko Scalability experiments [IJCAI 05]:  Scalability experiments [IJCAI 05] on randomly generated networks 1000 peers deployed on a cluster of 75 machines small world topology Close to the topology of the web peers ontologies random clauses of length 2 mappings random clauses of length 2 or 3 Slide22:  Varying topologies P: probability of redirecting an edge Model of Watts and Strogatz Scalability results:  Scalability results Varying parameters Number of mappings between peers complexity of mappings ratio of clauses of length 3 (0%, 20%, 100%) timeout : 30 s/query Depth of query processing Small depth (less than 7) even on the hard cases Time to produce a number of answers In 90% cases, the first answer is produced within 2 seconds Easy cases (simple mappings): few answers per query (5 on average) very fast (less than 0.1s) to compute all the answers without timeouts Hard cases (complex and more mappings per edge) around 1000 answers per query (but > 30% queries not complete : timeouts) quite fast to obtain them (less than 20s) Ongoing work (1):  Ongoing work (1) Extending the data model to RDF(S) W3C recommendation for describing web resources Classes and (binary) relations between objects each object is identified by a URI Triple notation: <resource, property, value> Relational notation: property(resource, value) RDFS:  RDFS SomeRDFS: data model :  SomeRDFS: data model a simple fragment of RDFS distributed through simple mappings (using the same constructors) Query rewriting:  Query rewriting Propositionalisation of RDFS statements Query rewriting using SomeWhere C1dom  C2dom C1range  C2range P1rel  P2rel Prel  Cdom Prel  Crange illustration:  illustration Q(X,Y): P2.Work(X)P2.refersTo(X,Y) illustration:  illustration Q(X,Y): P2.Work(X)P2.refersTo(X,Y) Ongoing work (2):  Ongoing work (2) Handling inconsistencies how to define them ? insatisfiability (no model) => inconsistency not a necessary condition how to check consistency? at each join of a new peer how to deal with inconsistency? correct it or reason with it ? for each A, there exists a model in which A is non empty: S | A illustration:  illustration path m1: AIPubli is a subclass of Conf. inconsistencies are caused by mappings. Article Theory Expe P2 path m0 -> m2: AIPublic is a subclass of Journal. Conf and Journal are disjoint, therefore AIPUbli is necessarily empty P1 P2P detecting of inconsistencies:  P2P detecting of inconsistencies Propagation of m1: { ¬AIPubli v Conf; ¬AIPubli v Publi; ¬AIPubli v ¬Journal; ¬BDPubli v Conf; ¬BDPubli v Publi; ¬BDPubli v ¬Journal }. No production of unit clause No inconsistency Propagation of m2: { ¬Theory v Journal; ¬AIPubli v Journal; …..; ¬AIPubli ; …; ¬AIPubli v ¬Conf}. Production of a unit clause Inconsistency {m1,m2} is a NoGood stored at P3 ¬Conf v Publi ¬Journal v Publi ¬Journal v ¬Conf ¬AIPubli v 2005 ¬BDPubli v 2005 ¬Theory v Article ¬Expe v Article ¬AIPubli v Theory Distributed storage of the NoGoods:  Distributed storage of the NoGoods Slide34:  Principle: avoid the inconsistencies when constructing answers Semantics of « well-founded » answer: obtained from a consistent subset of formulas Algorithm: for each answer, build its set of mapping supports and return the set of NoGoods encountered during the reasoning, discard the mapping supports including a NoGood return the answers having a not empty set of mapping supports P2P well-founded reasoning It will be presented in more details at ECAI 06 Perspectives:  Perspectives Coupling SomeWhere to a DHT for optimizing lookup queries Adapting the SomeWhere algorithm to support the epistemic semantics Modeling and handling trust in P2P Semantic overlay networks based on a logical approach P2P discovery and composition of smart devices based on a semantic description of the functionality, inputs and outputs of devices

Related presentations


Other presentations created by Breezy

Plant Anatomy
03. 01. 2008
0 views

Plant Anatomy

Learning Long Division
15. 06. 2007
0 views

Learning Long Division

ADO Net
24. 10. 2007
0 views

ADO Net

Ch 2 Chemistry of Life
05. 01. 2008
0 views

Ch 2 Chemistry of Life

REORGANIZATION
27. 09. 2007
0 views

REORGANIZATION

Enhanced Fujita Scale 6 23 04
05. 10. 2007
0 views

Enhanced Fujita Scale 6 23 04

severe convection punkka
07. 10. 2007
0 views

severe convection punkka

lsad07 psp
09. 10. 2007
0 views

lsad07 psp

idioms1
10. 10. 2007
0 views

idioms1

SabadosCiencia2006
13. 10. 2007
0 views

SabadosCiencia2006

TheodoreRoosevelt
22. 10. 2007
0 views

TheodoreRoosevelt

Timss
17. 10. 2007
0 views

Timss

Wynn ASA 2000
04. 10. 2007
0 views

Wynn ASA 2000

aas strom
29. 08. 2007
0 views

aas strom

element connections
29. 08. 2007
0 views

element connections

hwr clustering
29. 08. 2007
0 views

hwr clustering

Pov map 20060717 1
29. 11. 2007
0 views

Pov map 20060717 1

CONSTRUCTING BUD VASES ADN BOWS
11. 12. 2007
0 views

CONSTRUCTING BUD VASES ADN BOWS

nobel talk
15. 10. 2007
0 views

nobel talk

18 FOSIS
24. 10. 2007
0 views

18 FOSIS

Lec 08 FO1 06 Urbanisation
01. 11. 2007
0 views

Lec 08 FO1 06 Urbanisation

America vs The World
22. 10. 2007
0 views

America vs The World

Vasco Da Gama Slide Show
07. 11. 2007
0 views

Vasco Da Gama Slide Show

Fliess
15. 11. 2007
0 views

Fliess

01 threat
19. 11. 2007
0 views

01 threat

Konsolen
21. 11. 2007
0 views

Konsolen

the dancers
23. 11. 2007
0 views

the dancers

Probil
26. 11. 2007
0 views

Probil

UNE Benz
27. 11. 2007
0 views

UNE Benz

Galaxies
29. 08. 2007
0 views

Galaxies

DB2 XML DatabaseFINAL
23. 10. 2007
0 views

DB2 XML DatabaseFINAL

akzonobel
15. 10. 2007
0 views

akzonobel

ilana
29. 08. 2007
0 views

ilana

lauter
07. 11. 2007
0 views

lauter

GradSch GPOs
04. 10. 2007
0 views

GradSch GPOs

PHYS402 01
16. 10. 2007
0 views

PHYS402 01

cry beloved
02. 08. 2007
0 views

cry beloved

curtis
02. 08. 2007
0 views

curtis

Chaplet of Divine Mercy
02. 08. 2007
0 views

Chaplet of Divine Mercy

CS583 opinion mining
02. 08. 2007
0 views

CS583 opinion mining

A TIME FOR ANDREW Pres 2
02. 08. 2007
0 views

A TIME FOR ANDREW Pres 2

arthur powerpoint 11 20 03
02. 08. 2007
0 views

arthur powerpoint 11 20 03

cheryl toner ific
02. 08. 2007
0 views

cheryl toner ific

bats
02. 08. 2007
0 views

bats

23 stavros thurs
02. 08. 2007
0 views

23 stavros thurs

aas04 jeff
29. 08. 2007
0 views

aas04 jeff

moustakis
29. 08. 2007
0 views

moustakis

irsurveys07
29. 08. 2007
0 views

irsurveys07

venice oct03
29. 08. 2007
0 views

venice oct03

Office of Homeleand Security
29. 10. 2007
0 views

Office of Homeleand Security

agn presentation 102106
29. 08. 2007
0 views

agn presentation 102106

ReginaSchulteLadbeck 042104
29. 08. 2007
0 views

ReginaSchulteLadbeck 042104

Weingarten
03. 01. 2008
0 views

Weingarten

Presentation NASDAQ
24. 02. 2008
0 views

Presentation NASDAQ

nov retail ebony
24. 02. 2008
0 views

nov retail ebony

APAsymp04AIDMAN
02. 08. 2007
0 views

APAsymp04AIDMAN

Ray Flores Roadmap
04. 03. 2008
0 views

Ray Flores Roadmap

Beloved
02. 08. 2007
0 views

Beloved

2004 4050S1 11 Levin
02. 08. 2007
0 views

2004 4050S1 11 Levin

Konstantinidis
29. 09. 2007
0 views

Konstantinidis

Qin and Han Dynasties
25. 03. 2008
0 views

Qin and Han Dynasties

andy powell presentation
02. 08. 2007
0 views

andy powell presentation

arena rome minier
13. 11. 2007
0 views

arena rome minier

Presentation010605
10. 04. 2008
0 views

Presentation010605

03edclark lecture
13. 04. 2008
0 views

03edclark lecture

richard mushotzky
29. 08. 2007
0 views

richard mushotzky

Lawrence D Boston 2006
14. 04. 2008
0 views

Lawrence D Boston 2006

DMCH13
16. 04. 2008
0 views

DMCH13

ERates
17. 04. 2008
0 views

ERates

JHAN 14
18. 04. 2008
0 views

JHAN 14

4884061 firstfileFILE
22. 04. 2008
0 views

4884061 firstfileFILE

ppt26
23. 12. 2007
0 views

ppt26

Operations
28. 04. 2008
0 views

Operations

CH10 Outline
07. 04. 2008
0 views

CH10 Outline

CIM research
30. 04. 2008
0 views

CIM research

komossa
29. 08. 2007
0 views

komossa

ieee sp 2004
18. 06. 2007
0 views

ieee sp 2004

icws 2006 3
18. 06. 2007
0 views

icws 2006 3

ICTP intro
18. 06. 2007
0 views

ICTP intro

human mating beh 2005
18. 06. 2007
0 views

human mating beh 2005

IMDS CIESP
14. 11. 2007
0 views

IMDS CIESP

welch adv camp july05
02. 10. 2007
0 views

welch adv camp july05

Glycosylation
15. 06. 2007
0 views

Glycosylation

Making a Story Board
15. 06. 2007
0 views

Making a Story Board

Story Literary Elements
15. 06. 2007
0 views

Story Literary Elements

Life Cycle of Plants and Animals
15. 06. 2007
0 views

Life Cycle of Plants and Animals

Session1Alila
02. 11. 2007
0 views

Session1Alila

beetleborers
02. 01. 2008
0 views

beetleborers

2006 IADB
10. 10. 2007
0 views

2006 IADB

robo wk1
03. 01. 2008
0 views

robo wk1

Rosemary Panama
22. 10. 2007
0 views

Rosemary Panama

ec06nicapan
25. 10. 2007
0 views

ec06nicapan

Allies Pre Training Module
02. 08. 2007
0 views

Allies Pre Training Module

Carmona
30. 12. 2007
0 views

Carmona

TheSuccessofSingapor e2006
27. 03. 2008
0 views

TheSuccessofSingapor e2006

Advisory Board Presentation
02. 08. 2007
0 views

Advisory Board Presentation

Cameron SAS44 A Century of OA
27. 02. 2008
0 views

Cameron SAS44 A Century of OA

dubrovnik
16. 10. 2007
0 views

dubrovnik

sprfett
07. 01. 2008
0 views

sprfett

mccune albright syndrome
15. 10. 2007
0 views

mccune albright syndrome

michael soendermann 2007
18. 10. 2007
0 views

michael soendermann 2007

astro12Summer12
29. 08. 2007
0 views

astro12Summer12

familyweek1
19. 02. 2008
0 views

familyweek1