Bidirectional search for nearest neighbors queries over road networks

Abstract

The present work studies the k nearest neighbors queries in static road networks, considering Volatile Points of Interest (VPoI). This new type of PoI has a high frequency of location update on a map and its availability is uncertain. Car-sharing applications are a good example of this kind of query use: drivers can become available or unavailable at any time to accept a call or have their locations changed frequently. Previous solutions use spatial indexes or require a preprocessing phase in the algorithm, making their use with VPoI’s not feasible since if one of these objects becomes available or unavailable, preprocessing or indexing should be redone. The proposed solution uses a combination of the A* algorithm with a bidirectional search, directing an expansion of the vertices as well as reducing the processing time of the query. Search space pruning techniques are also applied to reduce the amount of potential VPoI’s to be scanned. The correctness and construction of the algorithm are presented, as well as an empirical experimental evaluation with real road networks.