TY - GEN
T1 - Efficient evaluation of k-NN queries using spatial mashups
AU - Zhang, Detian
AU - Chow, Chi Yin
AU - Li, Qing
AU - Zhang, Xinming
AU - Xu, Yinlong
PY - 2011/9/19
Y1 - 2011/9/19
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80052727585&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22922-0_21
DO - 10.1007/978-3-642-22922-0_21
M3 - Conference article published in proceeding or book
AN - SCOPUS:80052727585
SN - 9783642229213
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 348
EP - 366
BT - Advances in Spatial and Temporal Databases - 12th International Symposium, SSTD 2011, Proceedings
T2 - 12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011
Y2 - 24 August 2011 through 26 August 2011
ER -