Approximation of function evaluation over sequence arguments via specialized data structures

• Published in: Theoretical computer science 2015-11, Vol.607, p.113-123
• Main Authors: Biswas, Tamal T., Regan, Kenneth W.
• Format: Article
• Language: English
• Subjects: Approximation; Arrays; Cloud computing; Data structures; Derivatives; Machine learning; Mathematical analysis; Mathematical models; Memoization; Metrics; Sequences; Topology
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2015.03.049

•A warped grid data structure to retrieve stored approximate function evaluations.•Saves computing first Taylor partials by using single gradient of warped surface.•Applicable where function evaluation has lesser impact on greater arguments.•Efficient single-lookup-indexing for any stored evaluation.•Later application of interpolation to approximate any neighboring sequence. 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.