A new distributed grid structure for k-NN query processing algorithm based on incremental cell expansion in LBSs

To manage the frequent updates of moving objects' locations on road networks in an efficient way, we propose a new distributed grid scheme which utilizes node-based pre-computation technique to minimize the update cost of the moving objects' locations. Because our distributed grid scheme manages spatial network data separately from the POIs (Point of Interests) and moving objects, it can minimize the update cost of the POIs and moving objects. To process k-nearest neighbor (k-NN) query in our distributed grid scheme, we propose a k-NN query processing algorithm based on Incremental cell expansion which minimize the number of accesses to adjacent cells during POIs retrieval in a parallel way. Finally, we show from our performance analysis that our algorithm is better on retrieval performance than the k-NN algorithm of the existing work.