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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

12 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number7286782
Pages (from-to)2428-2442
Journal / PublicationIEEE Transactions on Computers
Volume65
Issue number8
Publication statusPublished - Aug 2016

Abstract

Although the travel time is the most important information in road networks, many spatial queries, e.g., κ-nearest-neighbor ( κ-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 M ashup Service (SMS) that enables the LBS provider to efficiently evaluate κ-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 κ-NN queries. We first discuss how the SMS processes a single κ-NN query using two optimizations, namely, direction sharing and parallel requesting. Then, we extend them to process multiple concurrent κ-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.

Research Area(s)

  • location-based services, road networks, Spatial mashups, web mapping services, κ-NN queries

Citation Format(s)

A Spatial Mashup Service for Efficient Evaluation of Concurrent κ-NN Queries. / Zhang, Detian; Chow, Chi-Yin; Li, Qing; Zhang, Xinming; Xu, Yinlong.

In: IEEE Transactions on Computers, Vol. 65, No. 8, 7286782, 08.2016, p. 2428-2442.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal