Many applications need to respond to incremental modifications to data. Being incremental, such modification often require incremental modifications to the output, making it possible to respond to them asymptotically faster than recomputing from scratch. In many cases, taking advantage of incrementality therefore dramatically improves performance, especially as the input size increases. As a frame of reference, note that in parallel computing speedups are bounded by the number of processors, often a (small) constant.
No takes yet. Share an insight, caveat, or question.
Umut A. Acar (2009) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: