A new distributed grid scheme utilizing node-based preprocessing technique for supporting k-NN queries in location-based services

Because moving objects usually move on spatial networks in location-based service applications, their locations are updated frequently, leading to the degradation of retrieval performance. To manage the frequent updates of moving objects’ locations 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 grid scheme manages spatial network data separately from the POIs (Point of Interests) and moving objects, it can mini- mize the update cost of the POIs and moving objects. Using our grid scheme, we propose a new k-nearest neighbor (k-NN) query processing algorithm which mini- mizes the number of accesses to adjacent cells during POIs retrieval in a parallel way. Finally, we show from our performance analysis that our k-NN query pro- cessing algorithm is better on retrieval performance than that of the existing S-GRID.