Streaming Approach to In Situ Selection of Key Time Steps for Time‐Varying Volume Data
Streaming Approach to In Situ Selection of Key Time Steps for Time‐Varying Volume Data
复制标题
DOI：
10.1111/cgf.14542
复制
发表时间：
2022-06
影响因子：
2.5
通讯作者：
Mengxi Wu;Yi-Jen Chiang;Christopher Musco
中科院分区：
文献类型：
--
作者：
Mengxi Wu;Yi-Jen Chiang;Christopher Musco
关键时间步长选择，即，选择最具代表性的时间步长子集，对于大的时变体积数据的有效和高效的科学可视化至关重要。特别是，随着计算机模拟的规模和复杂性不断增长，它们通常会生成超出可用存储容量和将结果传输到存储的带宽的输出，因此必须仅保存时间步长的子集。同时，必须选择该子集，使其具有高度代表性，以促进高保真的后处理和重建。关键时间步长选择问题在原位设置中尤其具有挑战性，在原位设置中，我们只能以在线流方式一次性处理数据，使用少量的主内存和快速计算。在本文中，我们将问题表述为最优分段线性插值问题。我们首先应用数值线性代数的方法来计算线性插值的解决方案和他们的误差在线流的方式。使用该方法作为构建块，我们可以通过标准动态规划（DP）算法获得分段线性插值问题的全局最优解。然而，这种方法需要在多个通道中处理时间步长，并且对于原位设置来说太慢。为了解决这个问题，我们引入了一种新的近似算法，它处理时间步长在一个通过在线流的方式，非常有效的计算时间和内存空间在理论和实践中。该算法适用于现场设置。此外，我们证明了我们的算法，这是基于一个贪婪的更新规则，有很强的理论保证的近似质量和存储的时间步数。据我们所知，这是第一个算法适用于在原位的关键时间步长选择这样的理论保证，是本文的主要贡献。实验证明了我们的新技术的有效性。
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.