Precomputation in a complex object environment

Abstract

Certain analytical results are established about precomputation in a complex object environment. The concept of 'intervals' is introduced and it is shown that object-identifier caching might be beneficial provided the frequency of updates to the set of subobjects associated with an object is not too high. However, in most cases, procedures with value caching outperformed other forms of representations. Certain performance characteristics of a knapsack-based algorithm are established which can be used to optimally decide which of the precomputed results to cache. Simulation results demonstrate how well this scheme performs. In particular, a binary search strategy seems ideally suited for caching.