针对大规模应用的欧拉-拉格朗日组合数据表示方法-36大数据

作者：Jiang Zhang

在科学应用中，模拟的数据输出形式主要有两种。一种是欧拉表示，也就是通常说的体数据，在固定的格点上记录数据信息，不过对于格点之间的区域往往需要插值。另一种是拉格朗日表示，即粒子数据，记录了离散粒子在数据场内的运动，其缺点是在一些感兴趣的区域可能没有粒子出现。在传统方法里，这两种数据表示形式在不同的分析任务中往往是独立存储和访问的。 为了提高计算效率，我们需要一种将两者进行结合的高效的组合表示形式。这篇文章[1]针对这一问题提出了一种欧拉-拉格朗日联合表示方法，可以对两种形式的原始模拟输出数据同时进行重组织，提高了数据载入和一些基本数据操作的效率。

图1 欧拉-拉格朗日的组合数据表示方法的主要部分

如图1所示，该方法在预处理阶段将原始的体数据和粒子数据组织成欧拉-拉格朗日单元的格式。基于这种数据结构，作者开发了一系列数据分析操作工具，例如条件查询，不同数据形式的转换，缺失时间步插值，以及轨迹的构建等。除此之外，该数据结构还可用于高效地对大规模数据进行多分辨率子集的采样。接下来会对这些内容一一介绍。

图2 (a) 单独的欧拉格点和拉格朗日粒子. (b) 欧拉-拉格朗日的组合数据形式

欧拉-拉格朗日单元是一种组合数据结构。在每个单元中，欧拉信息包含了格点的位置，相关的标量或矢量值，以及一系列邻接格点，拉格朗日信息包含了一系列指向每个粒子的向量，以及该粒子的ID和标量或矢量值。图2(a)展示了两种数据形式，其中黑色的实心圆表示格点，红色表示粒子。图2(a)将两种数据形式组织成了组合单元，每个单元由其中心的格点和指向该格点的若干粒子组成。

图3 组合单元在硬盘中的存储形式

这种组合单元在硬盘中的存储形式如图3所示，主要包含两个方面。一个是欧拉位置信息，包括格点位置，每个格点的一系列邻接格点，以及一个帮助索引文件（用于记录邻接格点的数目信息），这三种信息都是单独存放在不同的文件。另一个是时变数据信息，按照时间步组织存储。在每个时间步里，每个欧拉变量，拉格朗日向量，以及每个拉格朗日变量，都被单独存储在不同的文件。除此之外，也有一个帮助索引文件，用于记录起始读位置和每个单元的粒子树目。

图4 组合单元在内存中的组织形式

当组合单元被读取到内存中时，数据会被组织成更紧密的块，如图4所示。具体来讲，内存中的每个块保存了单元的基本信息，包括格点位置和欧拉变量，相关联的粒子数目，以及邻接格点。帮助索引此时变成了指向粒子（包括其位置向量和拉格朗日变量）的指针和指向邻接格点索引的指针。

图5 基于欧拉信息的条件组合单元查询示例

基于这种组合数据结构，我们可以进行一些基础的数据操作。第一种是条件查询，可以根据欧拉或拉格朗日的查询条件去匹配满足要求的单元并载入到内存中。图5给出了一个例子，通过设置查询条件（欧拉变量值比较高），可以将符合要求的单元，包括欧拉格点和拉格朗日粒子，逐一搜索出来并以可视化的方式呈现出来。第二种是两种形式之间的转换。我们可以将拉格朗日变量映射到欧拉格点上，也可以将欧拉数据值映射到拉格朗日粒子上。第三种是针对体数据和粒子数据时间分辨率不一致时，在缺失的时间步上利用已有时间步上的欧拉变量／拉格朗日变量进行插值。最后一种是粒子轨迹的构建，需要检索单元以从中找到ID相同的粒子。

图6 基于固定比率(unbiased sampling)和固定数目(biased sampling)的采样方法示例

此外，对于大规模数据，我们可以从中采样出多分辨率的数据子集。这主要是针对粒子数据过大造成视觉遮挡的问题。采样方法有两种，一种是在每个单元里采样固定比率的粒子，另一种是在每个单元里采样固定数目的粒子。前一种方法保留了数据域每个部分的相对粒子密度，后一种方法则突出了欧拉格点密度高的区域的粒子密度（因为非结构化数据的感兴趣区域往往是格点密集的地方），如图6所示例子。

图7 组合结构和八叉树以及k-d树的预处理时间的对比

图7展示了这种组合结构和八叉树以及k-d树的预处理时间的对比。可以看到，欧拉-拉格朗日组合结构花费了更多的时间，这是因为其预处理涵盖了将粒子和格点相关联的这部分计算。在后面的数据操作中，通过图8可以看到，组合结构相比于八叉树和k-d树，其效率基本上都有了很大的提高。这也证明了该结构在不同数据操作中的有效性。

图8 不同方法数据操作时间花费的对比

通过以上介绍可以看到，这种欧拉-拉格朗日组合结构就是将模拟输出的体数据和粒子数据在存储和读入时结合到了一起，支持快速易用的数据载入和操作。虽然牺牲了更多的时间用于预处理，在不同的数据分析任务中还是提高了效率。实际上，可视化中经常会碰到多源或者异构的数据，当我们需要一起进行分析时，可以像这篇文章一样，将它们更好地组织起来，能够节省我们在数据可视化和探索时的时间等开销。

End.

转载请注明来自36大数据（36dsj.com)： 36大数据 » 针对大规模应用的欧拉-拉格朗日组合数据表示方法