# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 5 Timeline Query Index and Analytical Query Processing
### TQ-index Construction
#### Congestion Event Detection
In this subsection, we explain how to process queries by exploiting the structure of a TQ-index. #### 5.3.1 Basic Query Processing

In this subsection, we present how QET exploits a TQ-index for the efficient processing of a basic query. Figure 13 depicts the overview of basic query processing. A user specifies parameters of a query \(Q_{1}\) and returns the timeline model including information about traffic congestion in chronological order. This result is visualized as a timeline view in a web browser. The basic query processing algorithm that identifies the congestion events in specified road links within the given time range is presented in Algorithm 6. A basic query utilizes the location index (\(LI\)) of a TQ-index to find specified road links from road networks (line 4). Then, the query obtains a time index (\(TI\)) of the location for locating the _Daily Event References_\((DER)\) at the given start date (line 5). Once we obtain the starting event (line 6), we can linearly scan the _Event Time References_\((ETR)\) through lines 7 to 11. While scanning, we collect a set of related traffic congestion and events that appear within the given start time and end time of the timeline model (line 9). Figure 13: Basic query processing. ```
1:Input A TQ-index \(tqi\), a set of LinkIDs \(L\), a start time \(t_{start}\), an end time \(t_{end}\) Output: A timeline model \(TM\)
2:procedureBasicQueryProcessing(\(tqi\), \(L\), \(t_{start}\), \(t_{end}\))
3:\(TM\)\(\leftarrow\) NULL;
4:foreach LinkID lid in \(L\)do
5: Road Segment \(l\)\(\leftarrow\)\(tqi\)LocationIndex.Find(\(lid\));
6: DailyEventReferences \(der\)\(\leftarrow\)\(l\).TimelIndex.GetDER(DayOf(\(t_{start}\)));
7: EventTimeReferences \(cursor\)\(\leftarrow\)\(der\).FirstDailyLocalEvent;
8:while\(cursor\).GetNext() AND \(cursor\).\(t\)\(\leq\)\(t_{end}\)do
9:if\(cursor\).\(e.t\)\(\geq\)\(t_{start}\)then
10: TM.AddConges(\(cursor\).\(e\));
11:endif
12:endwhile
13:endforeach
14:return\(TM\);
```
**Algorithm 6**Basic Query Processing

**Example 7**. : _Assume that a user specifies identifying congestion events that occur in road link \(L_{3}\) from day \(2\) to day \(3\). Figure 14 explains how a TQ-index is exploited during the basic query processing. First, we find the road link \(L_{3}\) in Location 1 ndex LI (step 1). Then, following the pointer of \(L_{3}\), we access the Time \(Index\) TI to locate the DailyEventReferences (step 2). In this case, we obtain the starting date point \(day\)\(2\) from DailyEventReferences (step 3). From this list, we can start to scan linearly \(EventTimeReferences\) until we meet the time greater than day \(3\). While scanning, we also collect a set of traffic congestion and events as a timeline model (step 4)._

To prove the correctness of Algorithm 6, we use the loop invariant technique [47]. This approach examines the correctness of the algorithm in three loop stages: (1) initialization; (2) maintenance; and (3) termination. **Theorem 4**. : _With a given start time \(t_{start}\) and an end time \(t_{end}\) as input parameters of a query and a cursor as a pointer to trace EventTimeReferences, algorithm Basic Query Processing is correct with this loop invariant: for

Figure 14: Basic query steps. any step in the inner loop, this statement is applied: \(t_{start}~{}\leq~{}\mathit{cursor.t}~{}~{}<~{}t_{end}\), otherwise, the value of the cursor will be more than \(t_{end}\) or it is NULL._

Proof. : **Inner Loop:** Before an iteration is started, a TQ-index \(tqi\) is already constructed, and \(LI\) is the LocationIndex of the TQ-index \(tqi\). For each \(lid\) that is defined in the outer loop, the algorithm will find corresponding events that started between \(t_{start}\) and \(t_{end}\). **Initialization:** When the iteration begins by exploiting the time index \(TI\) of \(tqi\), \(\mathit{cursor}\) is supposed to be the first node whose time value (denoted as \(\mathit{cursor.t}\)) is between the given date range \(t_{start}\) and \(t_{end}\). Otherwise, \(\mathit{cursor}\) is supposed to be \(\mathit{NULL}\).