知识卡片
滑动窗口把随机访问组织成顺序
依次处理相邻Interval时,各Shard所需源ID区间连续前移,故可按块读取并写回。磁盘顺序访问效率是GraphChi单机处理大图的关键,不是并发线程特别多。增加分片可降低单次内存需求,也增加管理和I/O轮转成本,不能视为无限扩容。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 图数据库:架构与算法 · 查看原书依据
之所以被称为“并行滑动窗口”,是因为如果当前正在处理第i 个间隔,则需在其他P -1个间隔对应的数据分片中读取对应的连续出边信息,而处理完后继续处理第i +1个间隔时,其他P -1个间隔对应的数据分片中需要读取的连续出边信息紧跟在之前处理第i 个间隔时候取的出边信息数据后面,随着计算的进行,每个数据分片就像有一个滑动窗口在随着计算的进行不断下移。
参考来源
- 位置:《大数据日知录:架构与算法》第14章《图数据库:架构与算法》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00019.html)
- 结论依据:原文在本章对滑动窗口把随机访问组织成顺序给出的定义、机制或示例支持本卡;技术产品描述限于2014年书中版本,示例与实测区分。
- 原始内容:之所以被称为“并行滑动窗口”,是因为如果当前正在处理第i 个间隔,则需在其他P -1个间隔对应的数据分片中读取对应的连续出边信息,而处理完后继续处理第i +1个间隔时,其他P -1个间隔对应的数据分片中需要读取的连续出边信息紧跟在之前处理第i 个间隔时候取的出边信息数据后面,随着计算的进行,每个数据分片就像有一个滑动窗口在随着计算的进行不断下移。