# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 5 Timeline Query Index and Analytical Query Processing
### TQ-index Construction
#### Congestion Event Detection
Induction hypothesis: Assume that \(P(i)\) is true for \(1\ \leq\ i\ \leq\ k\). We show that \(P(k+1)\) is true. The road links in \(P(k)\) are connected because the congestion events \(L(2),L(3),\ldots,L(k)\) are dependent. Case 1: If the congestion in road link \(L(k+1)\) is an independent IND, then it could be a starting node of a new congestion path \(P^{\prime}(1)\) and not a road link of \(P(k+1)\). Case 2: If the congestion in road link \(L(k+1)\) is affected by the previous congestion in \(L(k)\), then it has dependent congestion (DEP) type, which means it can be connected to \(P(k)\). Thus, \(P(k+1)\) is true. #### 5.2.3 Insertion to Timeline Model Information (TMI)

At this phase, we construct the TimelineModelInformation \(TMI\) of a TQ-index from extracted congestion and congestion events. The extracted information obtained in the previous algorithms will be inserted into \(EventList\) (\(EL\)) and \(CongestionList\) (\(CL\)) of \(TMI\). The elements of these lists are explained in Definition 7, and the structure of these lists is depicted in Figure 9. Algorithm 4 shows this insertion phase. We obtain the TimelineModelInformation \(TMI\) from the given TQ-index (line 2). Then, for each congestion event in \(E\), we add this information to the \(EventList\) of \(TMI\) by invoking AddToEventList in line 4. Then, we add the congestion \(c\) of \(e\) to the \(CongestionList\) of \(TMI\) by calling AddToCongestionList in line 6. This addition is invoked only when the type of \(e\) is \(START\). Otherwise, we do not add the congestion again into the \(CL\). The last step is to connect the congestion event and the \(TimeIndex\)\(T1\). ```
Input: A set of congestion events \(E\), a TQ-Index \(tqi\) Output: An updated TQ-Index \(tqi\)
1 procedureInsertionToTimelineModelInformation(\(E\),\(tqi\))
2 TimelineModelInformation\(tmi\gets tqi\).GetTML(\(L\));
3 foreach\(e\gets E\)do
4\(tmi\)AddToEventList(\(e\));
5 if\(e\).type is \(START\)then
6\(tmi\)AddToCongestionList(\(e\).\(c\));
7
8 endif
9\(tqi\).InsertToTimeIndex(\(e\));
10
11 endfor
```
**Algorithm 4**Insertion to TimelineModelInformation

#### 5.2.4 Insertion to TimeIndex TI

For this phase, we build a \(TimeIndex\) (\(T1\)), which presents a temporal part of traffic data. The main components are \(DailyEventReferences\) (\(DER\)) and \(EventTimeReferences\) (\(ETR\)) explained in Section 5.1. \(TimeIndex\) (\(T1\)) enables us to efficiently access a set of congestion events maintained in the \(EventList\) of \(TimelineModelInformation\) (\(TMI\)). The complete process is explained in Algorithm 5. First, we find the related vertex node of \(LocationIndex\) (\(LI\)), because \(T1\) is located in each vertex of \(LI\) (line 2). Then, we create an event time reference element \(et\) that keeps a pointer to a congestion event \(e\) and add it to \(ETR\) of \(T1\). Next, we try to find a node in \(DER\) that contains a reference to the first event in \(ETR\) on that given day (line 6). If the node does not exist, then we create a new node and add it to \(DER\) with a given day as the key and then refer to \(etr\) (lines 7 to 9). ```
Input: A TQ-index \(tqi\), a congestion event \(e\) Output: An updated TQ-index \(tqi\)
1 procedureT1 Insertion(\(tqi\), \(e\))
2// Get a road segment from the LocationIndex of a TQ-index
3
4
5:a road segment \(l\gets tqi\).LocationIndex.Find(\(e\).lid);
6
7:Initialize an EventTimeReferences \(etr\);
8:\(etr\).RefersTo(\(e\));
9:A DailyEventReferences \(der\gets l\).TimelIndex.GetDER(\(e\).GetDay());
10:if\(let\) is \(null\)then
11:\(der\leftarrow\) new DailyEventReferences(\(e\).GetDay());
12:\(der\).FirstDailyLocalEvent \(\gets\)\(etr\);
13:\(l\).TimelIndex.AddDER(\(der\));
14:endif
```
**Algorithm 5**Time Index Construction

After the execution of this phase, we have completed the construction of all components of a TQ-index as depicted in Figure 9.

### Analytical Query Processing

As explained in Section 4, QET supports three types of queries: (1) a basic query; (2) an aggregation query; and (3) an affected congestion query.