Emanuele Della Valle Irene Celino Daniele Dell’Aglio

•For more information visit http://wiki.larkc.eu/UrbanComputing

The Experience of Realizing a The Experience of Realizing a Semantic Web Urban Computing Semantic Web Urban Computing

ApplicationApplication

http://wiki.larkc.eu/UrbanComputing/ http://wiki.larkc.eu/UrbanComputing/

Emanuele Della Valle Irene Celino Daniele Dell’Aglio DEI – Politecnico di Milano CEFRIEL CEFRIEL [email protected]. [email protected] [email protected]

For more information visit http://wiki.larkc.eu/UrbanComputing

[source IEEE Pervasive Computing,July-September 2007 (Vol. 6, No. 3)]

Introduction

Urban Computing

2Terra Cognita @ ISWC 2009, Washington, USA 26-10-2009

The integration of computing, sensing, and actuation technologies into everyday urban settings and lifestyles.


Introduction

Urban Data Availability

• A large amount of the required information are (or can be made) available on the Internet

– maps (Google,Yahoo!, Wikimapia, OpenStreetMap ),– events scheduled (Eventful, Upcoming…),– voluntarily-provided users location (Google Latitude),– multimedia data with information about location (Flickr,

YouTube, …)– relevant places (schools, bus stops, airports...)– traffic information (accidents, problems of public

transportation...)– city life (job ads, pollution, health care...)



Introduction

Sample Usage Scenario

• A user is in a unknown city and would like to organize a day by visiting some places and attending a music concert

• He therefore needs to:– Find interesting destinations

• Monuments or relevant places• Music or cultural events scheduled for that day

– Understand the most suitable way to reach them

• To solve the problem today, the user would have to use multiple applications, manually check his requirements, manually passing intermediate results from a service to another one



Introduction

Problems in Automating Such Process

1. Lack of single homogenous query language to issue queries with

2. Plurality of the data sources involved in answering even simple queries

3. Heterogeneity of data sources

4. Need for interlinking data spread over various data sources

5. No duplication of several sources may be allowed

6. Data is evolving (e.g., events, friends positions)



Introduction

Our Assumptions

1. Integration of heterogeneous data source can be performed adopting RDF as interchange data format and linking data in sources to popular ontologies

2. Virtual RDF approach can be use to access contents in source without translating the entire source in RDF

3. Up-to-date contents can be found using dedicated search engines

4. Data in different sources can be cross linked

5. User queries can be encoded in SPARQL, but users are not requested to know the location of data

6. SPARQL can be extended to integrate computations that are better performed by dedicated algorithm



Backgrounds

Are Semantic Web Techs up to the Challenge?

• This kind of scenarios, if widely deployed, easily requires reasoning on 1010 triples in 100s ms

• Semantic Web techs are not up to this task (yet)– OWL-DL: 7.8 s reasoning about 4.4*109 triples– RDF-S: 75 ms reasoning about 109 triples



Backgrounds

LarKC project

• LarKC project aims at overcoming current limitation by fusing reasoning with search

• LarKC Platform– a pluggable algorithmic framework to exploit

techniques from databases, machine learning, cognitive science, … and geographic information systems as well

– RDF as internal data representation– SPARQL as language to issue queries– Types of plug-ins: Identifiers, Selectors, Transformers,

Reasoners, and Deciders



DataRequest

Web RetrievedData

PROBLEM: Which Milano

monuments or events can I

quickly get to from here?

PROBLEM: Which Milano

monuments or events can I

quickly get to from here?

StreetsMonumentsEventsData & Tools

PLATFORMSPARQLquery

SPARQLresult

Live Demo of the client application: http://seip.cefriel.it/alpha-Urban-LarKC/ A demonstration video: http://seip.cefriel.it/alpha-Urban-LarKC/alpha-Urban-LarKC-demo.htm

Our experience

Alpha Urban LarKC



Our experience

Data Preparation - Milan Street Topology

• Owned by Agenzia Mobilita, Ambiente e Territorio– http://www.amat-mi.it/

• Available as ESRI shape file• Process we followed to treat it as a virtual RDF graph

– We opened ESRI shape file using PostGIS

– We exported the geographic information in PostgreSQL• Loosing the PostGIS spatial extensions :-/

– We chose to represent data using W3C Geo Positioning RDF vocabulary and our own vocabulary

– We expose the PostgreSQL database using D2R Server and D2RQ as a Virtual RDF graph

– We added back some typical GIS spatial extensions using AllegroGraph spatial extensions



Our experience

Data Preparation – Possible Destinations

• Monuments– DBpedia resources indirectly accessed using Sindice

– Already available as RDF

• Events– Events from Eventful indirectly access using REST API

– Not available as RDF

– Process to map them to RDF on the fly• We chose to represent event using RDF Calendar, Talis Address

schema, W3C Geo and SKOS vocabularies• We wrote an XSLT to transform the proprietary XML schema of

Eventful in RDF• We wrote two LarKC plugins that fetch the events from the REST

service and apply the XSLT transformation



Our experience

Alpha Urban LarKC workflows

• The Alpha Urban LarKC is composed by 3 different workflows:

– monument destinationselection workflow

– event destination selection workflow

– path finding workflow


DataRequest

Web RetrievedData

PLATFORMSPARQLquery

SPARQLresult

StreetsEvents


Our experience

Monument Destination Selection Worflow

• To select monuments in Milano: – a Transformer analyzes the query to get the triple patterns to be

passed to the Identifier – the Identifier queries Sindice to get relevant RDF documents – a Selecter filters the documents to extract information about

relevant monuments and – a Reasoner answers the query



Our experience


• The alpha Urban LarKC is composed by 3 different workflows:





DataRequest

Web RetrievedData

PLATFORMSPARQLquery

SPARQLresult

StreetsEvents


Our experience

Event Selection Workflow

• In order to retrieve events in LarKC we developed a workflow composed by:

– a query Transformer processes the input SPARQL query and extracts location and time information interacting with GeoNames, then

– an Identifier uses the extracted information and it queries Eventful to get a list of events and passes the references to

– a Transformer, which translates the REST service XML response in RDF

– a Selecter passes on all the triples to

– a Reasoner, which answers the query



Our experience


• The alpha Urban LarKC is composed by 3 different workflows:





DataRequest

Web RetrievedData

PLATFORMSPARQLquery

SPARQLresult

StreetsEvents


Our experience

One of the Path Finding Workflow

• Route planning is rapidly developing– Recent algorithms are one million times faster than Dijkstra's algorithm

– Performances improvements are based on a smarter selection of the data subset on which applying standard algorithms

• Just like LarKC ;-)

• We implemented naively a Hierarchical Approach to route planning



• We measured the average response time at increasing number of concurrent requests

• Lesson Learned: response time could be improved if caching mechanisms were implemented

Evaluation

Stress Tests


EVDB server side caching?


Evaluation

Quality Evaluation 1/2

• Errors raised while executing the monument pipeline due to Sindice and DBpedia not answering

• Sindice incomplete results

• Lesson Learned: – Be careful in using 3rd party services

– SLA are required for some of our assumptions to hold

19

Available Milan monuments 25Milan Monuments with coordinates 12Milan Monuments with W3 geo coordinates 6Monuments indexed by Sindice with W3C geo coordinates 2

Terra Cognita @ ISWC 2009, Washington, USA 26-10-2009


Evaluation

Quality Evaluation 2/2

• Analysis of the events retrieved from EVDB for Milan

• Lesson Learned– If contents are voluntarily contributed data quality can be an

issue– Counter measurements should be put in place

• Duplication elimination• Disambiguation of Geographical Identifiers

20

Total UniqueProblems

Wrong coords

Wrong date

Not in Milano

9/5/2009 12 11 9 1 19/6/2009 12 11 9 1 19/7/2009 13 10 8 1 19/8/2009 14 12 11 1 19/9/2009 19 15 11 1 1

9/10/2009 14 11 7 1 09/11/2009 11 9 7 1 2

Terra Cognita @ ISWC 2009, Washington, USA 26-10-2009


Conclusions and Future Works

• Positive feedbacks about using LarKC– Modularity

• easier development process• more parallelizable and controllable

– Plug-ability• easier integration of geo-spatial tools

• Demonstrating Alpha Urban LarKC for any city is next step– Big obstacle: availability of street topology for other cities– Solution: investigate the adoption of OpenStreetMap

exposed as linked data by LinkedGeoData• Key missing component:

– A tools to directly treat GIS as Virtual RDF graphs• GIS2RDF server• Mapping language• GeoSPARQL extension



Much more to come!

22

Keep an eye on http://wiki.larkc.eu/UrbanComputing



Our experience

A Vocabulary for Street Topology in RDF


Classes:• Node• LinkProperties (domain / range):• from (Link / Node)• to (Link / Node)• lat (Node / xsd:Float)• long (Node / xsd:Float)• linkWeight (Link / xsd:Float)

A type Node.B type Node.D type Node.A lat 9.456A long 45.123

l1 type Link.l1 from A.l1 to B.l1 linkWeight 3.l2 type Link.l2 from B.l2 to D.l2 linkWeight 5.

Node definitions

Link definitions

l1

l3

l2

l4

l7

l8

l5 l6

A

B

C D

EF

3m

2m

3m

5m

4m

6m

4m

4m

9.456A

B

l1l2

D

3

5

from

fromto

tolinkWeight

linkWeight

45.123lat long


Our experience

Adding the Notion of Path


Classes:• Node• Link• Path

Properties (domain / range):• from (Link / Node)• to (Link / Node)• lat (Node / xsd:Float)• long (Node / xsd:Float)• linkWeight (Link / xsd:Float)• contain (Path / Link)• pathWeight (Path / xsd:Float)• pathFrom (Path / Node)• pathTo (Path / Node)

The new schema:

A

B

l1l2

D

3

5

from

fromto

tolinkWeight

linkWeight

p

8pathWeight

pathFrom

pathTo

containcontain

9.456

45.123

lat

long


Our experience

Query: SPARQL query to get the path

• Having introduced the notion of Path and counting on a reasoner that can generate paths, the query can be expressed in plain SPARQL

SELECT ?p ?w ?n1 ?l ?n2WHERE{

?p rdf:type Path.?p pathFrom <startingNode>.?p pathTo <endingNode>.?p contain ?l.?l from ?n1.?l to ?n2.?p pathWeight ?w

} ORDER BY ?w



Integrating the GraphProcess and the SPARQL engine results

26NTT DoCoMo Invited speech, 11-3-2009

Input

Converter

Shortest

Path Alg.

Graph Model (RDF)

Start/End points Path(s) (RDF)

GraphProcessor

Output

Converter

RDF Repository

SPARQL Engine

Graph Query

Extractor

Graph Submodel Extractor

query Result set

query

query

Delete Path(s)

Before query processing During query processing After query processing

Emanuele Della Valle Irene Celino Daniele Dell’Aglio

Documents

Transcript of Emanuele Della Valle Irene Celino Daniele Dell’Aglio