TY - GEN
T1 - Edge-based shortest path caching for location-based services
AU - Zhang, Detian
AU - Liu, An
AU - Jin, Gaoming
AU - Li, Qing
PY - 2019/7
Y1 - 2019/7
N2 - Shortest path queries on road networks are widely used in location-based services (LBS), e.g., finding the shortest route from my home to the airport through Google Maps. However, when there are a large number of path queries arrived concurrently or in a short while, an LBS provider (e.g., Google Maps) has to endure a high workload and then may lead to a long response time to users. Therefore, path caching services are utilized to accelerate large-scale path query processing, which try to store the historical path results and reuse them to answer the coming queries directly. However, most of existing path caches are organized based on nodes of paths; hence, the underlying road network topology is still needed to answer a path query when its querying origin or destination lies on edges. To overcome this limitation, we propose an edge-based shortest path cache in this paper that can efficiently handle queries without needing any road information, which is much more practical in the real world. We achieve this by designing a totally new edge-based path cache structure, an efficient R-tree-based cache lookup algorithm, and a greedy-based cache construction algorithm. Extensive experiments on a real road network and real point-of-interest datasets are conducted, and the results show the efficiency, scalability, and applicability of our proposed caching techniques.
AB - Shortest path queries on road networks are widely used in location-based services (LBS), e.g., finding the shortest route from my home to the airport through Google Maps. However, when there are a large number of path queries arrived concurrently or in a short while, an LBS provider (e.g., Google Maps) has to endure a high workload and then may lead to a long response time to users. Therefore, path caching services are utilized to accelerate large-scale path query processing, which try to store the historical path results and reuse them to answer the coming queries directly. However, most of existing path caches are organized based on nodes of paths; hence, the underlying road network topology is still needed to answer a path query when its querying origin or destination lies on edges. To overcome this limitation, we propose an edge-based shortest path cache in this paper that can efficiently handle queries without needing any road information, which is much more practical in the real world. We achieve this by designing a totally new edge-based path cache structure, an efficient R-tree-based cache lookup algorithm, and a greedy-based cache construction algorithm. Extensive experiments on a real road network and real point-of-interest datasets are conducted, and the results show the efficiency, scalability, and applicability of our proposed caching techniques.
KW - Caching services
KW - Large-scale
KW - Location based-services
KW - Path cache
KW - Shortest path queries
UR - http://www.scopus.com/inward/record.url?scp=85072761288&partnerID=8YFLogxK
U2 - 10.1109/ICWS.2019.00060
DO - 10.1109/ICWS.2019.00060
M3 - Conference article published in proceeding or book
AN - SCOPUS:85072761288
T3 - Proceedings - 2019 IEEE International Conference on Web Services, ICWS 2019 - Part of the 2019 IEEE World Congress on Services
SP - 320
EP - 327
BT - Proceedings - 2019 IEEE International Conference on Web Services, ICWS 2019 - Part of the 2019 IEEE World Congress on Services
A2 - Bertino, Elisa
A2 - Chang, Carl K.
A2 - Chen, Peter
A2 - Damiani, Ernesto
A2 - Damiani, Ernesto
A2 - Goul, Michael
A2 - Oyama, Katsunori
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 26th IEEE International Conference on Web Services, ICWS 2019
Y2 - 8 July 2019 through 13 July 2019
ER -