ROAM: A Fundamental Routing Query on Road Networks with Efficiency

Abstract

Novel road-network applications often recommend a moving object (e.g., a vehicle) about interesting services or tasks on its way to a destination. A taxi-sharing system, for instance, suggests a new passenger to a taxi while it is serving another one. The traveling cost is then shared among these passengers. A fundamental query is: given two nodes s and t , and an area A on road network graph G , is there a 'good' route (e.g., short enough path) P from s to t that crosses A in G ? In a taxi-sharing system, s and t can be a taxi's current and destined locations, and A contains all the places to which a person waiting for a taxi is willing to walk. Answering this Route and Area Matching (ROAM) Query allows the application involved to recommend appropriate services to users efficiently. In this paper, we examine efficient ROAM query algorithms. Particularly, we develop solutions for finding a ρ -route, which is an s - t path that passes A , with a length of at most (1+ρ) times the shortest distance between s and t . The existence of a ρ -route implies that a service or task located at A can be found for a given moving object m , and that m only deviates slightly from its current route. We present comprehensive studies on index-free and index-based algorithms for answering ROAM queries. Comprehensive experiments show that our algorithm runs up to 30 times faster than baseline algorithms.