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 language | English |
---|---|
Pages (from-to) | 259-287 |
Number of pages | 29 |
Journal | Distributed and Parallel Databases |
Volume | 31 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jun 2013 |
Externally published | Yes |
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