Incremental Graph Evaluation

Abstract

There are many computer applications that can be made incremental. After a small perturbation to the computation at hand, intermediate values of a previous evaluation can be used to obtain the result of the new computation. This requires less time than reevaluating the entire computation. We propose the use of a directed graph to represent computations that we wish to make incremental. This graph, called a dependency graph, represents an intermediate computation at each vertex. Edges between vertices represent the dependence of intermediate computations on other intermediate computations. A change to the computation can be represented as a change in the dependency graph.