A new distributed grid scheme and k-NN query processing for mobile objects in spatial networks

In telematics and LBS(location-based service) applications, because moving objects usually move on spatial networks, 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, called DS-GRID (distributed S-GRID), which utilizes node-based pre-computation technique to minimize the update cost of the moving objects' locations. Because our DS-GRID 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 DS-GRID, we propose two new algorithms, i.e., ICE(lncremental Cell Expansion) and MCE(Multicasting-based Cell Expansion), which minimize the number of accesses to adjacent cells during POIs retrieval in a parallel way. In addition, we present the analytical performance model of both ICE and MCS algorithms. We show from our performance analysis that both ICE and MCE algorithms are better on retrieval performance than the k-NN algorithm of the existing S-GRID.