基于Grid网格划分的改进路网最短路径查询

Improving Shortest Path Query in Road Network Based on Grid Partition

最短路径查询作为图数据库管理的一项重要课题在近些年来受到国内外学者的广泛关注.在现实应用中有效地利用缓存进行路网上最短路径查询成为一个重要的研究问题,而现有方法在缓存有限的条件下均不能高效地响应用户查询请求.针对上述问题本文提出了一种有效的用于支持路网最短路径查询的缓存代价模型,设计了缓存构造算法,进而高效的选择那些不同且能满足更多查询请求的最短路径放入缓存.基于此模型,利用Grid对大图进行划分,提高了查询效率,节省了辅助的存储空间和查询处理代价.最后采用真实数据集进行性能分析,实验结果显示本文提出的方法更有效.

In recent years, shortest path query which is a important topic in graph database management has received lots of attention of researchers. Also, in real applications, how to query shortest path effectively using cache is an important topic. However, existing caching techniques are ineffective for shortest path queries with limited caching space. Motivated by this, we propose an effective caching cost model to support shortest path queries using cache. Also, we design a greedy algorithm for selecting the variety and beneficial shortest paths to fulfill cache. Based on this model, we employ a method to partition road network using Grid, which can improve effectiveness of shortest queries, save extra ancillary space and processing costs. Experimental results on real dataset have shown the effectiveness of our beneficial model.