|
Title:
|
NEW QUERY PROCESSING ALGORITHMS FOR MOVING OBJECTS IN LOCATION-BASED SERVICES |
|
Author(s):
|
Jae-woo Chang , Hyun-jo Lee , Yong-ki Kim , Young-chang Kim , Ji-hee Kim |
|
ISBN:
|
978-972-8924-30-0 |
|
Editors:
|
Nuno Guimarães and Pedro Isaías |
|
Year:
|
2007 |
|
Edition:
|
Single |
|
Keywords:
|
Query processing algorithms, location-based services, range query, k-NN query, spatial network databases |
|
Type:
|
Full Paper |
|
First Page:
|
305 |
|
Last Page:
|
311 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
In this paper, we propose new query processing algorithms for moving objects on road network in location-based services, for such typical spatial queries as range and k nearest neighbors (k-NN) ones. Our query processing algorithms can reduce the computation time of network distance between a pair of nodes and the number of disk I/Os required for accessing nodes by using a materialization-based technique with the shortest network distances of all the nodes in the road network. It is shown that our range query processing algorithm achieves about up to one order of magnitude better performance than the Euclidean restriction and the network expansion algorithms proposed by Papadias et al. In addition, our k-NN query processing algorithm achieves about up to 170~400% performance improvement over the network expansion algorithm, while it shows about up to one order of magnitude better performance than the Euclidean restriction algorithm. |
|
|
|
|
|
|
