Approximation of function evaluation over sequence arguments via specialized data structures

This paper proposes strategies for maintaining a database of computational results of functions f on sequence arguments x→, where x→ is sorted in non-decreasing order and f(x→) has greatest dependence on the first few terms of x→. This scenario applies also to symmetric functions f, where the partial derivatives approach zero as the corresponding component value increases. The goal is to pre-compute exact values f(u→) on a tight enough net of sequence arguments, so that given any other sequence x→, a neighboring sequence u→ in the net giving a close approximation can be efficiently found. Our scheme avoids pre-computing the more-numerous partial-derivative values. It employs a new data structure that combines ideas of a trie and an array implementation of a heap, representing grid values compactly in the array, yet still allowing access by a single index lookup rather than pointer jumping. We demonstrate good size/approximation performance in a natural application.