Abstract
Urban computing refers to the use of information and communication technologies (ICT) to acquire and analyze the data of an urban space in order to solve the many issues caused by rapid urbanization, such as air pollution, traffic congestion, and waste management. Besides infrastructural sensors, urban computing often relies on vehicles running on the roads to help collecting data relevant to the urban space. It is important to predict their routes so that data collection tasks can be planned in advance. As roads are joined by crossroads, the problem then becomes that of predicting the turns of vehicles on entering the crossroads. The problem is complicated by the fact that the turn prediction often has to be made several blocks ahead so that data collection tasks can be scheduled in time. A general model that predicts the turn of a vehicle on approaching a crossroad is thus needed. Furthermore, as the number of crossroads in a city is normally large, it is inefficient to build a model for each crossroad. A technique that derives the turn model of a crossroad from those of the neighboring crossroads is thus interesting and useful. In this thesis, we address the above two issues. We first propose the Turn Prediction Model (TPM), which predicts in advance the turns of vehicles on entering a crossroad using machne learning techniques and information such as route history and time of day. Based on TPM, we then propose the Center-Deduced Technique (CDT) to derive the TPM of a crossroad from the TPMs of the neighboring crossroads. In this way, we only need to build and store the TPMs for a small number of crossroads while others can be derived using CDT. Perforamnces of the proposed techniques are evaluated using real-world road traces and the results demonstrate their effectiveness.