Experimental Evaluation

Introduction

This page contains information about benchmarking our spatial OQA (Ontology-Mediated Query Answering) system for mobility streams. Mobility streams are integrated by an approach called Local Dynamic Map (LDM), which is a standardized integration plattform for spatial and stream data in Cooperative Intelligent Transport Systems (ITS) .

Input

The following elements make the input for the experiments:

PipelineDB as the stream database supporting standard and stream relations (as tables or views);
The LDM ontology figures as the integration schema, where the concepts/roles are directly mapped to the relations;
Four groups of instance data which ranges from POIs extreacted out of OSM (e.g., parkings), to the (spatial) topology of the intersections, different types of vehicles (e.g., cars, bikes, etc.), and stream instance data generated by the vehicle movement (e.g., speed and position);
A set of queries, which represent real life use cases taken from the ITS domain. The queries range from simple single join to complex, mixed spatial-stream queries.

Ontology (TBox)

Our LDM ontology models in OWL 2 QL an LDM and ITS domain using a layered approach, separating bewtween the concepts (aka classes): ITS features (e.g., intersection topology), geo features (e.g., POIs), geometrical representations (e.g., polygon), actors (e.g., vehicles), events (e.g., accident); and roles: (aka properties) partonomies (e.g., isPartOf), spatial relations (e.g., intersects), connectivity (e.g., connectedTo), and generic roles (e.g., speed).

Database

The PipelineDB instance is split into three separate parts:

The static database includes the static ABox (e.g., vehicles, intersections, etc.) and TBox (e.g., concept inclusions);
The spatial database is a direct import of OSM instances using Osm2pgsql with the main tables planet_osm_point for POIs and planet_osm_line for streets;
The stream database uses functionality of PipelineDB's, i.e., Streams and Continuous Views. We modeled the database in a way, that there is a one-to-one mapping from streams → continuous views → TBox concepts/roles:
- stream_speed (iid integer, x integer) → v_speed → ldm:speed
- stream_pos (iid integer, x text) → v_pos → ldm:pos
- stream_signalstate (iid integer, x text) → v_signalstate → ldm:hasSignalState
The continous views are created as follows: CREATE OR REPLACE VIEW v_speed AS SELECT iid, x FROM ONLY stream_speed, etc.

Instances (ABox)

Tbd.

Queries

The following queries represent the input for the experimens and are described below:

q1(x, y) : MAPIntersection(x), hasGeo(x, u), near(u, v), hasGeo(y, v), Parking(y).
q2(x, z) : Vehicle(x), speed(x, y)[avg, 10], y > 30, vehicleMaker(x, z).
q3(x, v) : Vehicle(x), pos(x, y)[line, 10], inside(y, u), hasGeo(v, u), LineIn(v).
q4(x, y) : Vehicle(x), pos(x, y)[line, 10], overlap(y, z), pos(y, z)[line, 10], Bus(y), x != y.
q5(x, y) : MAPLineIn(x), hasSignal(x, y), MAPSignalGroup(y), hasState(y, z)[last, 15], z = 'R'.
q6(x, y) : MAPLineIn(x), hasGeo(x, u), intersects(u, v), pos(y, v)[line,10], Vehicle(y), speed(y, r)[avg,10], r > 30, hasSignalGroup(x, z), MAPSignalGroup(z), signalState(z, t)[last,15], t = 'R', isPartOf(x, w), MAPIntersection(w), w = 'I1' .

Results

We conducted our experiments on a Mac OS X 10.6.8 system with an Intel Core i7 2.66GHz and 8 GB of RAM. The average of six runs for the query rewriting and evaluation time was calculated.

Decompositions

The following list shows the hypergraph decomposition for each query:

q1_N1(x,u) :- MAPIntersection(x), hasGeo(x,u). q1_N2(y,v) :- hasGeo(y,v), Parking(y). q1(x,y) :- q1_N1(x,u), near(u,v), q1_N2(y,v).
q2(x,z) : Vehicle(x), speed(x,y)[avg,10], y > 30, vehicleMaker(x,z).
q3_F1(x,y) :- Vehicle(x), pos(x,y)[line,10]. q3_N1(v,u) :- MAPLaneIn(v), hasGeo(v,u). q3(x,v) :- q3_F1(x,y), intersects(y,u), q3_N1(v,u) .
q4_F1(x,y) :- Vehicle(x), pos(x,y)[line,15]. q4_F2(y,z) :- pos(y,z)[line,15], Bus(y). q4(x,y) :- q4_F1(x,y), intersects(y,z), q4_F2(y,z), x != y.
q5(x,y) : MAPLineIn(x), hasSignal(x,y), MAPSignalGroup(y), hasState(y,z)[last,15], z = 'R'.
q6_F1(y,r) :- Vehicle(y), speed(y,r)[avg,10], r > 30. q6_F2(y,v) :- pos(y,v)[line,10], Vehicle(y), q6_F1(y,r). q6_F3(x,z) :- hasSignalGroup(x,z), MAPSignalGroup(z), signalState(z,t)[last,15], t = 'R'. q6_N1(x,u) :- MAPLaneIn(x), hasGeo(x,u), q6_F3(x,z), MAPIntersection(w), isPartOf(x,w), w = 'I1'. q6(x,y) :- q6_N1(x,u), intersects(u,v), q6_F2(y,v).

Evaluation

The results shown below present query type, size of rewritten atoms, the number of subqueries, and the average evaluation time in seconds for n vehicles.

	Type	#Atom	# Sub Queries	10	Time 100	with 500	n Veh. 1000	2500	5000
q1	O,S	4	3	1.01
q2	O,F	21	1	1.02	1.08	1.17	1.28	1.59	1.63
q3	O,S,F	23	3	1.05	1.10	1.18	1.51	1.94	1.72
q4	O,S,F	22	3	1.05	1.10	1.17	1.36	1.74	1.71
q5	O,F	6	1	1.15	1.15	1.15	1.15	1.25	1.26
q6	O,S,F	53	5	1.25	1.32	1.31	1.47	2.48	1.83

Generation Tools

Tbd.

Detailed Logs

The all logs are put into this spreadsheet .

References

[1] Thomas Eiter, Herbert Füreder, Fritz Kasslatter, Josiane Xavier Parreira, Patrik Schneider. Towards a Semantically Enriched Local Dynamic Map. In Proc. of 23rd ITS World Congress (ITSWC 2016). To appear.

[2] Thomas Eiter, Jeff Z. Pan, Patrik Schneider, Mantas Simkus, Guohui Xiao. A Rule-based Framework for Creating Instance Data from OpenStreetMap. In Proc. of 9th International Conference on Web Reasoning and Rule Systems (RR 2015)

Contact

Patrik Schneider patrik(a)kr.tuwien.ac.at