面向海量数据的高效天文交叉证认的研究

1、1面向海量数据的面向海量数据的高效天文交叉证认的研究高效天文交叉证认的研究答辩人：赵青指导老师：孙济洲 教授Email: 2主要内容主要内容 研究背景及意义 面向多核环境的并行交叉证认方法 面向分布式集群环境的交叉证认方法 面向HEALPix和HTM索引的快速邻域编码计算算法 总结与展望3研究背景及意义研究背景及意义 天文多波段交叉证认的概念 基于位置信息的交叉证认 主要面临挑战： 天文观测设备的日新月异所带来的天文数据的海量性：TB乃至PB量级，且呈类摩尔定律增长22)_()2/ )_cos()_(BDECADECBDECADECBRAARAd22213rrd4 LAMOST望远镜，全称：大

2、天区面积多目标光纤光谱天文望远镜 2008年10月建成，每夜能观测上万个天体的光谱，世界上威力最大，最重要的天文望远镜之一 5 国家“十一五” 开始提出并已开始建设的世界最大的单口径射电望远镜 500米口径球面射电天文望远镜（FAST）。 6 美国LSST望远镜，8.4米口径大尺度概要巡天望远镜，每晚将产生数据量高达18TB，相当于28000张普通光盘的容量。7 关键是解决交叉证认的高效性需求与海量的天文观测数据量之间的矛盾，因此交叉证认是典型的数据密集型、I/O密集型计算难题！ 研究意义 虚拟天文台项目数据访问服务的核心模块 LAMOST望远镜大科学工程三大子课题之一 中国科学院天文科学主题

3、库索引层建设的必要技术 统计分析、数据挖掘的基础8多核环境下的并行交叉证认的研究多核环境下的并行交叉证认的研究 研究意义： 当今处理器芯片已经步入多核时代，多核计算资源的普及所带来的强大的计算能力为天文学中很多大规模计算难题的解决提供了新的途径 画框：降低计算复杂度 基于伪二维球面索引的划分方法2121_)2/ )_cos(_rrBDECADECBDECADECrrBRAARAHEALPixHTM9 使用伪二维球面索引的好处 嵌套的层次编号方式: 临近块的ID编码只区别在低位，且如果Q1区域包含Q2区域，则Q2的编码以Q1的编码为前缀。适合B-tree索引，物理上相近的块 其块号在数值上也连续

4、或相近，自然地实现了临近区域的聚类，适合于一切SQL系统。一次索引，可进行多级精度上的计算，便于选取最合适索引块和计算块的级数。不同密度、速度的星体可选择不同距离阈值。 等面积与简单网格天区划分方式相比，省去了对赤经的修正(spherical-polar distortion problem )，避免了复杂的球面坐标任务分配方式简单，容易实现负载平衡 通用性10 边界漏源问题的解决快速相邻块编码计算算法简单网格天区划分方式11 并行方法设计12 实验结果及分析Aladin 可视化结果：8412方法星表A来源星表A数据量星表B来源星表B数据量运行总耗时Parallel HEALPix-index

5、 function ( )SDSS100,106,811 2MASS470,992,970 32分钟Parallel HEALPix-index function ( )SDSS100,106,8112MASS470,992,970 25分钟Parallel HEALPix-index function ( )SDSS100,106,8112MASS470,992,970 57分钟Parallel HTM-index function ( )SDSS100,106,8112MASS470,992,97040分钟赤纬单维索引方法SDSS100,106,8112MASS470,992,97073小

6、时简单网格天区划分方法SDSS100,106,8112MASS470,992,97078分钟高丹（KD-tree+HTM）Part of GSC 2.3 295,832 Generat from GSC2.3 295,832 5.8分钟9412741284813 分析 与原高丹的方法相比，效率提高显著 计算耗时与查询数据耗时间的平衡：划分粒度过细，边缘数据的比例升高， B-tree索引特性决定非连续数据查询效率较低；划分粒度过粗，则计算量较高。 HTM索引与HEALPix索引相比： 相同面积下正三角形的周长大于正方形的边长14基于基于Boundary Growing Model的改进方法的改进

7、方法 数据库B-tree索引特性的利用 数据加载计算流程：Boundary Growing Model 减少I/O读取耗时，抑制内存填充速度解决最主要性能瓶颈：频繁的解决最主要性能瓶颈：频繁的I/O操作耗时操作耗时15 最大生长块概念 自顶向下的最大生长块快速确定方式增强Boundary Growing Model效果自适应于天体密度过滤空白区域16 并行算法设计17 实验结果及分析 实验一：稀疏数据集上的实验 SDSS DR6星表（约1亿条数据）、2MASS星表（约4.7亿条数据） 原始方法与改进方法的对比：7412841294127412841294121041218 实验二：非稀疏数据集

8、上的实验数据集：SDSS：47949212条记录、2MASS：35476377条记录 原始方法与改进方法的对比：7412841294127412841294121041219面向面向HTM索引的可行性分析索引的可行性分析 优化边界问题的解决方法 限制生长模型20基于基于MapReduce分布式模型的交叉证认分布式模型的交叉证认 意义： 数据急速增长，长期考虑，多核单机环境并不现实 突破关系数据库在处理海量数据时的瓶颈 利用大规模集群获得更强大的计算能力，进一步提高效率，为实现在线实时交叉证认和联合查询打下基础21MapReduce模型模型 概念： MapReduce是Google在2004年提

9、出的一个编程模型，并已于2010年年初正式申请获批该项技术的专利。它主要用以进行大规模数据集上的并行运算，其主要概念“Map（映射）”和“Reduce（规约）”最初借鉴于函数式编程语言。 优点： 适合处理海量数据，尤其适合于数据间存在较强独立性的应用； 成本低廉，使原本必须借助于非常高昂的超级计算机才能获得的计算能力可以在大量廉价机器上同样实现； 易于编程，将任务分发、任务调度、数据分布、容错处理、负载平衡等并行计算中不可避免的复杂控制细节隐藏于系统的运行时后台处理中22Step1:数据分布式存放（数据分布式存放（Map+Reduce）输入星表数据MapMapMapMapMapMapReduc

10、eReduceShuffle/SortChop/replicate（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）（块号+来源，属性）Reduce数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组23Step2:

11、证认计算（证认计算（Map）数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组数据块头部星表A记录组星表B记录组MapMapMapMapMapResultResultResultResultResult证认结果24实验实验 实验结果： 证认部分耗时：25秒 达到接近线性的加速比 意义： 确认了文件数据库在处理海量数据方面的优势 大幅度缩短大星表交叉证认计算用时，为最终实现实时联合查询服务提供了条件 充分利用了廉价的计算资源，对于快速增长的天文数据量具有良好的可扩展性，为今后天

12、文数据处理提供了一种可行的方案。25面向面向HEALPix和和HTM索引的快速邻域编码计算算法索引的快速邻域编码计算算法 研究意义 各种交叉证认方法得以高效实现的必要前提26 在各种天文数据查询、数据处理上有着广泛的应用空间，如“锥形检索服务”r（ ， ）27HEALPix索引下的邻接块编码计算算法索引下的邻接块编码计算算法异或运算之第二操作数求解规则：如果最终目标是求东北方向的共边邻接块，即图中标志为“2”的邻接块，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找第一次出现的“00”或“10”，从该位开始直到最后一位间的每两位均变成“01”，而更高位上均为“0”；如果最

13、终目标是求西南方向的共边邻接块，即图中标志为“6”的邻接块，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找第一次出现的“00”或“01”，从该位开始直到最后一位间的每两位均变成“01”，而更高位上均为“0”；如果最终目标是求东南方向的共边邻接块，即图中标志为“4”的邻接块，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找第一次出现的“11”或“10”，从该位开始直到最后一位间的每两位均变成“10”，而更高位上均为“0”；如果最终目标是求西北方向的共边邻接块，即图中标志为“8”的邻接块，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高

14、位寻找第一次出现的“00”或“01”，从该位开始直到最后一位间的每两位均变成“10”，而更高位上均为“0”； 28 块“2”编码： 块“4”编码： 块“6”编码： 块“8”编码： 块“1”编码： 块“3”编码： 块“5”编码： 块“7”编码： 1101101000010101110011111100110100000010110011111100111000000001110011111110010100101010110011111101101000010101110011111111000000101010110110101101101000010101110011111101100000

15、0000101101101011001101000000101100111111001100000000011001101111001110000000011100111111100100001010101100111029HTM索引下的邻接块编码计算算法索引下的邻接块编码计算算法异或运算之第二操作数求解规则：如果最终目标是求1号角对边方向的邻接三角形编码，即标记为“1”的邻接块，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找第一次出现的“01”或“11”位，如果找到的是“01”，则从该位开始直到最后一位间的每两位均为“11”，如果找到的是“11”，则从该位开始直到最后

16、一位间的每两位均为“10”，而更高位上均为“0”；如果最终目标是求0号角对边方向的邻接三角形编码，即标记为“0”的邻接块，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找第一次出现的“00”或“11”位，无论找到的是“00”还是“11”，都从该位开始直到最后一位间的每两位均设定为“11”，而更高位上均为“0”；如果最终目标是求2号角对边方向的邻接三角形编码，即标记为“2”的邻接块，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找第一次出现的“10”或“11”位，无论找到的是“10”还是“11”，都从该位开始直到最后一位间的每两位均设定为“01”，而更

17、高位上均为“0”； 30 块“0”编码： 块“1”编码： 块“2”编码： 00111011000000110011100000111101000001010011100000010010001010100011100031 实验结果： 计算 个HEALPix计算块中的每个计算块周围一圈的 个邻接HEALPix原子块的全部HEALPix编码（包含 次“同等划分级别下的邻接块编码计算”和 次“块内边界小块编码计算”） 总耗时：0.82秒 计算全天区 个HTM计算块中的每个计算块周围一圈的 个邻接HTM原子块的全部HTM编码（包含 次“同等划分级别下的邻接块编码计算”和 次“块内边界小块编码计算”） 总耗时：1.23秒 结论： 为高效交叉证认方法的实现奠定了基础，同时也在多种面向海量数据的天文数据处理中有着重要的应用价值。84884834888412528