One-pass evaluation of region algebra expressions

摘要

A region algebra is a set of operators that take lists of regions as inputs and return lists of regions as results. Consider evaluating an operator tree that has region lists at the leaf nodes, operators at the internal nodes, and edges representing the data flow between the operators. A simple method is to evaluate operators one at a time in a bottom-up manner starting at the leaves. This requires that intermediate results be buffered in memory or written to disk.We describe an alternative method that merges the input region lists and performs the evaluation using a single pass over this merged list. This can be more efficient than evaluating operators one at a time since intermediate results are not buffered or written to disk.