论文标题
多成本网络上最佳路由查询的有效索引方法
An Efficient Index Method for the Optimal Route Query over Multi-Cost Networks
论文作者
论文摘要
聪明的城市一直在考虑未来的浪潮，网络中的路线建议是一个基本问题。最短路线问题的大多数现有方法都认为网络中只有一种成本。但是，网络中总有几种成本，用户更喜欢在全球考虑这些成本的情况下选择最佳路线。在本文中，我们研究了在多成本网络中找到最佳途径的问题。我们证明这个问题是NP-HARD，现有的索引技术不能用于此问题。我们提出了一种基于轮廓天际线技术的基于分区的新型索引，以找到最佳路线。我们提出了一种顶点过滤算法来促进查询处理。我们在六个现实生活中进行了广泛的实验，实验结果表明，与以前的启发式算法相比，我们的方法的效率提高了效率。
Smart city has been consider the wave of the future and the route recommendation in networks is a fundamental problem in it. Most existing approaches for the shortest route problem consider that there is only one kind of cost in networks. However, there always are several kinds of cost in networks and users prefer to select an optimal route under the global consideration of these kinds of cost. In this paper, we study the problem of finding the optimal route in the multi-cost networks. We prove this problem is NP-hard and the existing index techniques cannot be used to this problem. We propose a novel partition-based index with contour skyline techniques to find the optimal route. We propose a vertex-filtering algorithm to facilitate the query processing. We conduct extensive experiments on six real-life networks and the experimental results show that our method has an improvement in efficiency by an order of magnitude compared to the previous heuristic algorithms.
