Incremental Algorithms

Consider the following scenario: This scenario presents a challenge: how do you avoid recomputing whole volumes after every small change? An effective answer to this question is often important for efficiency and latency. The general class of answers to this challenge: IncrementalAlgorithms. You process the changes, send only the difference across the network, draw only DirtyRectangles. Video compression is based on this - send just the changes in the video frame (with occasional full frame to avoid degradation). EventStreamProcessing is fundamentally about processing 'important' changes.

Unfortunately, there is no known solution general across domains. One cannot generally transform a non-incremental computation into an incremental one. Often, one needs to reduce expressiveness of the transforms to gain any real benefits, because a common issue is tracking how an update in one domain corresponds to an update in another. Incremental computation achieved by hand will almost never 'compose' - that is, after integrating with third-party modules developed in the same language you'll likely have lost incremental properties.

Some languages are relatively suitable for incremental computation, though. FunctionalReactiveProgramming can handle changes in the temporal dimension incrementally (no need to recompute the world every tick) but doesn't offer much help for incremental processing of very large 'volumes' in the spatial dimension, of the sort mentioned above. RelationalAlgebra is relatively incremental in the spatial dimension, making it suitable for ContinuousQueryLanguage. Each of these are valuable in a wide range of domains, and so offer some promise that a general purpose incremental programming language is feasible - even if we haven't quite figured out how to achieve it. Such a language would be a powerful tool for building huge-scale ReactiveProgramming systems such as reactive industrial-sized databases, command and control systems, and massively multi-player games; it would also help with LiveProgramming.

Incremental Invariants


View edit of October 15, 2010 or FindPage with title or text search