Efficient K-NN Queries Using Spatial Mashups In Time-Dependent Road Networks

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 tra-ditional 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 dif-ferent 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, a server-side spatial mashup framework is designed 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 limita-tions 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. In summary, the main contribution of this thesis as follows:· A new framework is proposed, which uses a server-side spatial mashup paradigm for an LBS provider, by accessing travel time and direction information from Web mapping services, to process spatio-temporal queries in a time-dependent road network.· We have utilized pruning techniques to reduce the number of external requests by pruning objects that are definitely not be part of query answers, and designed an algorithm to processing k-NN queries by combining pruning techniques with network expansion algorithm.· Grouping optimizations are designed by grouping objects and users to intersec- tions based on the road network topology and user moving directions to achieve shared execution, which is a first attempt to do this kind of grouping as far as we know. This kind of grouping optimization can heavily reduce the number of external request while keeps the high accuracy of travel time and query answers.· To further reduce the number of external requests, another shared execution op-timization called direction sharing is proposed, which try to make the route be-tween a source to a destination be shared used by other sources and their corre-sponding destinations. A histogram approach is also employed to estimate the sharing ability for a route to make full utilization of the direction sharing opti-mization.· We have presented a totally new parallel requesting approach to reduce response time for a single user query, exploited inter-query cooperation and incremental processing for a system with high workload (e.g., a large number of user queries arrived concurrently or in succession), brought forth and solved the starvation problem during incremental processing.