← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 1779.d.1.b

变化阈值决定激活范围

理解等级:中级

PageRank示例把新旧分值之差分到出边,变化超过阈值才激活邻居,减少不必要更新。阈值是精度与计算量的选择,不能不说明误差就称完全相同结果。最短路示例也区分增大时使缓存失效和减小时传播候选,体现增量更新依赖运算性质。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      将GAS接口的四个函数引入算法14.12后,Gather和Apply阶段很好理解,关键是Scatter阶段,在这个阶段,对当前计算的节点u 的出边指向的节点集合scatter_nbrs(u)中的任意节点v 来说,首先调用用户定义的Scatter函数,其逻辑是:判断节点u 的数值变化是否足够大,如果足够大,则需要继续迭代过程,激活节点v 使得后续计算能够继续,同时返回Δa ,也即节点u 的PageRank变化值分配到每条出边后获得的增量值。

    参考来源

    - 位置:《大数据日知录:架构与算法》第14章《图数据库:架构与算法》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00019.html) - 结论依据:原文在本章对变化阈值决定激活范围给出的定义、机制或示例支持本卡;技术产品描述限于2014年书中版本,示例与实测区分。 - 原始内容:将GAS接口的四个函数引入算法14.12后,Gather和Apply阶段很好理解,关键是Scatter阶段,在这个阶段,对当前计算的节点u 的出边指向的节点集合scatter_nbrs(u)中的任意节点v 来说,首先调用用户定义的Scatter函数,其逻辑是:判断节点u 的数值变化是否足够大,如果足够大,则需要继续迭代过程,激活节点v 使得后续计算能够继续,同时返回Δa ,也即节点u 的PageRank变化值分配到每条出边后获得的增量值。