Shortest Paths Caching Algorithms And Optimization Approaches For Location-based Services

With the rapid development of computer software technology and Internet technology, the degree of global information has been improved further. Especially in recent years, with the rapid development of mobile terminal technology, wireless network technology and mobile communication technology, the development of mobile Internet has been promoted vigorously and rapidly. The demand for getting information quickly and efficiently is more and more intense in people’s daily life, which also prompts the rapid development of location-based services (LBS). As a basic location-based service, the shortest path query on road network has attracted more and more attentions. As an important part of network search engines, web cache can reduce query response time efficiently to improve the efficiency of search engine. Improving hit ratio of shortest path query on limited cache has become an important issue of shortest path query web services.At present, existing caching techniques for the shortest path query can be divided into two categories:static caching techniques and dynamic caching techniques. Dynamic caching updates the shortest paths stored in the cache during the processing of the system dynamically. It is a simple strategy, but the cache constructed by it has low hit ratio, low utilization of cache space and poor parallelism. Static caching technologies analysis the query log to build mathematical model firstly, then select the optimal query stored in cache based on the mathematical model. However, both methods have been over-dependent on the query log, which can not use the cache space efficiently. So we mainly study the shortest path cache building technology in this thesis.This thesis summarizes existing related shortest path cache technologies firstly, and analysis the drawbacks of the existing technologies. In order to describe the shortest path cache quantitatively, we define a cache benefit model to guide the construction of shortest path cache based on the optimal substructure of shortest path in this thesis. Based on the benefit model, we proposed a new algorithm called SPEC to construct the shortest path cache, which can improve the space utilization and query hit ratio effectively. To solve the redundant computing problem in cache building processes. This thesis proposed improvement methods of the SPEC algorithm to improve efficiency of the construction of shortest path cache. We give a cache index structure based on inverted index and give the index construction algorithm and query algorithm. This index support sub path query effectively, which can improve efficiency of shortest path query. Finally, based on the experimental results and the analysis of it on real road network, we can get the result that the proposed caching benefit model can effectively measure the benefit of shortest path cache; the SPEC algorithm can construct shortest path cache effectively to improve the space utilization and query cache hit ratio.