Effective and efficient traffic data mining on sparse road networks

Abstract

A gigantic amount of traffic data, such as GPS and sensor information collected from highways, are often used to drive many road network applications, e.g., navigation, incident detection, and Point-of-Interest (POI) recommendation. Hence, topics about these ``big transportation data'' have attracted a lot of interest from both research and industry communities. A common problem about these applications is data sparsity. Specifically, each road does not have an equal amount of data. Roads that are rarely used may be associated with very few data. This can affect the effectiveness of road network applications that use them. In this thesis, we investigate how data sparsity can be taken into account, for improving the quality of the following three problems: incident detection, outlier detection, and weight completion.

First, we focus on a clustering-based approach for Incident Detection (ID) on sparse traffic data. It enables the finding of traffic incidents quickly from traffic data, thereby allowing emergency actions (e.g., rescuing injured people) to be carried out in a timely fashion. Existing ID solutions often rely on dense traffic data. We ask the question: Can ID be performed on sparse traffic data? As these data may not be enough to describe the state of the roads involved, they can undermine the effectiveness of existing ID solutions. To tackle this challenge, we borrow an important insight from the transportation literature, and use clustering to derive incident patterns. We devise a solution to detect anomalies in sparse traffic data by incident patterns. Experiments show that it is more effective on sparse traffic data, and efficient on large trajectory datasets.

Next, we study how to apply neural networks for the time-dependent trajectory outlier detection problem based on sparse traffic condition. It aims to extract abnormal movements of vehicles on the roads. This important problem, which facilities understanding of traffic behavior and detection of taxi fraud, is challenging due to the varying traffic conditions at different times and locations. To tackle this problem, we propose the deep-probabilistic-based outlier detection algorithm. This method, which employs deep-learning methods to obtain time-dependent outliners from a huge volume of trajectories, can handle complex traffic conditions and detect outliners accurately. Experiments show that our method is more accurate, and can handle millions of trajectories.

Finally, we utilize neural networks for the stochastic weight completion on sparse road networks. Road network applications make extensive use of network edge weights (e.g., traveling times). Some of these weights can be missing, especially in a road network where traffic data may not be available for every road. We study the stochastic weight completion problem, which computes the weight distributions of missing road edges. This is difficult, due to the intricate temporal and spatial correlations among neighboring edges. To tackle these challenges, we propose to incorporate the contextual properties about the road network (e.g., speed limits, number of lanes, road types) to provide finer granularity of road correlations. Experiments show that it is more effective and efficient than state-of-the-art solutions.