ACM International Conference on Distributed Event-Based Systems (DEBS) is one of the primary venues for Complex Event processing related research. Every year, they provide a grand challenge that challenges the participants to solve an event-based problem.
This year we are also competing, and following are some of our experiences while doing it.
This year grand challenges is to process events generated in a football game and answer four queries related to the game in streaming fashion. Both the player’s shoes and ball had sensors, and as the game continues, it generates about 15,000 events per second. Each event includes the location (x,y,z), time stamp, velocity and acceleration of the sensor. You can find more information from http://www.orgs.ttu.edu/debs2013/index.php?goto=cfchallengedetails. Complete dataset is 49 million events.
There are four usecases. I will explain each and tell bit about how we implemented them. To understand the queries, you need to know the Siddhi Event query language. Following is a crash course.
from [condition on event],
[condition on event],
[condition on event] ...
Here the comma separated conditions define an event sequence. That is the query matches when those conditions have matched in the given order by the incoming events.
We worked with two streams: Players – events from players and BallStream – events from the ball.
Usecase 1: Running analysis
The first usecase measures each player’s running speeds and calculates how long he spent on different speed ranges. For example, results will tell that the player “Martin” is running fast from the time 27 minutes and 01 second of the game to 27 minute and 35 second of the game.
We have implemented this usecase by using CEP event sequences to detect whenever a player crossed a threshold of event speeds using a query like following.
define partition player by Players .id</pre>
from s = Players [v 11] ,</pre>
t = Players [v > 1 and v <= 11]+ , e = Players [v 11]
select s.ts as tsStart , e.ts as tsStop ,s.id as playerId ,</pre>
<pre> ‘‘trot" as intensity , t .v as instantSpeed ,</pre>
<pre> (e.ts - s.ts )/1000000000 as unitPeriod
insert into RunningStats partition by player
Query define sequence of conditions. For example, Players [v 11] means velocity range in events received in player event stream. Siddhi invokes the callback when those conditions are met.
Here “+” point to one or more occurrences similar to regular expressions. You can find more information about Siddhi language from Siddhi Language Specification. We wrote a query for each speed range, found the time stamps of speed range changes, and calculated the final result.
Here event partitions partition the events by some condition before processing it. Above query partition events by the player.
Usecase 2 & 4: Ball Possession and Shots on Goal
For the second use case, we need to calculate the time each player controlled the ball (ball possession). A player controls the ball from the time he hit the ball until someone has hit the ball, ball goes out of the ground, or game is stopped. We identify hits when a ball is within one meter of a player and its acceleration increases by more than 55ms-2.
The usecase four is to detect hits and emit events if the ball is going to the goal.
We implemented both using event sequences, and following are the queries. Here fuctions like debs:isGoingToGoal(..) and debs:getDistance(..) are java custom functions we wrote and registered with Siddhi.
Following query detects the hits.
from Ball#window.length(1) as b join
Players\#window.length(1) as p unidirectional
p.x, p.y, p.z) 55
select p.sid, p.ts, p.x, p.y, p.z, p.a, p.pid,p.tid,
b.sid as ballSid
insert into hitStream
Following query detects the event streams while a player is in control of the ball.
from old = hitCountStream,
b = hitCountStream[old.pid != pid ],
n=hitCountStream[b.pid == pid]*,
e1 = hitCountStream[b.pid != pid ]
select b.pid as playerId, b.tid as teamId,
b.ts as startTs,
coalesce(e1.ts ,e2.ts) as endTs,
coalesce(e1.cnt ,e2.cnt) as counter1,
b.cnt as counter2
insert into BallPossessionStream
following query detects hits at the goal.
from s = hitStream,
t = Ball[debs:getDistance(s.x,s.y,s.z,
x, y, z) < 1000]+,
e = Ball[debs:isGoingToGoal(s.tid,x,y,z
,a,v,vx,vy,vz,s.ts,ts) == 1.0]+,
h = Ball[debs:isGoingToGoal(s.tid,x,y,z,
a,v,vx,vy,vz,s.ts,ts) == 0.0]
select s.ts as startTime, e.ts, s.pid,
s.tid, 'on' as mode "
insert into ShotOnGoalStream
Usecase 3: Heatmap of Activity
Usecase three divides the ground to a grid, and calculate the time a player spends on each cell. However, this usecase needs updates once every second. First part we can solve just like with the first usecase, but to make sure we get an event once a second, we had to couple it with a timer.
The queries are given below, and you can find the explanation from the paper. Following query detects when a player has changed the cell.
Following query use results from above two queries and calculate the time spent on each cell.
We were able to get about 50,000 events per second for usecase 3 and more than 100000 event per second with other usecases on a 4 core, 4G VMware virtual machine. This is about three times the required rate of 15000 events, which we believe to be impressive. Also this shows that Siddhi EQL can naturally fit such a complex scenario into queries, and they provide a nice higher level abstraction to think about the problem.
Hope this was interesting. Implementing the actual scenarios included more queries to calculate all the details, but above presents the basic idea.