# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 5 Timeline Query Index and Analytical Query Processing
### TQ-index Construction
#### Congestion Event Detection
When we move to the next iteration step \(i+1\)th, the new affected congestion will be added to \(RET\) again, which leads to an increase in the number of elements \(RET\) to \(i+1\). **Termination:** At the end of the iteration, the value \(i\) is equal to the size of \(C\), and the number of elements in \(RET\) would be the same as \(i\). **Correctness:** This loop invariant method proves that the algorithm will be terminated and produce the correct results. ## 6 Experimental Results

In this section, we present the performance evaluation of our QET system. ### Environment

We implemented the QET system in JAVA language using JDK version 1.8 with the maximum JVM of 4096 MB. All experiments were conducted on a commodity machine equipped with an Intel Core i5-4460 3.2 GHz Quad-Core Processor and 12 GB of main memory. To obtain sound and reliable experimental results, we repeated every test 10 times and averaged all the reported experimental results over all of the repetitions. ### Datasets

We used two real datasets in the evaluation of the QET system: (1) Busan ITS traffic sensor data; and (2) Seattle traffic sensor data. In subsequent discussions, these datasets will be referred to as \"Busan\" and \"Seattle\". The \"Busan\" dataset was collected from September 2013 to September 2015. Although the collection period was 24 months, there are some missing data for October 2013, April 2015, and November 2014. We exclude those dates to perform valid experiments, because the missing data can affect the number of congestion events. The data were collected from more than 12,000 road links, where 288 records are collected from each link per day. The amount of daily raw traffic sensor data is slightly more than eight megabytes. The total size of Busan ITS traffic is 5.6 gigabytes. The \"Seattle\" dataset is available from the Research Data Exchange [18] web site, which is a transportation data sharing system managed by the US Federal Highway Administration. The data were collected from the PeMS (Performance Measurement System), which utilized loop detectors to report volume and occupancy in fixed intervals. For our experiments, we used five-minute freeway data from Seattle which were aggregated from raw detector data. The total data size is approximately 5.2 gigabytes, ranging from May 2011 to November 2011. ### Experimental Result

To show that our system is working well and feasible, we conducted some experiments including index construction and query performance. We also show a data comparison chart to show the efficiency of the TQ-index. #### 6.3.1 Index Construction

In the first set of experiments, we evaluate the performance of the TQ-index construction. To evaluate the indexing performance, we measured (a) the total wall clock time to build the index,and (b) the index size for varying input data size. We varied the number of months from 8 to 24 in increments of four for the \"Busan\" dataset, and from two to six months in increments of one for the \"Seattle\" dataset. As explained in Section 5, TQ-index construction includes four steps: (1) location index (\(LI\)) construction; (2) timeline model (\(TM\)) extraction; (3) insertion to timeline information list (\(Til\)); and (4) insertion to time index (\(TI\)). Tables 2 and 3 summarize the performance results of these four steps. First, as we expected, total construction time increases with increasing dataset size. This is mainly because the amount of traffic congestion also increases as we vary the dataset size. Another observation is that the construction of the \"Busan\" dataset takes much more time than the construction of the \"Seattle\" dataset. The size of the \"Busan\" data is slightly bigger than the size of the Seattle data. However, the \"Busan\" dataset contains many primary roads, which contain more traffic congestion, whereas the \"Seattle\" dataset only contains traffic information on freeways.