SMashQ: Spatial mashup framework for k-NN queries in time-dependent road networks

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

25 Citations (Scopus)

Abstract

The k-nearest-neighbor (k-NN) query is one of the most popular spatial query types for location-based services (LBS). In this paper, 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 a 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 SMashQ, a server-side spatial mashup framework that enables a database server to efficiently evaluate k-NN queries using the route information and travel time accessed from an external Web mapping service, e.g.; Microsoft Bing Maps. Due to the expensive cost and limitations of retrieving such external information, we propose three shared execution optimizations for SMashQ, namely, object grouping, direction sharing, and user grouping, to reduce the number of external Web mapping requests and provide highly accurate query answers. We evaluate SMashQ using Microsoft Bing Maps, a real road network, real data sets, and a synthetic data set. Experimental results show that SMashQ is efficient and capable of producing highly accurate query answers. © 2012 Springer Science+Business Media, LLC.
Original languageEnglish
Pages (from-to)259-287
Number of pages29
JournalDistributed and Parallel Databases
Volume31
Issue number2
DOIs
Publication statusPublished - 1 Jun 2013
Externally publishedYes

Keywords

  • k-nearest-neighbor queries
  • Location-based services
  • Spatial mashups
  • Time-dependent road networks
  • Web mapping services

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Information Systems and Management

Cite this