Continuous Memoization
The term "memoization" is known in the field of computer science as a technique for recording and remembering the results of previous computations so that repeating the same computations can be avoided. The problem with current memoization methods is that the input must exactly match what is contained in the memo, that is the memo is limited to storing and producing discrete values. We define continuous memoization as a method that memoizes results of full or partial computations on discrete sets of input parameters. We use the results to reconstruct the computation of an unknown set of input parameters by applying a continuous function on the memoized results. This method avoids recomputing the result for every discrete set of input parameters.
Background & Objective: The new method applies to numerous fields in computer science such as computer graphics. The goal of this effort is to identify which applications can benefit most from the new approach and then to apply the method to those identified domains.
Technical Discussion: The new method memoizes a computation as follows. A set of input parameters are provided to the computation. A determination is made to see whether a memo contains results of the computation on sets of memoized parameters near the set of input parameters. If true, the computation for the set of input parameters is reconstructed using the results of the computations on the sets of memoized parameters near the set of input parameters. If false, the computation is performed using the set of input parameters. A result of the computation on the set of input parameters is then memoized, and that result is provided as output of the computation.
Reconstruction can be done be applying some continuous function, such as interpolation, on the memoized results. Additionally, the computation can be partitioned into a number of partial computations, and only selected partial computations are memoized.
The memo is stored in a cache like memory device. Least recently used replacement (LRU) algorithms can be used to keep the cache at a reasonable size. The cache can be partitioned into tiles, where a tile is the minimal amount of a memo that can be accessed for reading or writing. The size of the tile can be adjusted for a particular computation. In addition, the memo can be maintained at multiple levels of resolution, for example, the tiles can be arranged as a pyramid with coarse, middle, and fine resolutions. Continuous functions can than be applied to derive results for intermediate resolutions, as required.
Contact: Ron Perry
Technology Areas:
Artificial Intelligence
Graphics
Modification Date: October 30, 2002
