Finding the Most Accessible Locations: Reverse Path Nearest Neighbor Query in Road Networks

In this paper, we propose and investigate a novel spatial query called Reverse Path Nearest Neighbor (R-PNN) search to find the most accessible locations in road networks. Given a trajectory data-set and a list of location candidates spec-ified by users, if a location o is the Path Nearest Neighbor (PNN) of k trajectories, the influence-factor of o is defined as k and the R-PNN query returns the location with the highest influence-factor. The R-PNN query is an extension of the conventional Reverse Nearest Neighbor (RNN) search. It can be found in many important applications such as ur-ban planning, facility allocation, traffic monitoring, etc. To answer the R-PNN query efficiently, an effective trajectory data pre-processing technique is conducted in the first place. We cluster the trajectories into several groups according to their distribution. Based on the grouped trajectory data, a two-phase solution is applied. First, we specify a tight search range over the trajectory and location data-sets. The effi-ciency study reveals that our approach defines the minimum search area. Second, a series of optimization techniques are adopted to search the exact PNN for trajectories in the can-didate set. By combining the PNN query results, we can retrieve the most accessible locations. The complexity anal-ysis shows that our solution is optimal in terms of time cost. The performance of the proposed R-PNN query processing is verified by extensive experiments based on real and syn-thetic trajectory data in road networks