# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 5 Timeline Query Index and Analytical Query Processing
### The Index Structure  
Let \(TM=\{tl_{1},tl_{2},\ldots,tl_{n}\}\) denote the timeline model extracted from the historical traffic sensor data. As defined in Section 3.3, an element of the timeline model \(tl_{i}\) mainly represents traffic congestion information with spatio-temporal characteristics. The TQ-index consists of three key components: (1) \(LocationIndex\) (denoted by \(LI\)) representing road networks; (2) \(TimeIndex\) (denoted by \(TI\)) for fast access to daily congestion events; and (3) \(TimelineModelInformation\) (denoted by \(TMI\)) to maintain the timeline model of the road network. Figure 9 depicts the overall design of the TQ-index.  
Figure 9: TQ-index.  
\(LI\) contains a hash-based index and a graph representation of road networks, as illustrated in the left part of Figure 9. Because we focus on road segments as a spatial property of traffic information, we slightly modify the general concept of the graph representation as depicted in Figure 10. A node of a graph represents a road segment, whereas an edge of the graph illustrates a relationship between two road segments. The main reason for this modification is to optimize the tracing algorithm, because obtaining the next node is easier than obtaining the next edge in our approach.  
To facilitate fast access to the specific road segments among abundant road links, a hash-based index is provided as a crucial component of location index \(LI\). A hash key means an individual road segment and the value of the hash in a pointer to a node in the road networks. By following the next and previous pointers, we can identify the adjacent road links. In addition to the spatial information of the road network, a _node_ on the graph also has a pointer to \(TI\).  
\(TI\) enables us to quickly locate time-specified congestion by checking the first event on that day and scanning the local events linearly. Thus, each element of \(TI\) is connected from each vertex of \(LI\). \(TI\) mainly consists of two linked lists: (1) a daily event reference (\(DER\)) list and (2) an event time reference (\(ETR\)) list. The \(DER\) is a list of nodes, and each node of \(DER\) represents a day's information, which is connected to the node of a local event reference (\(LER\)) list. An \(ETR\) list represents all event times for a road link. Each element of the \(ETR\) list is connected to a node of \(TMI\). By combining \(DER\) and \(ETR\), we can effectively identify the daily congestion events of a road segment.  
\(TMI\) stores the timeline model information of the road network. As explained in Definition 7, the \(TMI\) consists of two lists : (1) a \(CongestionEventList\) to store a set of congestion events; and (2) a \(CongestionList\) to include a set of congestions. Because both \(CongestionEventList\) and \(CongestionList\) will contain a huge volume of timeline model information, the TQ-index has two indexes (such as \(LI\) and \(TI\)) to quickly identify a specified congestion or congestion event information. This relation is denoted as pointers in Figure 9.