Experimental Evaluation (EKAW 2018 Paper)
Introduction
This page contains information about benchmarking our spatial OQA (Ontology-Mediated Query Answering)
system in three Cooperative Intelligent Transport Systems (C-ITS) scenario and related use cases.
The C-ITS streams are integrated by an approach called Local Dynamic Map (LDM), which is a standardized integration platform for spatial and stream data.
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;
- Nine queries, which represent real-life queries derived from three scenarios and its use cases;
- Data is generated by a traffic simuluation with an #-shaped intersection structure and three levels of traffic densities (low, medium, high) that are used to generated streaming data, i.e.,vehicle movement (e.g., speed and position) and signal phases;
Database
The PipelineDB instance is split into a static and a streaming part.
The static database includes the ontology definitions and static instances:
- TBox including the concept and role inclusions;
- ABox including placeholder for vehicles the defintions of the intersections, lanes, etc.;
- The spatial database is directly imported from OSM instances including 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 numeric, tp numeric) → v_speed → ldm:speed
-
stream_pos (iid integer, x text, tp numeric) → v_pos → ldm:position
-
stream_signalstate (iid integer, x text, tp numeric) → v_signalstate → ldm:hasSignalState
Each stream is made of the columns iid
(object identification), x
(data point), and tp
(time point of the data item). We provide a PipelineDB 9.8.1 database dump that incluses the full DB schema with static instances.
Use the PipelineDB loader pipeline -d ldm_2 -f ldm_2.bak
to create the database ldm_2
.
As a prerequisite the database ldm_2
has to be created (e.g., using pgAdmin3) using the parameter Encoding: UTF8
and Template: pipeline
.
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).
C-ITS Scenarios
Our experiments are based on the following three scenarios, which were designed in cooperation with domain experts at Siemens Mobility:
- Traffic statistics
- Hazardous Events detection
- ADAS - Advanced driver-assistance systems
The scenarios are split into several use-cases that build the base to derive features and requirements.
We have derived a set of ten queries that represent the use-cases and take the features and requirements of each case into account.
Scenario Data
For the scenario data, we use a realistic traffic simulation of 4 intersections in a #-shaped layout.
The scenario environment was developed with the microscopic traffic simulation
PTV VISSIM
that allows us to simulate realistic driving behavior and signal phases. The structure of the intersection, driving patterns and signal phases are fixed, but we have adapted the traffic densities by light, medium, and heavy traffic.
We developed an adapter (not published here) that extracts the actual state of each simulation step, allowing us to replay the simulation from the logs. To increase the throughput for the experiments, we are able to replay the simuluation with 5ms, 10ms, 50ms, and 100ms (real-time speed of VISSIM) delay.
For creating the scenario data, we provide a script for the generation of existing vehicles vehicles_gen.py (run once for initialization) and a script for
running the simulation generating the streams stream_play_vissim.py. The second script replays a chosen VISSIM simulation log,
which we recorded from the simulation. We used low,
medium,
and high traffic densities for our benchmarks.
Below are the queries (divided by each scenario) that are used for the experiments:
Traffic Statistics
- Q1.1 - Object statistics : query q11 calculates the average and max speed over the last 10s of all BMWs and VWs.
q11(X,U,V) : Vehicle(X), speed(X,U)[avg,10], speed(X,V)[max,10], vehicleMaker(X,Z), (Z = 'BMW' or Z = 'VW') .
- Q1.2 - Road/intersection statistics : query q12 counts (seperately) the number of diesel and petrol vehicles passing the intersections i100.
q12a(X,Y) : Car(Y), pos(Y,Z)[line,10], vehicleEngine(Y,M), M = 'Petrol', intersects(Z,U), hasGeo(X,U), MAPIntersection(X), X = 'i100' .
q12b(X,Y) : Car(Y), pos(Y,Z)[line,10], vehicleEngine(Y,M), M = 'Diesel', intersects(Z,U), hasGeo(X,U), MAPIntersection(X), X = 'i100' .
q12(X,Y,Z) : q12a(X,Y)[count,10], q12b(X,Z)[count,10] .
- Q1.3 - Network statistics : query q13 traces the vehicles that start at I1 and counts those vehicles passing through I2. A delay of 7s allows to check the vehicle’s position 7s later, and the temporal relation before ensures that a vehicle first passes i100 and then i200.
q13a(X,V) : Vehicle(X), pos(X,V)[line,6], intersects(V,U), hasGeo(R,U), MAPIntersection(R), R = 'i100' .
delay(7s) .
q13b(X,Z) : Vehicle(X), pos(X,Z)[line,6], intersects(Z,W), hasGeo(R,W), MAPIntersection(R), R = 'i200' .
q13c(X) : q13a(X,V), before(V,Z) q13b(X,Z) .
Hazardous Events Detection
- Q2.1 - Simple maneuvers : query q21 returns all vehicles that either turn left/right by an Union of CQ. We introduce here the "match" atom
that checks if a trajectory (simplyfied to two lines), has an angle in between -180 and -20 (left) and 20 and 180 (right).
q21l(X,Y) : Vehicle(X), pos(X,Y)[line,6], match_angle(Y,Z,-175,-15), intersects(Y,U), hasGeo(R,U), MAPIntersection(R), R = 'i100' .
q21r(X,Y) : Vehicle(X), pos(X,Y)[line,6], match_angle(Y,Z,15,175), intersects(Y,U), hasGeo(R,U), MAPIntersection(R), R = 'i100' .
q21(X,Y) : q21l(X,Y) or q21r(X,Y) .
- Q2.2 - Complex maneuvers : query q22 checks if there is an illicit lane change, by checking the trajectory of vehicles that first are on in-lanes, and after cross to out-lanes.
q22(X,Y) : Vehicle(X), pos(X,V)[line,6,3], pos(X,W)[line,3,0], intersects(U,V), hasGeo(Z,U), MAPLaneIn(Z), intersects(S,W), hasGeo(Y,S), MAPLaneOut(Y) .
- Q2.3 - Red-light violations : query q23 detects red-light violations on intersections by searching for vehicles y at speed above 30km/h on lanes x whose signals will turn red in 5s. We use the functions
"traject_line" and "avg_reg" to predict the trajectory and speed in 2s in the future using simple trajectory projection and linear regression.
q23(X,Y) : MAPLineIn(X), hasGeo(X,U), intersects(U,V), pos(Y,V)[traject_line,5,-3], Vehicle(Y), speed(Y,R)[avg_reg,5,-3], (R > 10), hasSignalGroup(X,Z), MAPSignalGroup(Z), signalState(Z,T)[last,5,-5], T = 'R' .
- Q2.4 - Vehicle breakdown : with query q24, we check if a car
is for longer in our intersections, but not on one of its lanes. Further
we check if the car is not moving.
q24(X,Y) : Vehicle(X), pos(X,V)[line,15], speed(X,R)[avg,30], (R < 1), inside(V,U), hasGeo(Y,U), MAPIntersection(Y), during(V,R) disjoint(V,Z), hasGeo(P,Z), MAPParkLane(P) .
- Q2.5 - Traffic congestion : query q25 is only an estimation for traffic congestion
by checking if we have more than 20 standing cars. However,
we miss in our language (a) a long-term memory to store traces of traffic statistics, and (b) temporal relations that expressing that an event happend before another event.
q25(X,Y) : Vehicle(X), pos(X,V)[line,30], speed(X,R)[avg,30], (R < 1), intersects(V,U), hasGeo(Y,U), MAPLaneIn(Y), hasSignalGroup(Y,Z), MAPSignalGroup(Z), signalState(Z,S)[last,30], T = 'G', during(S,R) .
ADAS
- Q3.1 - Self monitoring : query q31 detects, if our ego vehicle is exceeding the speed limit that is assigned to the intersection our ego vehicle (identified as "car340") is currently driving on.
q31(X,W) : Vehicle(X), pos(X,V)[line,5], speed(X,W)[avg,5], intersects(V,U), hasGeo(Y,U), MAPIntersection(Y), speedLimit(Y,T), W > T, X = 'car340' .
- Q3.2 - Obstructed view : in query q32 we aim to detect cars that very likely will collide in next seconds with our ego vehicle by checking if our predicted trajectories will cross other cars.
q32(X) : Vehicle(X), pos(X,V)[traject_line,2,-1], speed(X,W)[mean_avg,5,-2], W > 10, intersects(V,U), Vehicle(Y), pos(Y,U)[traject_line,2,-1], W > T, Y = 'car340' .
- Q3.3 - Traffic rules : Detecting the violation of traffic rules, is not easy achievable by CQs, hence we need to encode them using a set of horn clauses, where
we encode the "right of way" as follows:
willCross(X,Y) ∧ straightOn(X) ∧ turnRight(Y) → giveWay(Y,X)
willCross(X,Y) ∧ turnLeft(X) ∧ turnRight(Y) ∧ crossOppositeLane(Y) → giveWay(Y,X)
vehicle(X) ∧ vehicle(Y) ∧ giveWay(Y,X) → stop(Y)
Note that we decompose each rule into a union of CQs and where eacg rule is a single CQ.
Decompositions
The hypergraph decompositions for each query are available in the following
file.
We have named the sub-queries by their types "_N" (normal), "_F" (stream), "_S" (spatial), and "_J" (join).
For instance, the decompositions for query q11 is as follows:
-
q11_N1(X,U) :- Vehicle(X), vehicleMaker(X,Z), Z = 'BMW' or Z = 'VW' .
-
q11_F1(X,Y) :- q11_N1(X,U), speed(X,Y)[avg,10] .
-
q11_F2(X,Z) :- q11_N1(X,U), speed(X,Z)[max,10] .
-
q11_J1(X,Y,Z) :- q11_F1(X,Y), q11_F2(X,Z) .
Results
We conducted our experiments on a Mac OS X 10.13.4 system with an Intel Core i7 2.9GHz, 8 GB of RAM,
and a 500GB SSD. The average of 21 runs for the query rewriting and evaluation time was calculated
with no outliers ignored.
Evaluation
The results of our experiments are shown below with the average evaluation time (AET) in seconds for
low, medium, and high
traffic data replayed with 5, 10, 50, and 100ms
delay, where
100ms is the normal replay speed of VISSIM.
We show for each conjunctive query the number of atoms and the number of sub-queries including the number
of stream sub-queries in brackets.
|
# Sub Queries |
# Atoms |
5
|
Low 10
|
Traffic 50
|
100
|
5
|
Medium 10
|
Traffic 50
|
100
|
5
|
High 10
|
Traffic 50
|
100
|
Logs |
q1.1 |
3 (2) |
42 |
1.35 |
1.18 |
0.95 |
0.86 |
1.45 |
1.30 |
0.99 |
0.88 |
1.46 |
1.35 |
1.14 |
0.99 |
q11 |
q1.1* |
3 (2) |
42 |
1.00 |
0.95 |
0.81 |
0.80 |
1.03 |
0.96 |
0.83 |
0.80 |
1.05 |
1.03 |
0.87 |
0.81 |
q11b |
q1.2 |
6 (2) |
43 |
1.30 |
1.20 |
1.01 |
0.96 |
1.33 |
1.24 |
1.04 |
1.00 |
1.41 |
1.38 |
1.07 |
1.01 |
q12 |
q1.3 |
8(2) |
44 |
1.44 |
1.35 |
1.15 |
1.08 |
1.47 |
1.37 |
1.23 |
1.09 |
1.45 |
1.44 |
1.30 |
1.20 |
q13 |
q2.1 |
6(2) |
43 |
1.31 |
1.20 |
1.01 |
0.98 |
1.43 |
1.29 |
1.09 |
0.99 |
1.48 |
1.40 |
1.13 |
1.02 |
q21 |
q2.2 |
7(2) |
45 |
1.36 |
1.26 |
1.05 |
1.00 |
1.47 |
1.29 |
1.08 |
1.03 |
1.51 |
1.43 |
1.13 |
1.06 |
q22 |
q2.3 |
7(3) |
50 |
1.57 |
1.50 |
1.27 |
1.21 |
1.63 |
1.53 |
1.30 |
1.22 |
1.72 |
1.65 |
1.37 |
1.27 |
q23 |
q2.4 |
5(2) |
46 |
1.24 |
1.21 |
0.98 |
0.92 |
1.28 |
1.24 |
1.06 |
0.97 |
1.28 |
1.29 |
1.13 |
0.99 |
q24 |
q2.5 |
7(3) |
43 |
1.44 |
1.38 |
1.16 |
1.08 |
1.50 |
1.41 |
1.20 |
1.11 |
1.55 |
1.47 |
1.26 |
1.17 |
q25 |
q3.1 |
5(2) |
43 |
1.85 |
1.72 |
1.40 |
1.32 |
1.89 |
1.79 |
1.48 |
1.35 |
2.06 |
2.04 |
1.57 |
1.38 |
q31 |
q3.2 |
5(3) |
63 |
1.41 |
1.34 |
1.23 |
1.17 |
1.48 |
1.43 |
1.27 |
1.20 |
1.56 |
1.51 |
1.31 |
1.21 |
q32 |
q3.3 |
12(5) |
43 |
3.02 |
2.80 |
2.42 |
2.39 |
3.26 |
2.98 |
2.58 |
2.38 |
3.36 |
3.20 |
2.66 |
2.44 |
q33 |
Each log file contains the details on each run for a particular query, traffic density, and replay delay.
For q3.3, we estimate the AET by running q2.1 twice for the the first two rules and add an estimate of 0.4s
to evaluate for the third rule, since our approach is geared towards CQ and cannot run a Datalog
rules directly.
Two comments regarding the evaluation of the stream atoms:
-
In the newset version, we allow the parallel creation and evaluation of stream atoms.
This is related to the problem that the combination between temporal relations and sequential stream
evaluation causes missing results, due to the delayed execution. A side effect is an slighty improved
performance as seen in q1.1 (sequential) and q1.1* (parallel) execution.
-
Queries with stream atoms have a built-in delays of 0.18s, since the Continuous Views
need that time to be "set up". Otherwise PipelineDB would return less or no result.
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.
References
[1] Thomas Eiter, Herbert Füreder, Fritz Kasslatter, Josiane Xavier Parreira, Patrik Schneider.
Towards a Semantically Enriched Local Dynamic Map.
International Journal of Intelligent Transportation Systems Research. Available online (2018)
[2] Spatial Ontology-Mediated Query Answering over Mobility Streams.
In Proc. of ESWC 2017. pp. 219–237 (2017)
[3] Detecting Mobility Patterns using Spatial Query Answering over Streams.
Stream Reasoning Workshop at ISWC 2017 (2017)
Contact
Patrik Schneider patrik(at)kr.tuwien.ac.at