Group Processing of Simultaneous Shortest Path Queries in Road Networks

The recent advancement of GPS-enabled mobile technologies and the proliferation of map-based applications are attracting an increasing number of people to use location based services (LBSs). Processing a larger number of simultaneous queries efficiently have become an important research topic in recent years. In this paper, we focus on an important class of LBSs, shortest path queries (SP-queries) in road networks. Given a source and a destination in a road network, an SP-query returns the path from the source to the destination that minimizes the travel time. We particularly focus on batch processing of simultaneous SP-queries in road networks. Traditional systems that process one query at a time usually provide slow responses, causing the machine to flood with incoming queries. Existing fast solutions for SP-queries require expensive pre-processing steps and are incapable of adapting with the continuous change in traffic on the roads. We propose an efficient group based approach that provides an approximate solution with reduced cost and high accuracy. An important benefit of our approach is that it does not require expensive pre-processing. The key concept is to exploit the path-coherence property of road networks by grouping queries that share substantial common paths in their shortest paths and processing the group in a single pass. Our approach incurs an average relative error of 0.5% and is on average 6 times faster than the straightforward approach that evaluates each SP-query individually.