paperbot · PL 论文追踪

全部论文 待读 收藏

P2 KickStarter

KickStarter
ASPLOS Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems2017匹配度 1/10 · 该论文研究流式图计算中的边删除与近似增量计算,属于图系统/运行时方向,与用户关注的静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析均无直接交集。引用 178 inbox
Keval Vora, Rajiv Gupta, Guoqing Xu
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:针对流式图边删除导致近似增量计算不正确或变慢的问题,KickStarter 旨在支持快速准确的持续图计算。

流式图的持续处理通过维护最近图版本上迭代计算的近似结果,并在用户查询时把近似结果送入迭代计算以快速修正误差,从而只做增量计算。该方式在增长图上很有效,但当图中出现边删除时,已有近似可能失效:要么导致不正确结果(例如单调计算终止在错误的极小/极大值),要么导致性能变差(收敛时间超过从头计算)。论文针对这一局限,研究如何在含边删除的流式图场景下继续利用近似结果实现快速且准确的持续计算。

问题
流式图持续处理依赖近似结果进行增量修正,但边删除会使已有近似失效,导致结果错误或收敛慢于从头计算。
方法
论文提出 KickStarter,目标是在存在边删除时仍能利用近似结果进行快速、准确的增量计算;摘要未展开具体算法细节。
评估
摘要未给出实验设置或结果;其目标评估维度是边删除下结果正确性与相比从头计算的性能。
原文摘要(Abstract)

Continuous processing of a streaming graph maintains an approximate result of the iterative computation on a recent version of the graph. Upon a user query, the accurate result on the current graph can be quickly computed by feeding the approximate results to the iterative computation --- a form of incremental computation that corrects the (small amount of) error in the approximate result. Despite the effectiveness of this approach in processing growing graphs, it is generally not applicable when edge deletions are present --- existing approximations can lead to either incorrect results (e.g., monotonic computations terminate at an incorrect minima/maxima) or poor performance (e.g., with approximations, convergence takes longer than performing the computation from scratch).

链接与引用

DOI 原文 · PDF(开放获取) · DBLP

BibTeX
@inproceedings{VoraGX17,
  title = {KickStarter},
  author = {Keval Vora and Rajiv Gupta and Guoqing Xu},
  booktitle = {ASPLOS},
  year = {2017},
  doi = {10.1145/3037697.3037748}
}