Edge-Based Shortest Path Caching for Location-Based Services
Title | Edge-Based Shortest Path Caching for Location-Based Services |
Publication Type | Conference Paper |
Year of Publication | 2019 |
Authors | Zhang, Detian, Liu, An, Jin, Gaoming, Li, Qing |
Conference Name | 2019 IEEE International Conference on Web Services (ICWS) |
Keywords | cache storage, caching services, edge-based path cache structure, edge-based shortest path cache, edge-based shortest path caching, Google Maps, graph theory, greedy algorithms, greedy-based cache construction algorithm, historical path results, large-scale, large-scale path query processing, location based services, location based-services, location-based services, Metrics, path cache, path caches, path caching services, pubcrawl, query processing, querying origin, R-tree-based cache lookup algorithm, resilience, Resiliency, road network topology, Scalability, shortest path queries, shortest route, tree data structures, Web Caching |
Abstract | 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. |
DOI | 10.1109/ICWS.2019.00060 |
Citation Key | zhang_edge-based_2019 |
- location-based services
- Web Caching
- tree data structures
- shortest route
- shortest path queries
- Scalability
- road network topology
- Resiliency
- resilience
- R-tree-based cache lookup algorithm
- querying origin
- query processing
- path caching services
- path caches
- path cache
- Metrics
- pubcrawl
- location based-services
- location based services
- large-scale path query processing
- large-scale
- historical path results
- greedy-based cache construction algorithm
- greedy algorithms
- graph theory
- Google Maps
- edge-based shortest path caching
- edge-based shortest path cache
- edge-based path cache structure
- caching services
- cache storage