# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 2 Related Work
### Traffic Sensor Data Analysis  
Because road traffic problems are prevalent in most countries, a variety of models exploiting historical traffic sensor data have been proposed for traffic sensor data analysis. Existing approaches can be broadly classified into three categories, namely (1) multi-dimensional spatio-temporal data approaches; (2) Markov model-based approaches; and (3) other approaches.  
In the first category, several solutions have represented traffic data in time series as multi-dimensional spatio-temporal data modeling [10; 22; 23; 24; 25]. [PERSON] et al. [22] proposed a novel floating car data analysis based on data cube modeling to explore traffic congestion patterns. [PERSON] et al. [10] assumed that traffic patterns are recurrent within a tight time frame and proposed a travel time prediction model by considering matrices on a spatial and temporal scale in a pattern matching process. [PERSON] et al. introduced a spatio-temporal congestion pattern to predict short-term traffic decongestion times [23]. A singular value decomposition (SVD) technique is used to reduce the traffic matrices to achieve an efficient query processing on road traffic data [24; 25]. Most previous works focus on finding traffic patterns over different levels of spatial-temporal dimensions by aggregating congestion event data. We focus on providing a traffic query system that enables users to track the congestion events and the affected congestion events. In addition, we identify the starting point of congestion by measuring the dependency of the congestion.  
In the second category, several traffic prediction systems are included [26; 27; 28]. [PERSON] et al. [26] used spatio-temporal hidden Markov models (STHMM) to model correlations among different traffic time series. STHMMs focus on predicting near-future travel cost and cannot provide answers for the users' queries. A 3D Markov random field was used in [27] to predict traffic flows, and uses  
Figure 1: Traffic timeline features.  
both time series analyses and geometrical correlations. A HMM-based model [28] is proposed for urban-scale traffic estimation using floating car data. Traffic condition on a road segment is considered as a hidden state that can be estimated according to the conditions of road segments of similar traffic characteristics. Note that there is a big difference between the QET system and Markov-model based systems: QET aims to provide a novel analytical query processing method based on a timeline model for road; Markov model-based systems focus on providing the estimation of traffic conditions. Thus, Markov model-based approaches cannot provide answers for the users' queries and cannot be directly applied to the QET system.  
In the final category, there are also several approaches [11; 12; 13; 29]. [PERSON] et al. [11] developed a particle filter approach that used historical data for real-time short- to medium-term travel time prediction to select particles for partial resampling. A congestion-aware route planning system [29] is proposed to achieve a social optimum of all drivers' travel time using historical taxi trip data and loop detector data. [PERSON] et al. [12] combined three data mining methods, such as K-means clustering, decision trees, and neural networks, to predict travel time with non-recurrent congestion. [PERSON] et al. [13] suggest a genetic program model that represents spatio-temporal interactions as algebraic expressions for the prediction of travel times. The result of these analytical processes provide a deep understanding of traffic behavior. However, these approaches do not support a query processing system for answering analytical questions, which is more useful to end users.