Institute for Data Analysis and Visualization

We present a method for efficient computation and storage of approximations of error tables used for error estimation between different time steps in time-varying datasets. The error between time steps is defined as the distance between the data of these time steps. Error tables are used to look up the error between different time steps of a time-varying dataset, their generation itself can be expensive. For n time steps, the exact error look-up table has a memory complexity and preprocessing time complexity of O(n^2). Our approximate error table approach uses trees, where leaf nodes represent original time steps, and interior nodes contain an approximation of the children nodes. The error computed on an edge of a tree describes the distance between the two nodes on that edge. Evaluating the error between two different time steps requires traversing a path between the two leaf nodes, accumulating the errors on the traversed edges. For n time steps, this scheme has a memory complexity and preprocessing time complexity of O(n log(n)), a significant improvement over the exact scheme. As we do not need to calculate all possible n^2 error terms, our approach is a fast way to generate the approximation.