Efficient evaluation of k-NN queries using spatial mashups

Detian Zhang, Chi Yin Chow, Qing Li, Xinming Zhang, Yinlong Xu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

10 Citations (Scopus)

Abstract

K-nearest-neighbor (k-NN) queries have been widely studied in time-independent and time-dependent spatial networks. In this paper, we focus on k-NN queries in time-dependent spatial networks where the driving time between two locations may vary significantly at different time of the day. In practice, it is costly for a database server to collect real-time traffic data from vehicles or roadside sensors to compute the best route from a user to an object of interest in terms of the driving time. Thus, we design a new spatial query processing paradigm that uses a spatial mashup to enable the database server to efficiently evaluate k-NN queries based on the route information accessed from an external Web mapping service, e.g., Google Maps, Yahoo! Maps and Microsoft Bing Maps. Due to the expensive cost and limitations of retrieving such external information, we propose a new spatial query processing algorithm that uses shared execution through grouping objects and users based on the road network topology and pruning techniques to reduce the number of external requests to the Web mapping service and provides highly accurate query answers. We implement our algorithm using Google Maps and compare it with the basic algorithm. The results show that our algorithm effectively reduces the number of external requests by 90% on average with high accuracy, i.e., the accuracy of estimated driving time and query answers is over 92% and 87%, respectively.

Original languageEnglish
Title of host publicationAdvances in Spatial and Temporal Databases - 12th International Symposium, SSTD 2011, Proceedings
Pages348-366
Number of pages19
DOIs
Publication statusPublished - 19 Sep 2011
Externally publishedYes
Event12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011 - Minneapolis, MN, United States
Duration: 24 Aug 201126 Aug 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6849 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011
Country/TerritoryUnited States
CityMinneapolis, MN
Period24/08/1126/08/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this