A Safe-Region Approach to k-RNN Queries in Directed Road Network

In road networks, k-Range Nearest Neighbor (kRNN) queries locate the k-nearest neighbors for every point on the road segments that are within a given query region, based on the network distance. This is an important task, because the user´s location information may not be accurate, furthermore, users may be unwilling to reveal their exact location for privacy reasons. Therefore, in this specific situation, evaluating the query result at each point and communicating with the server will create a significant communication burden for the client. We propose an efficient approach that computes a safe segment region for each inside road segment, such that the client is not required to evaluate the query answer returned by the LBS (location-based server) within the safe region. In addition, our safe region-based query processing algorithm is designed for a directed road network, where each road network has a particular orientation. In contrast, previous kRNN research produced algorithms that operated only in undirected road networks.