Buffering of Intermediate Results in Dataflow Diagrams

Buffering of intermediate results in dataflow diagrams can significantly reduce latency when a user browses these results or re-executes a diagram with slightly different inputs. We define the optimal buffer allocation problem of determining the buffer contents which minimize the average response time to such user requests. We show that this problem has several characteristics which render traditional latency reduction techniques ineffective. Since optimal buffer allocation is NP-hard, we propose heuristic methods for buffer management of intermediate results. We present a simulation of the behavior of these heuristics under a variety of conditions, varying graph structure and access pattern. We argue that history mechanisms which track user access patterns can be used to improve performance. We further show that graph structure and access pattern determine the factor of improvement which is possible. The performance enhancements we describe can be applied to minimize query response time in visual dataflow languages.