大数据量交叉证认算法研究-LAMOST.ppt

高丹中国虚拟天文台研发团队,ChineseVirtualObservatory,大数据量交叉证认算法研究,11/29-12/03,China-VO2006,Guilin,2,内容,星表介绍交叉证认的意义现有的交叉证认工具交叉证认概念交叉证认方法比较B-tree索引HTM索引HTM索引分区+kdtree进一步工作,11/29-12/03,China-VO2006,Guilin,3,星表,星表是包含天体信息（如赤经、赤纬、星等、流量）的二维数据表格多波段：光学、红外、射电、X射线等星表的每一行对应一个天体，不同星表的同一天体的共同属性是位置信息赤经：0360度赤纬：-9090度,11/29-12/03,China-VO2006,Guilin,4,星表实例,11/29-12/03,China-VO2006,Guilin,5,交叉证认的必要性,多波段数据急剧增长革命性步骤：数据融合联系桥梁：位置交叉证认,11/29-12/03,China-VO2006,Guilin,6,交叉证认的意义,多波段数据融合，获得天体多波段信息对天体的物理性质、演化规律获得更全面系统的认识为进一步的统计分析、数据挖掘做准备提取天体的参数越多，越有利于天体分类和测光红移的计算增加了发现新天体的概率LAMOST三大核心子课题之一虚拟天文台数据融合必由之路,11/29-12/03,China-VO2006,Guilin,7,现有的交叉证认工具,SIMBADALADINNEDMASTTOPCATOpenSkyqueryGVO-cross-match,11/29-12/03,China-VO2006,Guilin,8,现有工具的优缺点,优点：界面友好数据资源丰富缺点：不能进行大样本的交叉证认参数不能自由选择交叉证认结果需要用户进一步加工没有对结果进行分类没给出交叉证认的概率只能与特定的数据交叉证认,11/29-12/03,China-VO2006,Guilin,9,交叉证认的概念,将不同星表或数据库中的源按位置属性将它们联系起来，在相同位置的源或一定误差半径范围内的源，被证认为是同一天体。,11/29-12/03,China-VO2006,Guilin,10,证认的判断方法,有两个源分别在星表a、b中，它们的误差半径分别为r1，r2，它们的之间的球面距离为d。如果它们的关系满足，则认为它们是同一天体。,（1）,11/29-12/03,China-VO2006,Guilin,11,证认的判断方法（例子）,2MASS：r1=0.1ra=357.661036243116,decl=0.434507548194SDSS：r2=0.1ra=357.661059,decl=0.434484d：0.000032746961两个源满足(1)式，被证认为同一个天体,11/29-12/03,China-VO2006,Guilin,12,索引,Indexingmechanismsusedtospeedupaccesstodesireddata.,11/29-12/03,China-VO2006,Guilin,13,B-tree索引的交叉证认,为星表的ra，decl两列建B-tree索引以小表为中心，在大表中遍历寻找证认源以(1)式为判断算法复杂度O(N*N),11/29-12/03,China-VO2006,Guilin,14,B-tree索引的交叉证认（续）,11/29-12/03,China-VO2006,Guilin,15,B-tree索引方法优缺点,优点：证认精度高缺点：内存限制，索引不好速度慢，算法复杂度高,11/29-12/03,China-VO2006,Guilin,16,HTM,TheSpatialIndexisaquadtreeofsphericaltriangles.Thetreeisbuiltinthefollowingway:Startoutwith8trianglesonthesphereusingthe3maincirclestodeterminethem.Then,everytrianglecanbedecomposedinto4newtrianglesbydrawingmaincirclesbetweenmidpointsofitsedges,11/29-12/03,China-VO2006,Guilin,17,HTMpcode,ra=45.0,decl=66.0,level=14N313330303330003,11/29-12/03,China-VO2006,Guilin,18,HTMlevel,LevelArea(arcmin2)NumLeaves101.77E18,388,608111.43E033,554,432121.11E0134,217,728132.77E-1536,870,912146.92E-22,147,483,648151.73E-28,589,934,592201.69E-58,796,093,022,208251.65E-89,007,199,254,740,922,11/29-12/03,China-VO2006,Guilin,19,HTM索引的交叉证认,由星表的精度选取一定的HTM级数由星表的ra,decl计算出HTMpcode值两个B-tree索引一个空间索引N*N遍历自然连接省去(1)式判断，要求两个星表级数一样，即精度差不多,11/29-12/03,China-VO2006,Guilin,20,HTM索引的交叉证认（续）,11/29-12/03,China-VO2006,Guilin,21,HTM索引方法优缺点,优点：索引好，空间索引解决了内存限制问题缺点：速度慢，没有解决算法复杂度问题认证精度低漏源概率高大量一对多、多对一混杂要求两个表精度差不多,11/29-12/03,China-VO2006,Guilin,22,HTM索引分区+kdtree的交叉证认,以小表为中心，把HTM索引当作分区对每个分区的大表，把ra、decl作为参数建kdtree对每个分区内的每个源，在kdtree中找最近邻用(1)式证认判断HTM级数比星表精度低，漏源可能性小,11/29-12/03,China-VO2006,Guilin,23,HTM索引分区+kdtree方法优缺点,优点：索引好，空间索引解决了内存限制问题分区，算法复杂度降低，速度快证认精度高缺点：HTM级数难确定,11/29-12/03,China-VO2006,Guilin,24,进一步工作,进一步改进和优化算法尝试其他索引算法，如HEALpix优化交叉证认界面实现参数自由选择和加工计算证认的概率提供与上层的数据挖掘和可视化工具的接口集成一些现有的数据挖掘算法，开发面向天文数据特点的挖掘工具,11/29-12/03,China-VO2006,Guilin,25,Thankyou!,Q&A,?,www.org,