首页> 外文期刊>Knowledge and Data Engineering, IEEE Transactions on >Holistic Top-k Simple Shortest Path Join in Graphs
【24h】

Holistic Top-k Simple Shortest Path Join in Graphs

机译:图中的整体Top-k简单最短路径联接

获取原文
获取原文并翻译 | 示例

摘要

Motivated by the needs such as group relationship analysis, this paper introduces a new operation on graphs, named top-k path join, which discovers the top-k simple shortest paths between two given node sets. Rather than discovering the top-k simple paths between each node pair, this paper proposes a holistic join method which answers the top-k path join by finding constrained top-k simple shortest paths between two nodes, and then devises an efficient method to handle the latter problem. Specifically, we transform the graph by encoding the precomputed shortest paths to the target node, and use the transformed graph in the candidate path searching. We show that the candidate path searching on the transformed graph not only has the same result as that on the original graph but also can be terminated much earlier with the aid of precomputed results. We also discuss two other optimization strategies, including considering the join constraint in the candidate path generation as early as possible, and pruning search space in each candidate path generation with an adaptively determined threshold. The final extensive experimental results also show that our method offers a significant performance improvement over existing ones.
机译:基于诸如组关系分析之类的需求,本文介绍了一种针对图的新操作,名为top-k路径联接,它发现了两个给定节点集之间的top-k条最短路径。与其发现每个节点对之间的前k个简单路径,不如提出一种整体连接方法,该方法通过找到两个节点之间受约束的top-k最短路径来回答top-k路径连接,然后设计一种有效的方法来处理后一个问题。具体来说,我们通过编码到目标节点的预先计算的最短路径来变换图,并在候选路径搜索中使用变换后的图。我们表明,在变换后的图上搜索候选路径不仅具有与原始图上相同的结果,而且可以借助预先计算的结果更早地终止。我们还讨论了其他两种优化策略,包括尽早考虑候选路径生成中的联接约束,以及使用自适应确定的阈值修剪每个候选路径生成中的搜索空间。最终的大量实验结果还表明,与现有方法相比,我们的方法具有显着的性能改进。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号