# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 5 Timeline Query Index and Analytical Query Processing
### TQ-index Construction
#### Congestion Event Detection
**Maintenance:** Suppose that at the \(i\)th iteration, the cursor is at position \(j\) of LocalEventReferences and \(\mathit{cursor.t}\) of \(\mathit{cursor_{j}}\) is still between \(t_{start}\) and \(t_{end}\). Then, because the long node at \(j+1\) position exists and the \(\mathit{cursor.t}<~{}t_{end}\), we can update the cursor to position \(j+1\). **Termination:** Because \(\mathit{cursor}\) is a pointer that points the sorted elements of EventTimeReferences, there will always be the end of EventTimeReferences. At the end of the iteration, \(\mathit{cursor}\) could be \(\mathit{NULL}\) when it passes the end of EventTimeReferences, or the time of the cursor would satisfy the condition \(\mathit{cursor.t}~{}~{}>~{}t_{end}\) when it passed the matched elements of EventTimeReferences. **Correctness:** At the end of the iteration (after termination), \(\mathit{cursor}\) would be \(\mathit{NULL}\) or the \(\mathit{cursor.t}\), which is greater than \(t_{end}\), trivially. #### 5.3.2 Aggregation Query Processing

An aggregate function is a function that needs a grouping of the values of multiple rows together to provide a single value. Our QET system supports the common aggregate functions, such as SUM, MIN, MAX, COUNT, and AVG for the traffic analytical queries. For example, query \(Q_{2}\) in Section 1 needs to calculate COUNT values to find the amount of congestion on each road segment in a day and then apply MAX function to the count values. In this case, we use a road segment ID and date as the key for grouping. Another example is query \(Q_{3}\) in Section 1, which needs to keep the longest duration of congestion in a day by applying the MAX function. Algorithm 7 describes the detailed steps for aggregation query processing. This algorithm begins by obtaining a timeline model from basic query processing (line 2). Then, we retrieve a list of traffic congestion from the timeline model (line 3). There are two iterations in the next steps. The first iteration groups congestion list \(C\) based on the given key (lines 5 to 8). Then, the second iteration invokes AggregateFunction with a grouped set of congestion events as the parameter. The result of this function is aggregated values of the given set of congestion added into the aggregated value list (lines 10 to 13). Then, we sort the aggregated value list and return this list as the output of the algorithm. ```
Input: A TQ-index \(tqi\), a set of LinkIDs \(L\), a start time \(t_{start}\), an end time \(t_{end}\), combined aggregation keys key Output: A set of aggregated value \(A\)
1 procedureAggregationQueryProcessing(\(tqi\),\(L\),\(t_{start}\), \(t_{end}\), key)
2 A timeline model \(TM\leftarrow\) BasicQueryProcessing(\(tqi\),\(L\),\(t_{start}\), \(t_{end}\));
3 A set of traffic congestions \(C\leftarrow\) GetCongestations(\(TM\));
4\(H\leftarrow\) new HashMap(key:String, value:List); // Grouping
5 foreach Congestion \(c\) in \(C\)do
6 A group of congestions \(gr\gets H\).GetOrInsert(\(key\));
7\(gr\).Add(\(c\));
8 end foreach
9 Initialize Aggregated Value List \(A\); // Compute aggregated values for each group in \(H\)
10 foreach Group of congestions \(gr\) in \(H\)do
11 Aggregated Value \(av\leftarrow\) AggregateFunction(\(gr\));
12\(A\).add(\(av\));
13 end foreach
14 Sort(\(A\));
15 return\(A\);
```
**Algorithm 7**Aggregation Query Processing

**Example 8**. : _Figure 15 describes aggregation query processing. We obtain a timeline model containing a list of traffic congestion events \(C\) by invoking BasicQueryProcessing. The elements of \(C\) are \(c_{1}\), \(c_{2}\), \(c_{3}\), \(c_{4}\), and \(c_{5}\). Next, we apply the grouping to \(C\) to obtain hashmap \(H\) as a result. The Hashmap \(H\) contains only two elements: \(L_{1}\)\(<\)\(c_{1}\), \(c_{3}\), \(c_{4}\)\(>\) and \(L_{2}\)\(<\)\(c_{2}\), \(c_{5}\)\(>\). Then, we pass \(H\) into a COUNT aggregation function. The result shows the number of congestion events for each group in \(H\).