Customizable Point-Of-Interest Queries In Dynamic Continental Road Networks

Modern map services and other spatial systems must support a wide range of applications. Besides computing optimal (with respect to a cost function such as travel times or time in traffic) point-to-point routes, advanced queries like “find the closest Thai restaurant to my current location” or “what is the best place to stop for groceries on my way home” need to be supported as well. All these location services depend on a location and a set of points-of-inter-est (POIs) with certain properties (such as open times, category, or personal preferences). Given a location, we want to rank the POIs to decide which ones to report first. If one wants to order them by the actual driving (or walking) time from a given location, all these problems could be solved with one or more calls to a standard graph search algorithm, such as Dijkstra’s. For continental road net-works, however, this takes several seconds for long-range queries, too slow for interactive applications. For better performance, more sophisticated solutions are needed. We present a unified framework for dealing with exact point-of-interest (POI) queries in dynamic continental road networks within interactive applications. 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. Even in this fully dynamic scenario, our solution is fast enough for interactive applications on continental road networks.