Zhang Zining, Yang Shenghong, Qin Yunchuan, Yang Zhibang, Huang Yang, Zhou Xu
College of Computer Science and Electronic Engineering, Hunan University, Changsha, Hunan China.
Neural Comput Appl. 2022 Jun 28:1-11. doi: 10.1007/s00521-022-07485-x.
Graphs are widespread in many real-life practical applications. One of a graph's fundamental and popular researches is investigating the relations between two given vertices. The relationship between nodes in the graph can be measured by the shortest distance. Moreover, the number of paths is also a popular metric to assess the relationship of different nodes. In many location-based services, users make decisions on the basis of both the two metrics. To address this problem, we propose a new hybrid-metric based on the number of paths with a distance constraint for road networks, which are special graphs. Based on it, a most relevant node query on road networks is identified. To handle this problem, we first propose a Shortest-Distance Constrained DFS, which uses the shortest distance to prune unqualified nodes. To further improve query efficiency, we present Batch Query DFS algorithm, which only needs only one DFS search. Our experiments on four real-life road networks demonstrate the performance of the proposed algorithms.
图表在许多实际应用中广泛存在。图表的一项基本且热门的研究是探究两个给定顶点之间的关系。图表中节点之间的关系可以通过最短距离来衡量。此外，路径数量也是评估不同节点关系的一个常用指标。在许多基于位置的服务中，用户基于这两个指标来做出决策。为了解决这个问题，我们针对道路网络（一种特殊的图表）提出了一种基于带有距离约束的路径数量的新混合指标。基于此，确定了道路网络上的一个最相关节点查询。为处理这个问题，我们首先提出了最短距离约束深度优先搜索（Shortest-Distance Constrained DFS），它利用最短距离来修剪不合格节点。为了进一步提高查询效率，我们提出了批量查询深度优先搜索（Batch Query DFS）算法，该算法只需要一次深度优先搜索。我们在四个实际道路网络上进行的实验证明了所提算法的性能。
