Burst Shortest Path Query Caching Strategies And Optimization Approaches

With the rapid development of computer technology and Internet technology,graph data and model are used increasingly to describe the complex relationship between various entities.As the most classic and basic issue in graph theory,shortest path query has attracted broad attention all the time.And with the popularity of smart mobile devices,the demand of the shortest path query on road network has become a focus recently.The caching technology is efficient to support smart mobile devices,so how to use the caching technology to support shortest path query on road network efficiently has become a significant research problem.Caching technology can be divided into two categories:static caching technology and dynamic caching technology.And existing caching technology for shortest path query is mainly the static one.Based on query's statistic information in query log,those technologies calculates query's benefit and puts the optimal query in cache based on the benefit.Static cache needs to be refreshed regularly,for example,updating cache once a day.However,those static technologies are over-depended on query log,and they can't handle the burst query efficiently which has no regular pattern.So we mainly study how to refresh cache dynamically so as to support shortest path query more efficiently.Firstly,this thesis introduces existing work on shortest path caching technology and analyses their drawbacks.Then,based on the burst query's characteristic and sliding window technology,we propose a benefit model suitable for burst query to evaluate each path.The value of the benefit is obtained from the query's statistic information and frequency growth rate in the sliding window.Next,to build and refresh shortest path cache and ensure the utilization ratio and hit ratio,we propose a cache initialization and refresh algorithm BRC(Benefit Reload Cache)according to the benefit model.To solve the redundant computing problem,we propose some optimization strategies and a new algorithm BRC*to improve efficiency of the construction and refreshment of shortest path cache.We give a cache index structure based on inverted index and give the index construction algorithm,refreshing algorithm and query algorithm.This index can support sub path query effectively,which can improve efficiency of shortest path query.Finally,based on real road network datasets,we implement the BRC and BRC*algorithm.Through a large number of comparing experiments and results analysis,it's proved that our model and algorithm can handle burst query efficiently and the shortest path cache which is built based on our algorithm has both higher hit ratio and utilization ratio.