Voronoi-based Range-kNN search with Map Grid in a mobile environment

Mobile Computing, which attracts a large amount of users, allows users to access mobile information services through spatial queries. For this large group of mobile users, they are expecting more efficient information services, which requires the query results to be retrieved in a short time period. In this paper, we propose an efficient Voronoi-based Range-kNN search algorithm with constructing a Map Grid (MG). With MG, the query range can be derived in a short time period even when the mobile user is moving, as well as finding the first nearest neighbours for the Range-kNN query. Then for searching the objects outside the query range, a Voronoi-based algorithm is used. We have proved that our algorithm is more efficient than Range-kNN algorithms which use irregular polygons or even irregular shapes as the query range. Meanwhile, in the evaluation part, the overall performance of our search algorithm is proved to be quite efficient.