© 2014年。由爱思唯尔公司出版信息工程研究院负责评选和同行评议可在www.sciencedirect.com上在线获取ScienceDirectIERI Procedia 10（2014）138 - 1432014未来信息工程海量时空数据王欢，邓俊辉，袁国栋 *清华大学计算机科学与技术系，北京，100084摘要随着基于计算机的气候模拟的扩展，对大量气候数据的有效可视化和分析变得比以往任何时候都更加重要。本文尝试将窗口查询与时变数据挖掘技术相结合，探索隐藏在气候变化背后的因素。在保证查询时间和存储开销不变的前提下，该算法支持对三维时变数据集的平均值、最小值和最大值等多种查询。给出了一种新的时变数据分析算法，特别适用于大数据分析。所有这些算法已经实现并集成到一个视觉分析系统，与平铺液晶超分辨率显示。在实际应用中的几个数据集上的实验结果。© 2014作者。由爱思唯尔公司出版 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究院负责评选和同行评议关键词：窗口查询;可视化分析;时空数据挖掘;可视化;地球系统模型;1. 介绍近年来，随着计算能力和存储能力的快速增长，越来越多的科学数据通过先进的观测仪器和模拟实验产生，如全球海洋实时观测系统。我们将以地球系统模型（ESM）为例。的* 通讯作者。联系电话：+86-158-0140-2071。电子邮箱：whthu168@163.com。本文是国家高技术研究发展计划（863计划）项目资助的课题。2010AA012402。2212-6678 © 2014作者由爱思唯尔公司出版 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究所负责的选择和同行评审Huan Wang等人/ IERI Procedia 10（2014）138139stni1ESM是描述大气、海洋、海冰以及陆地和海洋生物圈内部和之间的过程的方程组[1]。通过对地球气候和环境变化的模拟，科学家可以更好地了解生态环境，进而更详细地解释地球演化机制。在地球科学中，规模高达TB的大数据无处不在。通常，即使是对这样的数据集的单次扫描也将花费数十分钟。这就是为什么可视化技术和工具对科学家如此重要[2]。然而，另一方面，人类解释数据的方式与计算机的方式大不相同。例如，有了更高层次的视觉和感知能力，我们可以更快、更精确地从图像和动画中找到模式。事实上，气候可视化在过去二十年中一直是VISC的重要组成部分。通常，2D标量数据可以使用诸如颜色映射之类的算法来可视化，而3D标量数据可以使用诸如等值面、轮廓提取、体绘制等之类的算法来可视化。许多可视化工具包也已经开发出来，如VTK [3]和visIt [4]。近年来，可视化技术正朝着大规模、交互性、实时性的方向快速发展。可视化分析（或可视化数据挖掘）是可视化和数据挖掘技术的结合。Wong等人列出了极端规模视觉分析的最大挑战[5]。结合窗口查询技术和时变数据挖掘方法，提出了一个面向海量时空数据的综合可视化分析平台。2. 背景2.1. 基本概念值域查询问题是计算几何中的核心问题之一。设是由d维欧氏空间Rd的若干子集组成的系统。P是由Rd中的n个元素组成的点集。范围查询的问题可以定义为：对于任意给定的区域R，设计有效的算法，找出哪些元素属于R（图1（a））。如果P和R同时给定，则问题可转化为求解P≠R的问题。我们可以对P的元素进行逐个测试，这显然是耗时的[6]。sti，ni，t我sti，ni1，ti2j11i2j1i，ni1，t2012年1月1日图1.一、（a）左：范围查询的示例;（b）右：一维情况下稀疏表的计算在实际应用中，P通常是预先给定的，相对不变，这意味着它可以通过更有效的算法来求解。在这种情况下，它被抽象成一个精确的数学模型。为对于任意给定的点pP，分配权重w（p）S。 可以证明，（S，）是一个可交换的半群[6].然后这个问题在数学上表示为计算p的所有权重之和属于PR。............140Huan Wang等人/ IERI Procedia 10（2014）138J2.2. 相关工作已经发明了许多算法用于范围查询，例如四叉树，B树，KD树，优先级搜索树，跳过列表等[7，8和9]。以范围最小/最大查询（RMQ）为例，最新的研究结果表明，RMQ问题可以在O（n），O（1）时间内解决[10]。通过在线性时间内构造笛卡尔树，将其转化为最低公共祖先（LCA）问题[11]，可以在O（n），O（1）时间内解决。然而，这一结果不能直接扩展到时空数据，因为每个时间片的树结构不一致或其实现的复杂性。本文利用稀疏表技术给出了一个时间复杂度为O（nlogn），O（1）的高效算法，该算法在时间复杂度和空间复杂度上取得了很好的平衡。3. 窗口查询为方便起见，本文仅给出了二维时空数据查询的公式，便于三维时空数据查询的扩展。假设2d数据集V的行数、列数和时间片数为R、C、T， 定义NR *C。查询窗口W的左上角下标为（i1，j1），右下角下标为（i2，j2）。必须指出的是，由于数据是巨大的，通常高达数百千兆字节，输出数据不能完全在内存中处理因此，高效的缓存策略和存储技术必须仔细设计了通常，数据根据时间维度划分为多个部分，以获得最佳性能。3.1. 平均查询我们可以很容易地构造一个平均查询算法使用鸽子洞原则。它由两个阶段组成：预处理阶段和查询执行阶段。首先，考虑V在时间t从（0，0）到（i，j）的子集，si，j，t是位于其中的所有点的和。因此，我们有：斯韦夫斯+s-s.（一）i，j，ti，j，t i 1，j，t i，j 1，t i-1，j-1，t通过少量的观测，我们可以使用动态规划方法来计算si，j，t，它只遍历整个数据集一次。因此，空间复杂度和时间复杂度都是（N*T）。其次，遵循类似的原理，窗口W中的平均值avgt由下式给出：平均tsi 2，j 2，t-si1，j 2，t-si 2，j 1，t si1，j 1，t。（二）（i2i 1）*（j2 1）显然，时间复杂度是（T）。3.2. 最小/最大查询由于范围最大和最小查询的相似性，下面我们将只讨论范围最大查询。首先，定义一个表i，j，ni，nj，t，其大小为N*R*T*C*T，其中i，j，ni，nj，t为最大在时间t，在（i，j）处开始的具有长度（2ni，2nj）的子集中的值。 很明显，我们可以得到一个递归算法如下，并且图1（b）示出了它在1D情况下如何工作sti，j，ni，nj，t maxsti，j，ni-1，n1，t，st2n1，j，n i1，nj 1，t，st2nj1，ni 1，nj1，t，sti2n ，j2nj 1，n1，nj-1，t。（三）利用初始条件sti，j，0，0，t，可以使用动态编程技术来计算预处理函数。因此，空间和时间复杂度都是（N* logN *T）。其次，选择完全覆盖区域[i1，i2]*[j1，j2]的两个子集，然后找到最大值在m之间。 因此，我们有0.5*（i1i2）i2ui 你好，我是来找你的。 Le t uio g（i 21 1）且ujlog（j21）。查询过程仅需要时间复杂性，并且对于mul，n由下式给出：Huan Wang等人/ IERI Procedia 10（2014）138141maxtmaxs ti1，j1，u i，uj，t，sti2ui1，j1，ui，uj，t，sti1，j2-2uj1，ui，uj，t，sti221，j2-2uj1，ui，uj，t。 （四）4. 时变数据分析由于时变数据的普遍存在性，各种各样的数据挖掘方法已经被不同的研究团体应用，如股票市场研究人员，信号处理工程师和企业收入预测者[12]。然而，其范围通常是有限的。在我们的应用中，我们需要设计一种方法，不仅可以分析局部数据的变化趋势，而且可以很容易地观察到全局趋势。增长矩阵法是解决这一问题的一个很好的方法。它是由Daniel A. 2006年《金融分析》[13]。与传统的图表技术不同，它将二维信息转化为三维信息，可以显示更多隐藏的信息，更好地利用人类对颜色的敏感性。图二. (a)左侧：最小查询结果的可视化分析;它显示了1850年至2048年的全球气温;紫色圈出的黑色区域表示附近的温度波动很大;（b）中间：可视化分析系统的完整视图;（c）右：GAMIL数据集的可视化对于大小为T的时间序列S，首先生成2d三角形布局L，其中水平轴表示开始时间i，垂直轴表示结束时间 j，以及L（i，j）表示GM（i，j）的值，GM（i，j）是S（i）和S（j）的函数。这种基本技术不仅可以可视化不同尺度（天，周，月，年）的内部效应，还可以可视化不同时间序列的内部效应。如图在下面的图2中，将构造的三角矩阵GM映射到图像线性布局L。 因此，L上的每一位的颜色L（i，j） 代表了S.通常，选择GM（i，j）=S（i）-S（j）5. 执行我们的系统是用C++和Java Applet实现的。该系统由3层组成：资源和基础设施层、业务层和中间层，如图3所示。在业务层，数据转换模型基本上消除了数据噪音并统一了格式（通常是NETCDF[14]）。将查询窗口的位置、大小等查询参数打包传输到服务器端的查询引擎模型中。查询引擎负责从磁盘中提取数据，并将时间序列反馈给客户端，客户端可以在（1）时间内响应。在显示层，管理员可以使用命令行与服务器交互，用户可以使用浏览器访问客户端。用户还可以使用平铺式LCD显示器以获得超分辨率图像。142Huan Wang等人/ IERI Procedia 10（2014）138图三.海量时空数据超分辨率图像及其可视化对地球科学研究具有重要意义。当使用更高的分辨率时，更容易观察到细微的天气现象和细粒度的细节。例如，1°纬度× 1°经度分辨率生成64，800个数据点，而0.25°纬度×0.25°经度分辨率生成1，036，800个数据点，这意味着16倍的计算量。我们的拼接式LCD显示器完全由普通商品部件制成，这有助于我们使用每像素价格最低的技术。如图4所示，显示环境被选择为4*6平铺布局，每个平铺1440*960分辨率。见图4。可视化分析系统6. 实验在实验中，为了验证系统的正确性，我们首先生成了一组正弦波数据，并为每个数据集随机创建了数百个查询矩形。我们还测试了大气物理研究所的GAMIL数据集，以验证3d时空数据集，大小为362*196*30，时间片为120，如图2（b）和（c）所示。为了进行性能分析，我们在Linux操作系统上进行了测试，4个Intel（R）Core（TM）i7 CPU，每个8个内核，2.67 GHz，20 GB内存和100 Mbit/s的局域网环境。我们使用普林斯顿大学水文气候小组模拟的偏差校正的向下长波辐射通量数据集（dlwrf），大小为360*180*1，时间切片为2920*5（2003年至2007年的3小时输出），如图2（a）所示。我们发现查询速度几乎是实时的。查询窗口可以任意拖动，几乎没有任何延迟，延迟或抖动。7. 结论数据驱动的可视化分析是近年来科学研究中一项很有前途的新技术。本文设计并实现了一个基于窗口查询和增长矩阵的海量时空数据分析工具包。在实验中，我们采用了大屏幕技术，Huan Wang等人/ IERI Procedia 10（2014）138143显示超分辨率气候模拟数据。事实证明，我们的高性价比大屏幕拼接液晶显示器解决方案提供了高性能的超分辨率可视化显示。在未来，我们将把系统扩展到更多的统计变量，如中位数，异常。今后应支持对不同领域、变量和数据集进行多变量直观分析。我们还希望探索如何更好地设计海量时空气候数据的范围查询算法，而不仅仅局限于窗口查询。确认作者非常感谢张亮、赵慧明的系统开发和清华大学地球系统科学中心的数据支持。本研究得到了国家高技术研究发展计划（863计划）第二阶段的资助。2010AA012402。引用[1] 王斌。一种典型的高性能计算：地球系统建模：地球系统模拟[J].物理，2009，38（08）：0-0.[2] 王文，王文，等.可视化分析方法及其应用[M].北京：科学出版社，1999. Springer BerlinHeidelberg，2008.[3] 放大图片作者：John W，Martin K.引用该论文张文军，张文军，张文军. 一九九六年。[4] “VisItWeb Site”，Lawrence Livermore National Laboratory，http://www.llnl.gov/visit。[5] 王培昌，沈宏伟，庄俊荣，等.大规模可视化分析中的十大挑战[J]. IEEE计算机图形学与应用，2012，32（4）：63.[6] 波丽几何范围查询算法研究[D].哈尔滨理工大学，2008。[7] 放大图片作者：Shi Q，JaJa J.中国科学技术出版社，2002.诉讼第14届IEEE国际会议，2002：142-151.[8] 沙美湾多维度量数据结构基础[M].摩根·考夫曼，2006年。[9] D M山公园E一种近似值域搜索的动态数据结构[C]//第26届计算几何年会论文集. ACM，2010：247-256.[10] 王文，王文，等.基于向量机的组合模式匹配算法的研究[J].计算机学报，2000，24（1）：119- 119. Springer Berlin Heidelberg，2006：36-48.[11] 放大图片作者：Bender M.水平祖先问题的简化[J].理论计算机科学，2004，321（1）：5-12.[12] 李晓，李晓，等.大规模时间序列的可视化挖掘与监控[C].北京：清华大学出版社，2001.ACM，2004：460-469。[13] 王晓云，王晓云，等.金融时间序列数据的谱可视化分析[C].北京：科学出版社，1999. 2006年：第195-202页。[14] Rew R，Davis G. NetCDF：一种科学数据访问接口[J].计算机图形学与应用，IEEE，1990，10（4）：76-82.
我的内容管理
展开
