方法
Parallel HEALPix-index
function ( 12 47 on ( 12 48 )
Parallel HEALPix-index
function ( 12 49 )
Parallel HTM-index
function ( 8 48 )
• 画框：降低计算复杂度
RA_ A RA_ B
r1 r2
cos((DEC _ A DEC _ B) / 2)
DEC _ A DEC _ B r1 r2
• 基于伪二维球面索引的划分方法
HEALPix
HTM
• 使用伪二维球面索引的好处
– 嵌套的层次编号方式: 临近块的ID编码只区别在低位， 且如果Q1区域包含Q2区域，则Q2的编码以Q1的编码 为前缀。
• 数据加载计算流程：Boundary Growing Model
– 减少I/O读取耗时，抑制内存填充速度
• 最大生长块概念
•增强Boundary Growing Model效果
•自适应于天体密度
•过滤空白区域
• 自顶向下的最大生长块快速确定方式
Empty Table of 00101001
E
E
00101001010101
E
E
00101001110000
EE
EE
00101001110001
EE
EE
00101001110010
00101001110011
00101001111100
00101001
Found biggest blocks
• 并行算法设计
• 研究意义
– 虚拟天文台项目数据访问服务的核心模块 – LAMOST望远镜大科学工程三大子课题之一 – 中国科学院天文科学主题库索引层建设的必
要技术 – 统计分析、数据挖掘的基础
多核环境下的并行交叉证认的研究
• 研究意义：
– 当今处理器芯片已经步入多核时代，多核计算资源的 普及所带来的强大的计算能力为天文学中很多大规模 计算难题的解决提供了新的途径
• 国家“十一·五” 开始提出并已开 始建设的世界最 大的单口径射电 望远镜 —— 500 米口径球面射电 天文望远镜 （FAST）。
• 美国LSST望远镜，8.4米口径大尺度概要巡天 望远镜，每晚将产生数据量高达18TB，相当于 28000张普通光盘的容量。
• 关键是解决交叉证认的高效性需求与海量 的天文观测数据量之间的矛盾，因此交叉 证认是典型的数据密集型、I/O密集型计算 难题！
• 总结与展望
研究背景及意义
• 天文多波段交叉证认的概念
• 基于位置信息的交叉证认
d 3 r12 r22
• 主要面临挑战：
– 天文观测设备的日新月异所带来的天文数据 的海量性：TB乃至PB量级，且呈类摩尔定律 增长
• LAMOST望 远镜，全称： 大天区面积 多目标光纤 光谱天文望 远镜
• 2008年10月 建成，每夜 能观测上万 个天体的光 谱，世界上 威力最大， 最重要的天 文望远镜之 一
算块任务
无
向从进程发送 “结束”命令
其中一个子进程 开始
接收主进程消息
结束命令
消息类型
结束
计算块 块号
计算星表B中该 计算块的边界
块编码
查询星表A数 据库表
查询星表B数据 库表（中心块+
边界块）
两两数据间距 离计算
结束
向主进程发送 结果回收请求
有
有无证认结果
无
请求新任务
• 实验结果及分析
Aladin 可视化结果：
470,992,970 57分钟
SDSS
100,106,811 2MASS
470,992,970 40分钟
SDSS
100,106,811
SDSS
100,106,811
Part of GSC 295,832 2.3
2MASS
2MASS
Generat from GSC2.3
470,992,970 470,992,970 295,832
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索引特性的利用
73小时 78分钟 5.8分钟
• 分析
– 与原高丹的方法相比，效率提高显著
– 计算耗时与查询数据耗时间的平衡：划分粒度过细， 边缘数据的比例升高， B-tree索引特性决定非连续数 据查询效率较低；划分粒度过粗，则计算量较高。
– HTM索引与HEALPix索引相比：
• 相同面积下正三角形的周长大于正方形的边长
天津大学博士研究生毕业答辩
面向海量数据的 高效天文交叉证认的研究
答辩人：赵青 指导老师：孙济洲 教授
天津大学计算机学院 Email: zhaoqing@
主要内容 • 研究背景及意义
• 面向多核环境的并行交叉证认方法
• 面向分布式集群环境的交叉证认方法
• 面向HEALPix和HTM索引的快速邻域编码计算 算法
赤纬单维索引方法
简单网格天区划分方法
高丹（KD-tree+HTM）
星表A来源 SDSS
星表A数据 量
100,106,811
星表B来源 2MASS
星表B数据 量
470,992,970
运行总耗时 32分钟
SDSS
100,106,811 2MASS
470,992,970 25分钟
SDSS
100,106,811 2MASS
✓ 任务分配方式简单，容易实现负载平衡
– 通用性
简 单 网 格 天 区 划 分 方 式
• 边界漏源问题的解决
快速相邻块编码计算算法
• 并行方法设计
主进程
开始
向各子进程分 配待证认的计
算块块号
接收子进程消息
结果返回
接收证认结果
消息类型
写入数据库
请求 新任 务
是否还有尚待证 有 分配新的计
认的计算块
✓ 适合B-tree索引，物理上相近的块 其块号在数值上也连续或 相近，自然地实现了临近区域的聚类，适合于一切SQL系统。
✓ 一次索引，可进行多级精度上的计算，便于选取最合适索引 块和计算块的级数。不同密度、速度的星体可选择不同距离 阈值。
– 等面积
✓ 与简单网格天区划分方式相比，省去了对赤经的修正 (spherical-polar distortion problem )，避免了复杂的球面坐标