• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International conference on world wide web >Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling
【24h】

Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling

机译：修剪后的地标标记在大型进化网络上的动态和历史最短路径距离查询

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We propose two dynamic indexing schemes for shortest-path and distance queries on large time-evolving graphs, which are useful in a wide range of important applications such as real-time network-aware search and network evolution analysis. To the best of our knowledge, these methods are the first practical exact indexing methods to efficiently process distance queries and dynamic graph updates. We first propose a dynamic indexing scheme for queries on the last snapshot. The scalability and efficiency of its offline indexing algorithm and query algorithm are competitive even with previous static methods. Meanwhile, the method is dynamic, that is, it can incrementally update indices as the graph changes over time. Then, we further design another dynamic indexing scheme that can also answer two kinds of historical queries with regard to not only the latest snapshot but also previous snapshots. Through extensive experiments on real and synthetic evolving networks, we show the scalability and efficiency of our methods. Specifically, they can construct indices from large graphs with millions of vertices, answer queries in microseconds, and update indices in milliseconds.
机译：对于大型演化图上的最短路径和距离查询，我们提出了两种动态索引方案，它们可用于各种重要应用，例如实时网络感知搜索和网络演化分析。据我们所知，这些方法是第一种实用的精确索引方法，可以有效地处理距离查询和动态图更新。我们首先为最后一个快照的查询提出一种动态索引方案。它的离线索引算法和查询算法的可伸缩性和效率即使在以前的静态方法中也具有竞争力。同时，该方法是动态的，也就是说，它可以随着图形随时间的变化而递增地更新索引。然后，我们进一步设计了另一种动态索引方案，该方案还可以回答两种历史查询，这些查询不仅涉及最新快照，还涉及先前快照。通过在真实和合成演进网络上的大量实验，我们展示了我们方法的可扩展性和效率。具体来说，他们可以从具有数百万个顶点的大型图构造索引，以微秒为单位回答查询，并以毫秒为单位更新索引。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号