多维代价图模型上最优路径查询问题的研究

Optimal Path Query Based on Cost Function Over Multi-Cost Graphs

近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系.最短路径查询是图研究领域中一类非常重要的查询并有着广泛的应用.然而,目前大多数关于最短路径的查询都是定义在单代价(权重)图模型下的.现实世界中,基于单一代价所选择的最短路径并不明智,比如路程最短的路径需要花费极高的费用.该文中,作者介绍了多维代价图模型的概念,并给出了多维代价图模型下基于函数的最优路径的定义.现有的计算最短路径的方法都利用了最短路径的子路径最优的性质:最短路径上的任意两点间的子路径是这两点的最短路径.因此,在计算最短路径的过程中,对访问过的每个顶点,只需保留起点到该点的最短路径即可.不幸的是,多维代价图模型下,当评分函数是非线性的时候,子路径最优的性质并不成立.因此,目前的方法均不能应用于多维代价图模型下基于函数的最优路径查询问题.该文给出了一个best-first search分支界限法并给出3种优化策略.进一步,给出了一个顶点过滤算法,该算法能从图中过滤掉大部分不属于最优路径的顶点.最后,用真实数据集上的实验验证了算法的有效性.

Graphs have been widely used to model complex relationships among various entities in real applications. Shortest path query is an important problem in graphs and has been well- studied. However, most approaches for shortest path are based on single-cost （weight） graphs. However, it is non-sufficient that considering only one cost type. In this paper, we introduce the definition of multi-cost graph and propose a new query： the optimal path query based on function over multi-cost graphs. Most existing methods to compute shortest path utilize the property of optimal sub-path in shortest path： any sub-path of a shortest path is also a shortest path. Thus, they only need to maintain the shortest path from starting node to any visited node （not ending node） when computing shortest path. Unfortunately, the optimal sub-path property doesn＇t hold in multi-cost graphs. We propose a best-first search branch and bound algorithm and three optimizing strategies. We also propose a vertex-filtering algorithm to filter a large proportion of vertices from graph. We confirmed the effectiveness and efficiency of our algorithms using real-life datasets in experiments.