1A Spatial Mashup Service for Efficient Evaluation of Concurrent k-NN Queries

Abstract—Although the travel time is the most important information in road networks, many spatial queries, e.g., k-nearest-neighbor (k-NN) and range queries, for location-based services (LBS) are only based on the network distance. This is because it is costly for an LBS provider to collect real-time traffic data from vehicles or roadside sensors to compute the travel time between two locations. With the advance of web mapping services, e.g., Google Maps, Microsoft Bing Maps, and MapQuest Maps, there is an invaluable opportunity for using such services for processing spatial queries based on the travel time. In this paper, we propose a server-side Spatial Mashup Service (SMS) that enables the LBS provider to efficiently evaluate k-NN queries in road networks using the route information and travel time retrieved from an external web mapping service. Due to the high cost of retrieving such external information, the usage limits of web mapping services, and the large number of spatial queries, we optimize the SMS for a large number of k-NN queries. We first discuss how the SMS processes a single k-NN query using two optimizations, namely, direction sharing and parallel requesting. Then, we extend them to process multiple concurrent k-NN queries and design a performance tuning tool to provide a trade-off between the query response time and the number of external requests and more importantly, to prevent a starvation problem in the parallel requesting optimization for concurrent queries. We evaluate the performance of the proposed SMS using MapQuest Maps, a real road network, real and synthetic data sets. Experimental results show the efficiency and scalability of our optimizations designed for the SMS. Index Terms—Spatial mashups, location-based services, k-NN queries, web mapping services, road networks