Streaming Approach to In Situ Selection of Key Time Steps for Time-Varying Volume Data
EuroVis 2022
Mengxi Wu, Yi-Jen Chiang and Christopher Musco
Computer Graphics Forum , vol. 41(3), pp. 309--320, 2022
(Special Issue for Eurographics/IEEE Conference on Visualization (EuroVis 2022))
Abstract:
Key time steps selection, i.e., selecting a subset of most
representative time steps, is essential for effective and efficient
scientific visualization of large time-varying volume data. In
particular, as computer simulations continue to grow in size and
complexity, they often generate output that exceeds both the available
storage capacity and bandwidth for transferring results to storage,
making it indispensable to save only a subset of time steps. At the
same time, this subset must be chosen so that it is highly
representative, to facilitate post-processing and reconstruction with
high fidelity. The key time steps selection problem is especially
challenging in the in situ setting, where we can only process data in
one pass in an online streaming fashion,
using a small amount of main memory and fast computation. In this
paper, we formulate the problem as that of optimal piece-wise
linear interpolation. We first apply a method from numerical
linear algebra to compute linear interpolation solutions and their
errors in an online streaming fashion. Using that
method as a building block, we can obtain a global optimal solution
for the piece-wise linear interpolation problem via a standard dynamic
programming (DP) algorithm. However, this approach needs to process
the time steps in multiple passes and is too slow for the in situ
setting. To address this issue, we introduce a novel approximation
algorithm, which processes time steps in one pass in
an online streaming fashion, with very efficient
computing time and main memory space both in theory and in
practice. The algorithm is suitable for the in situ
setting. Moreover, we prove that our algorithm, which is based on a
greedy update rule, has strong theoretical guarantees
on the approximation quality and the number of time steps stored. To
the best of our knowledge, this is the first algorithm suitable
for in situ key time steps selection with such
theoretical guarantees, and is the main contribution of this
paper. Experiments demonstrate the efficacy of our new techniques.
Back to Yi-Jen Chiang's home page