Buffering of Intermediate Results in Dataflow Diagrams

Allison Woodruff,  Michael Stonebraker  

 About the Authors

Browsing   Buffer Management   Data Lineage   Dataflow Diagrams   Visual Language Implementation   Scientific Visualization   Visual Dataflow Languages  


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 characterisitcs 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.

 Document in PostScript (compressed, 184074 bytes)

 The Tioga Project

Bending the Rules: Steps toward Semantically enriched Graphical Rewrite Rules Creating Database Queries by Demonstration Index of Talks Proceedings - 11th Intl. Symposium on Visual Languages