I. Introduction
With the rapid development of positioning technology (like high accuracy), mobile equipments (like smart phones and navigators), wireless networks (like 4G and WiFi)and location-based services (like Google Maps, AMap, Uber and Foursquare), the shortest path query in road networks becomes more and more popular and important in our daily lives, such as finding the shortest route from my home to the airport through Google Maps, calling the nearest taxi by Uber and so on. However, when there are a large number of path queries arrived concurrently or in a short while, a location-based service (LBS)provider has to endure a high workload and then may lead to a long response time to users. For example, based on the report of AMap
http://www.sohu.com/a/116158205_475389
, it processed nearly 2 billion path queries in total during the National Day holiday of China in 2016, i.e., more than 3,300 queries per second.