Adaptive Memoization

Memoization may be viewed as a mechanism for re-using a computation---if a function is re-applied to the same argument we may re-use the previous computation to determine the result, rather than perform it again. Conventional memoization is accurate in the sense that it only permits re-use when a computation will be precisely the same as one that has already been performed. But in many cases a computation may be largely, though not entirely, the same as one that has been previously carried out for a slightly di#erent input. The previous computation may be re-used by permitting inaccurate memoization, and restoring accurancy by adapting the result to the variant input. This technique, which we call adaptive memoization, greatly increases the e#ectiveness of both memoization and adaptivity alone (or in orthogonal combination) for incremental computation. In particular we obtain an incremental version of Quicksort that adjusts its output in logarithmic expected time to insertions and deletions at random positions in the input, and an incremental version of Insertion Sort that adjusts its output in linear time to an insertion or deletion anywhere in its input. These results are the best possible for these algorithms, and rely crucially on adaptive memoization