Optimal Route Queries with Arbitrary Order Constraints

Given a set of spatial points DS, each of which is associated with categorical information, e.g., restaurant, pub, etc., the optimal route query finds the shortest path that starts from the query point (e.g., a home or hotel), and covers a user-specified set of categories (e.g., {pub, restaurant, museum}). The user may also specify partial order constraints between different categories, e.g., a restaurant must be visited before a pub. Previous work has focused on a special case where the query contains the total order of all categories to be visited (e.g., museum - restaurant - pub). For the general scenario without such a total order, the only known solution reduces the problem to multiple, total-order optimal route queries.

Provided by: Institute of Electrical & Electronic Engineers Topic: Data Management Date Added: May 2013 Format: PDF

Find By Topic