We show that partition-based algorithms developed for point-to-point shortest path computations can be naturally extended to handle augmented queries such as finding the closest restaurant or the best post office to stop on the way home, always ranking POIs according to a user-defined cost function. Our solution allows different trade-offs between indexing effort (time and space) and query time. Our most flexible variant allows the road network to change frequently (to account for traffic information or personalized cost functions) and the set of POIs to be specified at query time. We show that multilevel overlays are extremely practical for finding the closest POI, even in an online version (with no index). In the offline case (when indexing is allowed), although slower than the best hierarchical methods, multilevel overlays are still fast enough and have much lower space overhead. Finally, we present the first practical approach for finding the best via node on dynamic continental road networks with tens of thousands of candidate POIs. While CRP can handle changes to the cost function in a second or less, hierarchical methods may take hours. Even in this fully dynamic scenario, our solution is fast enough for interactive applications on continental road networks.
You are here: / / A Unified Framework For Dealing With Exact Point-Of-Interest Queries In Dynamic Continental Road Networks