An Effective Spatial Mashup Framework for K-nearest-Neighbor Queries in Time-Dependent Road Networks

Abstract

Spatio-temporal queries have been widely used in location-based services (LBS). Despite the importance of travel time in road networks, the distance measure of traditional spatio-temporal queries for LBS, e.g., k-nearest-neighbor (k-NN), is mostly based on Euclidean or network distance between two locations, which can not reflect the real travel time. In this thesis, we focus on k-NN queries, in time-dependent road networks, where the travel time between two locations may vary significantly at different time of the day. In practice, it is costly for an LBS provider to collect real-time traffic data from vehicles or roadside sensors to compute the best route from a user to a spatial object of interest in terms of the travel time. Thus, we design a server-side spatial mashup framework that enables an LBS provider to efficiently evaluate spatio-temporal queries using the route information and travel time accessed from an external Web mapping service, e.g., Microsoft Bing Maps, Google Maps, MapQuest Maps, Yahoo! Maps, Baidu Maps and so on. Due to the expensive cost and limitations of retrieving such external information, we propose pruning, grouping, direction sharing and parallel requesting optimizations to reduce the number of external Web mapping requests and user query response time, and integrate them into k-NN queries using spatial mashups. We evaluate each proposed query algorithm by using Google/Bing/MapQuest Maps, a real road network, real data sets, and synthetic data sets. Experimental results show that our proposed algorithms are efficient and capable of producing highly accurate query answers with low number of external requests and user query response time.

Date of Award	7 May 2014
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Qing LI (Supervisor)