The rapid development of location based services set higher demands on efficiency promotion and cost control of the services.In the paper

we propose a k-nearest neighbor query algorithm based on density grid index.In processing of the algorithm

a series of candidate search radii is obtained by utilizing of the geometrical features of the rectangle.Then the appropriate candidate search radii are chosen to make distance filtering according to the density distribution of the moving object

it is useful to achieve reducing the unnecessary accessing to memory index units and disk index units.Our extensive experiments show that the efficiency of the density grid index with our algorithm is about equal to ST

2

B-tree on the k-nearest neighbor query

but our algorithm h

as obvious advantages in the cost of I/O.