Efficient Processing of Moving k-Range Nearest Neighbor Queries in Directed and Dynamic Spatial Networks

Abstract EN

A k-range nearest neighbor (kRNN) query in a spatial network finds the k closest objects to each point in the query region.

The essential nature of the kRNN query is significant in location-based services (LBSs), where location-aware queries with query regions such as kRNN queries are frequently used because of the issue of location privacy and the imprecision of the associated positioning techniques.

Existing studies focus on reducing computation costs at the server side while processing kRNN queries.

They also consider snapshot queries that are evaluated once and terminated, as opposed to moving queries that require constant updating of their results.

However, little attention has been paid to evaluating moving kRNN queries in directed and dynamic spatial networks where every edge is directed and its weight changes in accordance with the traffic conditions.

In this paper, we propose an efficient algorithm called MORAN that evaluates moving k-range nearest neighbor (MkRNN) queries in directed and dynamic spatial networks.

The results of a simulation conducted using real-life roadmaps indicate that MORAN is more effective than a competitive method based on a shared execution approach.