• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE international conference on data engineering >FERRARI: Flexible and efficient reachability range assignment for graph indexing
【24h】

FERRARI: Flexible and efficient reachability range assignment for graph indexing

机译：FERRARI：灵活，高效的可达性范围分配，用于图形索引

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

摘要

In this paper, we propose a scalable and highly efficient index structure for the reachability problem over graphs. We build on the well-known node interval labeling scheme where the set of vertices reachable from a particular node is compactly encoded as a collection of node identifier ranges. We impose an explicit bound on the size of the index and flexibly assign approximate reachability ranges to nodes of the graph such that the number of index probes to answer a query is minimized. The resulting tunable index structure generates a better range labeling if the space budget is increased, thus providing a direct control over the trade off between index size and the query processing performance. By using a fast recursive querying method in conjunction with our index structure, we show that, in practice, reachability queries can be answered in the order of microseconds on an off-the-shelf computer — even for the case of massive-scale real world graphs. Our claims are supported by an extensive set of experimental results using a multitude of benchmark and real-world web-scale graph datasets.
机译：在本文中，我们针对图的可达性问题提出了一种可扩展且高效的索引结构。我们以众所周知的节点间隔标记方案为基础，其中从特定节点可到达的一组顶点被紧凑地编码为节点标识符范围的集合。我们对索引的大小施加了明确的限制，并灵活地为图的节点分配了近似的可到达范围，以使回答查询的索引探针的数量最小化。如果增加空间预算，则得到的可调索引结构将产生更好的范围标记，从而直接控制索引大小和查询处理性能之间的折衷。通过结合我们的索引结构使用快速递归查询方法，我们表明，实际上，即使在大规模现实世界中，在现成的计算机上也可以以微秒为单位回答可达性查询图。我们的主张得到了使用大量基准测试和实际Web规模图形数据集的广泛实验结果的支持。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号