Self-adjusting computation refers a technique that enables computations to respond to dynamically changing (input) data automatically. The fundamental idea is to track the control and data dependencies in a computation in such a way that changes to data can be propagated through the computation by identifying the affected pieces that depend on the changes and re-doing the affected pieces. Self-adjusting computation can dramatically improve efficiency of updates in response to small changes to data with respect to recomputing from scratch. In many cases, self-adjusting computation can achieve close to optimal update times. By automatically performing the updates, instead of relying of sophisticated algorithms and precious human intelligence and labor to implement these algorithms, the technique basically automates a typically a very complex task. The technique has proved effective for a broad range of problems, including in computational finance, geometric problems, machine learning, and has even helped solve previously open problems in these areas. The main technical device in the development of self-adjusting computation was to unite techniques that are sometimes known as "Theory B" and "Theory A", which trace to fathers of Computer Science, Alonzo Church, and Alan Turing.

Self-adjusting computation is being used by Jane Street to speed up their analytics.

Publications

Page updated

Google Sites

Report abuse