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

D. Zhang, C.-Y. Chow, Qing Li, X. Zhang, Y. Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

© 2016 IEEE. 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.
Original languageEnglish
Article number7286782
Pages (from-to)2428-2442
Number of pages15
JournalIEEE Transactions on Computers
Volume65
Issue number8
DOIs
Publication statusPublished - 1 Aug 2016
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this