# Querying and Extracting Timeline Information from Road Traffic Sensor Data
## 1 Introduction  
Traffic congestion is one of the most prevalent transport problems in cities. Heavy traffic congestion can have many effects, such as delays, unpredictable travel times, increased fuel consumption, and road rage. For example, the total annual delay in travel time was around 13 billion people hours from the year 2010 to the year 2014, which consumed around six million tons of excess fuel in urban areas of the US [1]. Many countries use intelligent transportation systems (ITSs) to provide integrated road traffic-related services. ITS centers collect and store road traffic sensor data (occasionally, we use the terms \"traffic sensor data\" and \"traffic data\" interchangeably) from multiple heterogeneous sources, and mainly focus on providing real-time traffic information to alleviate the problems caused by traffic congestion. A Busan ITS center in South Korea captures traffic data every five minutes for each road link (road segment) and focuses on providing real-time traffic information. The traveler's information website of Seattle provides real-time traffic conditions and travel times throughout the city. Most traffic information services are based on data collected by ITS systems. PeMS [2], Highway England [3], Daum Map [4], Naver Map [5], and Here Map [6] offer more complete features based on ITS traffic data. In addition to ITS-generated data, several approaches also use crowd-sourced data to provide real-time traffic information [7; 8; 9]. Continuous historical traffic sensor data is generated once the real-time use of these data is complete. By utilizing archived historical traffic data, researchers find valuable insights, such as travel time predictions [10; 11; 12; 13], traffic bottleneck analysis [14], and survival analysis [15]. While existing applications can efficiently provide limited analysis results, they are unable to cope with several types of analytical queries. In real life, there are many demands from citizens concerning traffic patterns on certain days or duration in traffic and changes in roads. For example, inhabitants of urban areas typically have analytical questions concerning road traffic behaviors, such as:  
* \(Q_{1}\): What types of congestion events occurred on Broadway Avenue (a road) last week? * \(Q_{2}\): Which road links are the most congested on a certain day? * \(Q_{3}\): Where is the heaviest congestion on a certain day? * \(Q_{4}\): If Broadway becomes congested, which other roads are affected? This demand for specifically analyzed traffic information suggests the need for an interactive traffic query system which plays a key role in semantic applications for smart cities [16]. Motivated by these considerations, we investigate how to design an efficient road traffic analytical query system by exploiting historical traffic data. There are three critical challenges that arise in the design of such a system. They are: (1) how to model traffic information for interactive analytic queries; (2) how to facilitate the modeled traffic information for efficient query processing; and (3) how to provide intuitive visualization for the traffic query system. To address the above challenges, we propose a QET (querying and extracting timeline information) system, a novel system that facilitates effective analytical query processing based on a timeline model for road traffic sensor data. First, we devise an intuitive timeline model that can be used to capture the standard design as well as the spatio-temporal features of road traffic sensor data. In the QET construction phase, we extract timeline information from raw traffic sensor data by detecting the congestion events and obtaining some analytical information, such as an event's dependency and the affectedness. Second, to enable efficient query processing over timeline information, we propose a TQ-index (timeline query index), which is an in-memory data structure that exploits spatio-temporal features of timeline modeling.