Incremental Attribute Evaluation: A Flexible Algorithm for Lazy Update

Abstract

This paper introduces a new algorithm for incremental attribute evaluation.The algorithm is lazy: Itevaluates only theattributes that are both affected byachange andthat are directly or indirectly observable by the user.In this way, the wasted work of computing values that are never actually used is avoided.Although the algorithm is not optimal, it performs better than the standard "optimal" algorithm in cases where expensive but optional computations need to be supported.Furthermore, the algorithm does not have some of the limitations of other algorithms.It works for general attributed graphs as well as for standard attributed trees.In addition, it does not presume any special editing model, and it supports multiple change points without loss of efficiency.