此卡片不在当前主题的阅读序列中,可返回主题继续阅读。
知识卡片
图分片按目标切源点排序
先按顶点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所示。