返回主题:图计算:切分、BSP 与迭代

此卡片不在当前主题的阅读序列中,可返回主题继续阅读。

知识卡片

结构图卡 · 5434

图分片按目标切源点排序

理解等级:中级

先按顶点ID划Interval,每个Shard保存目标在该Interval内的入边,再按源点ID排序。处理一个Interval时,自身Shard提供全部入边,其他Shard的连续窗口提供出边。两种排序配合,让需访问的边集中成块,而非大量随机寻找。

结构图:

flowchart TD
 A[按目标顶点划Interval] --> B[Shard保存目标区间全部入边]
 B --> C[Shard内部按源ID排序]
 C --> D[完整读取当前Shard]
 C --> E[其他Shard读取对应连续窗口]
 D --> F[内存重建当前子图]
 E --> F
 F --> G[更新并顺序写回]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 图数据库:架构与算法 · 查看原书依据

      在对图节点进行顺序编号并由小到大排序后(称为技巧1),根据编号大小,将图节点划分为不相交的P 个间隔(Interval),每个间隔代表子图节点集合S ,与每个间隔相对应绑定一份数据分片(Shard),用来记录该子图需要保存的信息,这里记载的是图节点集合S 中的所有入边(Inlink)信息,并按照有向边的源节点序号由小到大对边进行排序后有序存储(称为技巧2),图切分后的效果如图14-16所示。

    参考来源

    - 位置:《大数据日知录:架构与算法》第14章《图数据库:架构与算法》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00019.html) - 结论依据:原文在本章对图分片按目标切源点排序给出的定义、机制或示例支持本卡;技术产品描述限于2014年书中版本,示例与实测区分。 - 原始内容:在对图节点进行顺序编号并由小到大排序后(称为技巧1),根据编号大小,将图节点划分为不相交的P 个间隔(Interval),每个间隔代表子图节点集合S ,与每个间隔相对应绑定一份数据分片(Shard),用来记录该子图需要保存的信息,这里记载的是图节点集合S 中的所有入边(Inlink)信息,并按照有向边的源节点序号由小到大对边进行排序后有序存储(称为技巧2),图切分后的效果如图14-16所示。