Experimental Evaluation (ESWC 2017 paper)
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 platform for spatial and stream data in Cooperative Intelligent Transport Systems (ITS) .
General Setup
The following components are used to perform 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;
- A set of queries, which represent real life and syntetic queries;
- Two C-ITS scenarios, which are used to define the intersection structure and the generated stream data, i.e.,vehicle movement (e.g., speed and position) and signal phases;
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.
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).
Scenarios
Our experiment is based on two scenarios of monitoring vehicles and traffic lights (a) on a single intersection and (b) on a network of locally connected intersections, both managed by a single roadside C-ITS station.
Scenario (a)
We have a T-shaped intersection that represents a real-world deployment of C-ITS stations in Vienna. It connects two roads with 13 lanes and 3 signal groups that are linked to the lanes. We developed a synthetic data generator that simulates the movement of 10, 100, 500, 1000, 2500, and 5000 vehicles on a single intersection updating the streams averagely 50ms. This allows us to generate streams with up to 10000 data points per sec. and stream. We chose random starting points and simulated linear movements on a constant pace, creating a stream of vehicle positions. We also simulated simple signal phases for each traffic light that toggle between red and green every 3 secs. The aim of this scenario is to show for simple driving patterns the scalability of our approach in the number of vehicles.
We provide two python scripts for generating the data, vehicles_gen.py generates the vehicles (including their brand) as instances, and stream_gen_syn.py generates the vehicle movements and signal phases. The movement scripts can be run in parallel (using --lower --upper to define vehicle id ranges) to generate a large amount of stream data, since a single generator instance can not create large throughput.
Scenario (b)
In (b), we use a realistic traffic simulation of 9 intersections in a grid, developed with the microscopic traffic simulation
PTV VISSIM that allows us to simulate realistic driving behavior and signal phases. The intersection structure, driving patterns and signal phases are more complex, but the number of vehicles is lower (max. 300) than in (a), as we quickly have traffic jams. We developed an adapter to extract the actual state of each simulation step, allowing us to replay the simulation from the logs. To vary data throughput, we ran the replay with 0ms, 100ms (real-time), 250ms and 500ms delay. For illustration, we provide a recording of 12s in the simulation.
For this scenario, the vehicle generation script is the same as in (a), and the VISSIM simulation can be generated using
stream_gen_vissim.py using the
logs of the 9-intersection simulation.
Queries
The following queries represent the input for the experiments and are described below:
- Show all cars with their brands that travel above 30 (km/h):
q1(X,Y) :- Car(X), speed(X,Y)[avg,10], vehicleMaker(X,Z), Y > 30 .
- Show all lanes and signal groups that switched the last 15s to Red:
q2(X,Y) :- MAPLaneIn(X), hasSignalGroup(X,Y), MAPSignalGroup(Y), signalState(Y,Z)[last,15], Z = 'R'.
- Show all vehicles on incoming lanes:
q3(X,V) :- Vehicle(X), pos(X,Y)[line,10], intersects(Y,U), hasGeo(V,U), MAPLaneIn(V) .
- Show all vehicles with crossed paths in the last 30s:
q4(X,Y) :- Vehicle(X), pos(X,W)[line,30], intersects(W,Z), pos(Y,Z)[line,30], Car(Y) .
- Show all vehicles above 30km/h that head straight:
q5(X,Y) :- Vehicle(X), pos(X,Y)[line_angle,15], speed(X,Z)[avg,15], Car(Y), Z > 10, Y < 10, Y > -10 .
- Show all red-light violations on intersections '4705069100' by searching for vehicles y with speed above 30km/h the last 10s on lanes x whose signals will turn red in 15s (Example 1. of paper):
q6(X,Y) :- MAPLineIn(X), hasGeo(X,U), intersects(U,V), pos(Y,V)[line,10], Vehicle(Y), speed(Y,R)[avg,10], R > 10, hasSignalGroup(X,Z), MAPSignalGroup(Z), signalState(Z,T)[last,15], T = 'R', isPartOf(X,W), MAPIntersection(W), W = '4705069100' .
- Synthetic query for testing many ontology atoms:
q7(X,Z) :- MAPLaneIn(X), hasSignalGroup(X,Y), MAPSignalGroup(Y), signalState(Y,R)[last,15], R = 'R', isPartOf(X,U), MAPIntersection(U), U = '4705069100', connected(X,Q), connected(Q,V), MAPLane(V), hasSignalGroup(V,Z), MAPSignalGroup(Z), signalState(Z,S)[last,15], S = 'R'.
- Synthetic query for testing many spatial atoms:
q8(X,Y) :- Vehicle(X), pos(X,Y)[line,20], intersects(Y,U), hasGeo(R,U), MAPLaneIn(R), intersects(Y,V), hasGeo(S,V), MAPLaneIn(S), intersects(Y,W), hasGeo(T,W), MAPLaneIn(T), within(Y,Z), hasGeo(Q,Z), MAPIntersection(Q) .
- Synthetic query for testing many stream atoms:
q9(X,Q,R,S,T,U) :- Vehicle(X), speed(X,Q)[avg,1], speed(X,R)[avg,5], speed(X,S)[avg,10], speed(X,T)[avg,30], speed(X,U)[avg,60] .
Decompositions
The following list shows the hypergraph decomposition for each query:
-
Query q1(X,Y):
Single query, no decomposition.
-
Query q2(X,Y):
Single query, no decomposition.
-
Query q3(X,V):
q3_F1(X,Y) :- Vehicle(X), pos(X,Y)[line,10] .
q3_N1(V,U) :- MAPLaneIn(V), hasGeo(V,U).
q3_S1(X,V) :- q3_F1(X,Y), intersects(Y,U), q3_N1(V,U) .
-
Query q4(X,Y):
q4_F1(X,W) :- Vehicle(X), pos(X,W)[line,30] .
q4_F2(Y,Z) :- pos(Y,Z)[line,30], Car(Y) .
q4_S1(X,Y) :- q4_F1(X,W), intersects(W,Z), q4_F2(Y,Z).
-
Query q5(X,Y):
q5_F1(X,Z) :- Vehicle(X), speed(X,Z)[avg,15], Z > 10 .
q5_F2(X,Y) :- Vehicle(X), pos(X,Y)[line_angle,15], Y < 10, Y > -10 .
q5_J1(X,Y) :- q5_F1(X,Z), q5_F2(X,Y) .
-
Query q6(X,Y):
s
q6_F3(X,Z) :- MAPLaneIn(X), hasSignalGroup(X,Z), MAPSignalGroup(Z), signalState(Z,T)[last,15], T = 'R' .
q6_F1(Y,R) :- speed(Y,R)[avg,10], Vehicle(Y), R > 10 .
q6_F2(Y,V) :- pos(Y,V)[line,10], Vehicle(Y) .
q6_J1(Y,V) :- q6_F2(Y,V), q6_F1(Y,R) .
q6_N1(X,U) :- MAPLaneIn(X), hasGeo(X,U), MAPIntersection(W), isPartOf(X,W), W = '4705069100' .
q6_J2(X,U) :- q6_F3(X,Z), q6_N1(X,U) .
q6_S1(X,Y) :- q6_J2(X,U), intersects(U,V), q6_J1(Y,V) .
-
Query q7(X,Z):
q7_F1(X,Y) :- MAPLaneIn(X), hasSignalGroup(X,Y), MAPSignalGroup(Y), signalState(Y,R)[last,15], R = 'R' .
q7_N1(X,U) :- MAPLaneIn(X), MAPIntersection(U), isPartOf(X,U), U = '4705069100' .
q7_J1(X,Y) :- q7_F1(X,Y), q7_N1(X,U) .
q7_N3(X,V) :- MAPLaneIn(X), connected(X,Q), connected(Q,V) .
q7_F2(V,Z) :- MAPLane(V), hasSignalGroup(V,Z), MAPSignalGroup(Z), signalState(Z,S)[last,15], S = 'R' .
q7_J2(X,Z) :- q7_J1(X,Y), q7_N3(X,V), q7_F2(V,Z) .
-
Query q8(X,Y):
s
q8_F1(X,Y) :- Vehicle(X), pos(X,Y)[line,20] .
q8_N1(Q,Z) :- MAPIntersection(Q), hasGeo(Q,Z) .
q8_S1(X,Y) :- q8_F1(X,Y), within(Y,Z), q8_N1(Q,Z) .
q8_N2(R,U) :- MAPLane(R), hasGeo(R,U) .
q8_S2(X,Y) :- q8_S1(X,Y), intersects(Y,U), q8_N2(R,U) .
q8_N3(S,V) :- MAPLane(S), hasGeo(S,V) .
q8_S3(X,Y) :- q8_S2(X,Y), intersects(Y,V), q8_N3(S,V) .
q8_N4(T,W) :- MAPLane(T), hasGeo(T,W) .
q8_S4(X,Y) :- q8_S3(X,Y), intersects(Y,W), q8_N4(T,W) .
-
Query q9(X,Q,R,S,T,U):
q9_F1(X,Q) :- Vehicle(X), speed(X,Q)[avg,1] .
q9_F2(X,R) :- Vehicle(X), speed(X,R)[avg,5] .
q9_J1(X,Q,R) :- q9_F1(X,Q), q9_F2(X,R) .
q9_F3(X,S) :- Vehicle(X), speed(X,S)[avg,10] .
q9_J2(X,Q,R,S) :- q9_J1(X,Q,R), q9_F3(X,S) .
q9_F4(X,T) :- Vehicle(X), speed(X,T)[avg,30] .
q9_J3(X,Q,R,S,T) :- q9_J2(X,Q,R,S), q9_F4(X,T) .
q9_F5(X,U) :- Vehicle(X), speed(X,U)[avg,60] .
q9_J4(X,Q,R,S,T,U) :- q9_J3(X,Q,R,S,T), q9_F5(X,U) .
Results
We conducted our experiments on a Mac OS X 10.6.8 system with an Intel Core i7 2.66GHz, 8 GB of RAM,
and a 500GB HDD. The average of 11 runs for the query rewriting and evaluation time was calculated
with the largest outlier ignored.
Evaluation (a)
The results shown are for scalability scenario (a) and present query type, size of rewritten atoms,
the number of subqueries, and the average evaluation time (AET) in seconds for n vehicles.
Note, that all the queries with multiple stream atoms (q4, q5, q6, and q9) have a builtin delay of 0.2s
since the Continuous Views of PIPELINEDB do return less or no result, if queried immediately after
each other.
Each conjunctive query has sub-queries of different types, where O, S, resp. F represents ontology, spatial,
resp. stream sub-queries.
Marked with (*) are the queries that only contain "slow" streams generated by traffic lights.
Also attached are the logs of the executions, where the details on each evaluation step is documented.
|
Type |
# Sub
Queries |
# Atoms |
10
|
Time
100
|
with
500
|
n Veh.
1000
|
2500
|
5000
|
Logs |
| q1 |
O,F |
1 |
1 |
0.85 |
0.82 |
0.91 |
1.05 |
1.22 |
1.58 |
a_q1 |
| q2 |
O,F (*) |
1 |
6 |
0.83 |
0.83 |
0.83 |
0.83 |
0.83 |
0.83 |
a_q2 |
| q3 |
O,S,F |
3 |
23 |
0.89 |
0.87 |
1.00 |
1.25 |
1.39 |
1.74 |
a_q3 |
| q4 |
O,S,F |
3 |
22 |
1.10 |
1.09 |
1.24 |
1.53 |
1.81 |
2.32 |
a_q4 |
| q5 |
O,S,F |
3 |
42 |
1.11 |
1.10 |
1.26 |
1.39 |
1.90 |
1.92 |
a_q5 |
| q6 |
O,S,F |
7 |
52 |
1.39 |
1.39 |
1.49 |
1.69 |
2.36 |
2.28 |
a_q6 |
| q7 |
O,F (*) |
6 |
69 |
1.16 |
1.16 |
1.16 |
1.16 |
1.16 |
1.16 |
a_q7 |
| q8 |
O,S |
9 |
73 |
0.92 |
0.94 |
1.30 |
1.43 |
1.72 |
2.19 |
a_q8 |
| q9 |
O,F |
9 |
105 |
1.67 |
1.73 |
1.99 |
2.06 |
2.49 |
2.97 |
a_q9 |
A summary of all the logs for (a) is given in the spreadsheet, where we
also provide details on the calculation of the AET.
Evaluation (b)
The results shown are for VISSIM scenario (b) with the average evaluation time delay in ms in the 5,6,7, and 8 column.
|
Type |
# Sub
Queries |
# Atoms |
0
|
Time
100
|
with
250
|
ms delay
500
|
Logs |
| q1 |
O,F |
1 |
1 |
0.78 |
0.74 |
0.73 |
0.71 |
b_q1 |
| q2 |
O,F (*) |
1 |
6 |
0.77 |
0.77 |
0.72 |
0.71 |
b_q2 |
| q3 |
O,S,F |
3 |
23 |
0.83 |
0.81 |
0.77 |
0.75 |
b_q3 |
| q4 |
O,S,F |
3 |
22 |
1.02 |
1.00 |
0.95 |
0.93 |
b_q4 |
| q5 |
O,S,F |
3 |
42 |
1.05 |
1.00 |
0.98 |
0.96 |
b_q5 |
| q6 |
O,S,F |
7 |
52 |
1.40 |
1.28 |
1.26 |
1.25 |
b_q6 |
| q7 |
O,F (*) |
6 |
69 |
1.15 |
1.12 |
1.11 |
1.09 |
b_q7 |
| q8 |
O,S |
9 |
73 |
0.99 |
0.98 |
0.92 |
0.91 |
b_q8 |
| q9 |
O,F |
9 |
105 |
1.71 |
1.68 |
1.66 |
1.63 |
b_q9 |
A summary of all the logs for (b) is given in the spreadsheet
Sources and Executable
The files for reproducing the experiments are available under shell script, JAR-file, and config.properties.
The sources of our implementation is available under code, where the entry point to the stream QA code is in SemSearchLDM.java.
We will also provide later a full installation environment using gradle.
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).
[2] Thomas Eiter, Thomas Krennwallner, Patrik Schneider.
Lightweight spatial conjunctive query answering using keywords.
In Proc. of ESWC 2013
Contact
Patrik Schneider patrik(a)kr.tuwien.ac.at