面向海量数据的 高效天文交叉证认的研究 答辩人：赵青 指导老师：孙济洲 教授 天津大学计算机学院 天津大学博士研究生毕业答辩 面向海量数据的 高效天文交叉证认的研究 答辩人：赵青 指导老师：孙济洲 教授 天津大学计算机学院 Email: zhaoqing@tju.edu.cn

主要内容 研究背景及意义 面向多核环境的并行交叉证认方法 面向分布式集群环境的交叉证认方法 面向HEALPix和HTM索引的快速邻域编码计算算法 总结与展望

天文多波段交叉证认的概念 基于位置信息的交叉证认 主要面临挑战： 研究背景及意义 天文观测设备的日新月异所带来的天文数据的海量性：TB乃至PB量级，且呈类摩尔定律增长

LAMOST望远镜，全称：大天区面积多目标光纤光谱天文望远镜 2008年10月建成，每夜能观测上万个天体的光谱，世界上威力最大，最重要的天文望远镜之一

国家“十一·五” 开始提出并已开始建设的世界最大的单口径射电望远镜 —— 500米口径球面射电天文望远镜（FAST）。

美国LSST望远镜，8.4米口径大尺度概要巡天望远镜，每晚将产生数据量高达18TB，相当于28000张普通光盘的容量。

关键是解决交叉证认的高效性需求与海量的天文观测数据量之间的矛盾，因此交叉证认是典型的数据密集型、I/O密集型计算难题！ 研究意义 虚拟天文台项目数据访问服务的核心模块 LAMOST望远镜大科学工程三大子课题之一 中国科学院天文科学主题库索引层建设的必要技术 统计分析、数据挖掘的基础

研究意义： 画框：降低计算复杂度 基于伪二维球面索引的划分方法 多核环境下的并行交叉证认的研究 当今处理器芯片已经步入多核时代，多核计算资源的普及所带来的强大的计算能力为天文学中很多大规模计算难题的解决提供了新的途径 画框：降低计算复杂度 基于伪二维球面索引的划分方法 HEALPix HTM

使用伪二维球面索引的好处 嵌套的层次编号方式: 临近块的ID编码只区别在低位，且如果Q1区域包含Q2区域，则Q2的编码以Q1的编码为前缀。 适合B-tree索引，物理上相近的块 其块号在数值上也连续或相近，自然地实现了临近区域的聚类，适合于一切SQL系统。 一次索引，可进行多级精度上的计算，便于选取最合适索引块和计算块的级数。不同密度、速度的星体可选择不同距离阈值。 等面积 与简单网格天区划分方式相比，省去了对赤经的修正(spherical-polar distortion problem )，避免了复杂的球面坐标 任务分配方式简单，容易实现负载平衡 通用性

边界漏源问题的解决 简单网格天区划分方式 快速相邻块编码计算算法

并行方法设计

实验结果及分析 Aladin 可视化结果： 方法 星表A来源 星表A数据量 星表B来源 星表B数据量 运行总耗时 Parallel HEALPix-index function ( ) SDSS 100,106,811 2MASS 470,992,970 32分钟 25分钟 57分钟 Parallel HTM-index function ( ) 40分钟 赤纬单维索引方法 73小时 简单网格天区划分方法 78分钟 高丹（KD-tree+HTM） Part of GSC 2.3 295,832 Generat from GSC2.3 5.8分钟

number of blocks bordering one compute-block 分析 与原高丹的方法相比，效率提高显著 计算耗时与查询数据耗时间的平衡：划分粒度过细，边缘数据的比例升高， B-tree索引特性决定非连续数据查询效率较低；划分粒度过粗，则计算量较高。 HTM索引与HEALPix索引相比： 相同面积下正三角形的周长大于正方形的边长 Version number of blocks bordering one compute-block HealPix 4*2^n+4 1 HTM 3*[2^(n+1)]+6 1.5

基于Boundary Growing Model的改进方法 解决最主要性能瓶颈：频繁的I/O操作耗时 数据库B-tree索引特性的利用 数据加载计算流程：Boundary Growing Model 减少I/O读取耗时，抑制内存填充速度

最大生长块概念 自顶向下的最大生长块快速确定方式 增强Boundary Growing Model效果 自适应于天体密度 过滤空白区域

并行算法设计

实验结果及分析 实验一：稀疏数据集上的实验 SDSS DR6星表（约1亿条数据）、2MASS星表（约4.7亿条数据） 原始方法与改进方法的对比： 计算块分块数量 SDSS数据库查询 2MASS数据库 查询 （中心块） 2MASS数据库查询(边界块) 距离计算 其他 总用时 307s 59s 335s 580s 40s 1321s 317s 639s 151s 44s 1191s 427s 54s 1177s 51s 72s 1781s 计算块分块数量 SDSS数据库查询 2MASS数据库查询 距离计算 其他 总用时 120s 78s 2489s 48s 2735s 127s 79s 690s 58s 954s 191s 102s 199s 57s 549s 374s 239s 67s 738s

实验二：非稀疏数据集上的实验 数据集：SDSS：47949212条记录、2MASS：35476377条记录 原始方法与改进方法的对比： 计算块分块数 SDSS数据库查询 2MASS数据库查询 （中心块） 2MASS数据库查询(边界块) 距离计算 其他 总用时 33s 17s 124s 96s 16s 286s 19s 191s 24s 283s 43s 28s 403s 11s 22s 507s 计算块分块数 SDSS数据库查询 2MASS数据库查询 距离计算 其他 总用时 32s 19s 421s 27s 499s 36s 20s 130s 213s 46s 39s 31s 143s 107s 60s 11s 210s

面向HTM索引的可行性分析 优化边界问题的解决方法 限制生长模型

基于MapReduce分布式模型的交叉证认 意义： 数据急速增长，长期考虑，多核单机环境并不现实 突破关系数据库在处理海量数据时的瓶颈 利用大规模集群获得更强大的计算能力，进一步提高效率，为实现在线实时交叉证认和联合查询打下基础

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

Step1:数据分布式存放（Map+Reduce） Shuffle/Sort Chop/replicate 数据块头部 星表A记录组 星表B记录组 （块号+来源，属性） Map Reduce Map Map 输入星表数据 Reduce Map Map Reduce Map

Step2: 证认计算（Map） 证认结果 Map Map Map Map Map Result Result Result Result 数据块头部 星表A记录组 星表B记录组 证认结果 Map Result Map Result Map Result Map Result Map Result

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

面向HEALPix和HTM索引的快速邻域编码计算算法 研究意义 各种交叉证认方法得以高效实现的必要前提

在各种天文数据查询、数据处理上有着广泛的应用空间，如“锥形检索服务” r （ α，δ ）

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

块“2”编码： 块“4”编码： 块“6”编码： 块“8”编码： 块“1”编码： 块“3”编码： 块“5”编码： 块“7”编码：

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

块“0”编码： 块“1”编码： 块“2”编码：

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

未来展望 研究基于数据挖掘、概率统计等更复杂交叉证认方法在海量数据上的效率问题，争取更高的证认精确度。 研究并实现可在线访问的交叉证认服务系统。要构建出具有实际应用价值的交叉证认系统还有许多工作要做，包括多种数据源间的格式转换、多层系统架构的实现、对多种交叉证认扩展方法的支持、与数据查询系统的整合等。 基于交叉证认计算中具有的数据间独立性，可为更加复杂、更加专用的交叉证认方法提供基于数据划分的自动并行化方法，由此可进一步设计开发出支持多种交叉证认方法扩展的自动并行化系统

谢谢各位老师！ 请您们给予指点！