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