论文标题
PSPC：有效的平行最短路径在大规模图上计数
PSPC: Efficient Parallel Shortest Path Counting on Large-Scale Graphs
论文作者
论文摘要
在现代图分析中，最短的路径是一个基本概念。许多\ rrev {最近的作品}主要集中在这些最短路径的距离上。然而，在中间分析的时代，计数$ s $和$ t $之间的最短路径同样至关重要。 \ rrev {it}是\ rev {也}图形数据库区域中的重要问题。近年来，已经进行了几项研究，以解决此类问题。尽管如此，由于指数构建阶段的依赖关系，目前的技术面临着相当大的平行障碍，因此限制了其应用的可能性并浪费了潜在的硬件性能。为了解决此问题，我们提供了一种平行的最短路径计数方法，该方法可以避免这些依赖关系，并随着螺纹数量的增加而获得大致线性索引时间的速度。我们的经验评估验证了效率和有效性。
In modern graph analytics, the shortest path is a fundamental concept. Numerous \rrev{recent works} concentrate mostly on the distance of these shortest paths. Nevertheless, in the era of betweenness analysis, the counting of the shortest path between $s$ and $t$ is equally crucial. \rrev{It} is \rev{also} an important issue in the area of graph databases. In recent years, several studies have been conducted in an effort to tackle such issues. Nonetheless, the present technique faces a considerable barrier to parallel due to the dependencies in the index construction stage, hence limiting its application possibilities and wasting the potential hardware performance. To address this problem, we provide a parallel shortest path counting method that could avoid these dependencies and obtain approximately linear index time speedup as the number of threads increases. Our empirical evaluations verify the efficiency and effectiveness.
