# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 5 Timeline Query Index and Analytical Query Processing
### TQ-index Construction
#### Congestion Event Detection
: Before the loop in line 4 is executed, _stat_ of all road links is _not congested_, _logs_ is sorted by time, and \(E\) is an empty list. _stat_ can be considered a previous congestion state of all link ID. For every iteration, the current congestion state can be obtained by checking the _log.speed_ value. If a value of _log.speed_ is less than the threshold \(th\), then the current state is congested; otherwise, it is not congested. By Lemma 1, it is true that the first detected event of all road links is a _START_ event, because we set _not congested_ as the initial status, and a _STOP_ event will be detected later. This proves the correctness of the Congestion Events Detection algorithm. ### Congestion Dependency Calculation

The congestion events extracted by Algorithm 2 are further examined for the property of congestion dependency. This is because road link congestion will affect subsequent congestion of the following road links, or it is an affected congestion caused by the previous congestion of other road links. The type of dependency can be utilized to indicate that specific congestion is the head of congestion in road links or the affected congestion. In addition, we also connect related congestion to reveal the effect of the congestion. Algorithm 3 shows the process for revealing the affectedness of a congestion event. To identify affectedness, we check the congestion status of the adjacent road link for the given congestion event. Thus, an iteration of the checking will be done for a set of previous road links and a set of subsequent road links in lines 4 to 9 and lines 10 to 15. If prior congestion exists in the previous link at the same

Figure 12: Case for congestion events detection. time in line 4, this implies that the congestion event has occurred due to congestion in the previous road link. Thus, the dependency type of the congestion is set to DEP (dependent). In other cases, the dependency type maintains the value of IND (independent), which is initialized in line 3. Whenever simultaneous congestion occurs in the subsequent road links, the type of these congestion events is automatically set to DEP in line 12. In lines 6 to 7 and 13 to 14, we connect related congestion events to construct a congested path (several road links) and see the effects of the congestion path. ```
Input: a congestion event \(e\), a \(LocationIndex\)\(LI\) Output: an updated congestion event \(e\)
1 procedureCalculateDependency(\(e\), \(LI\))
2 congestion \(c\gets e\);
3\(c\).type \(\leftarrow\) IND; // Finding source of congestion
4 foreach\(c_{prior}\gets LI.\)PriorCongsOf(\(c\))do
5\(c\).type \(\leftarrow\) DEP;
6\(c\).affectedby \(\leftarrow\)\(c_{prior}\); // c prior is affecting c
7\(c_{prior}.affecting\gets c\);
8
9 Stop iteration;
10 end foreach // update dependency of obtained subsequent congestion
11 foreach\(c_{subquent}\gets LI.\)SubquentCongsOf(\(c\))do
12 if\(c_{subquent}.\)start = \(c.\)_start then
13\(c_{subquent}.\)type \(\leftarrow\) DEP; // State that subsequent congestion is affected by c
14\(c_{subquent}.affectedby\gets c\); // State that c is affecting subsequent congestion
15\(c.affecting\gets c_{subquent}\) ;
16
17 end if
18 end foreach
```
**Algorithm 3**Congestion Dependency Calculation

We discuss the correctness of Algorithm 3 using the following theorem. **Theorem 3**. : _[Correctness of congestion dependency calculation] The Congestion Dependency Calculation algorithm is correct. In other words, for a congestion path containing \(n\) road links, every road link in the path can have either DEP or IND as the type._

Proof. : As shown in Figure 5(a), a congestion path can have several road links. We prove the lemma by induction on the number of road links \(n\). Let \(P(k)\) denote the congestion path of k road links and \(L(k)\) denote the \(k_{th}\) road link in \(P(K)\). 1. Basis of induction: \(P(1)\) is true. Generally, \(L(1)\) means a single road link. It is typically the head of the congestion path, and the type is set to IND. 2.