# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 5 Timeline Query Index and Analytical Query Processing
### TQ-index Construction
#### Congestion Event Detection  
For this step, we detect a _START_ event (the beginning of congestion) or a _STOP_ event (the end of congestion) of congestion explained in Definition 5. The congestion events detection in Algorithm 2 begins by reading daily raw traffic log files \(f\) and initializing a set of daily events \(E\). From line 4, we start to detect congestion events for each traffic data record. Lines 5 to 6 and 12 to 13 identify the change in congestion by comparing the current congestion status with the previous congestion status. There are only four cases of congestion status comparison among all of the raw traffic data, as illustrated in Figure 12. _Case1_ occurs when the congestion status moves from not congested to congested, and _Case2_ occurs when the congestion status moves from congested to not congested. However, _Case3_ (_Case4_) implies the maintenance of a congested (decongested) state. From _Case1_, a new _START_ event would be produced as written in Lines 7 to 8, and the current status will change to congested in Line 10. In contrast, _Case2_ produces a _STOP_ event as depicted in lines 14 to 15, and the current status will change to not congested. In both cases, a new congestion event will be added to \(E\) in lines 9 and 16. Nothing is done for _Case3_ and _Case4_, because they maintain the same state. We now state the correctness of Algorithm 2. The following proposition is key to establishing the correctness of algorithm Congestion Events Detection. ```
Input: daily raw traffic log file \(f\), a congestion status hashmap \(stat\) Output: a set of congestion events \(E\)
1 procedureDetectEvents(\(f\), \(stat\)) // Detect All Events
2\(logs\leftarrow\) sorted traffic data list by reading all lines from the file \(f\);
3 Initialize a set of congestion events \(E\) to be \(null\);
4 foreach\(tr\) in \(logs\)do
5 if\(tr.to<th\)then
6 if\(std[tr.lid]\) is congestedthen
7 Initialize a new event \(e\);
8\(e.ty\)\(\leftarrow\) START;
9\(E.\)Add(\(e\));
10\(stat[tr.lid]\)\(\leftarrow\) congested;
11 endif
12
13 endif
14
15 else
16 if\(stat[tr.lid]\) is congestedthen
17 Initialize a new event \(e\);
18\(e.ty\)\(\leftarrow\) STOP;
19\(E.\)Add(\(e\));
20\(stat[tr.lid]\)\(\leftarrow\) not congested;
21
22 endif
23
24 endfor
25
26 endfor
27
28 endfor
29
30 endfor
310 endfor
```  
**Algorithm 2**Congestion Events Detection  
```
Input: daily raw traffic log file \(f\), a congestion status hashmap \(stat\) Output: a set of congestion events \(E\)
1 procedureDetectEvents(\(f\), \(stat\)) // Detect All Events
2\(logs\leftarrow\) sorted traffic data list by reading all lines from the file \(f\);
32 Initialize a set of congestion events \(E\) to be \(null\);
4 foreach\(tr\) in \(logs\)do
5 if\(tr.to<th\)then
6 if\(std[tr.lid]\) is congestedthen
7 Initialize a new event \(e\);
8\(e.ty\)\(\leftarrow\) START;
9\(E.\)Add(\(e\));
10\(stat[tr.lid]\)\(\leftarrow\) congested;





**Proposition 1**. : _Given a road link \(l\), the congestion event is one of the cases in Figure 12. If we compare the previous status and the current status of road link \(l\), it is easy to find that the four cases are the possible combinations of the two statuses._

**Lemma 1**. : _For road link \(l\) in the road networks, we can have either a START event or a STOP event if the status of \(l\) is changed._

Proof. : By Proposition 1, a road link \(l\) can have only one of the four cases. However, only _Case1_ and _Case2_ create a new _START_ event or a new _STOP_ event, because these cases imply a change in congestion status. _Case3_ and _Case4_ do not generate any events (NULL), because these cases maintain the same state as the possible state of road link \(l\). **Theorem 2**. : _[Correctness of congestion event detection] Congestion Events Detection algorithm is correct. In other words, for any input of raw traffic log \(f\), the algorithm terminates after obtaining a set of congestion events \(E\) by considering only status changes of congested road segments._

Proof.