1、1面向海量數(shù)據(jù)的面向海量數(shù)據(jù)的高效天文交叉證認(rèn)的研究高效天文交叉證認(rèn)的研究答辯人：趙青指導(dǎo)老師：孫濟(jì)洲 教授Email: 2主要內(nèi)容主要內(nèi)容 研究背景及意義 面向多核環(huán)境的并行交叉證認(rèn)方法 面向分布式集群環(huán)境的交叉證認(rèn)方法 面向HEALPix和HTM索引的快速鄰域編碼計(jì)算算法 總結(jié)與展望3研究背景及意義研究背景及意義 天文多波段交叉證認(rèn)的概念 基于位置信息的交叉證認(rèn) 主要面臨挑戰(zhàn)： 天文觀測設(shè)備的日新月異所帶來的天文數(shù)據(jù)的海量性：TB乃至PB量級(jí)，且呈類摩爾定律增長22)_()2/ )_cos()_(BDECADECBDECADECBRAARAd22213rrd4 LAMOST望遠(yuǎn)鏡，全稱：大

2、天區(qū)面積多目標(biāo)光纖光譜天文望遠(yuǎn)鏡 2008年10月建成，每夜能觀測上萬個(gè)天體的光譜，世界上威力最大，最重要的天文望遠(yuǎn)鏡之一 5 國家“十一五” 開始提出并已開始建設(shè)的世界最大的單口徑射電望遠(yuǎn)鏡 500米口徑球面射電天文望遠(yuǎn)鏡（FAST）。 6 美國LSST望遠(yuǎn)鏡，8.4米口徑大尺度概要巡天望遠(yuǎn)鏡，每晚將產(chǎn)生數(shù)據(jù)量高達(dá)18TB，相當(dāng)于28000張普通光盤的容量。7 關(guān)鍵是解決交叉證認(rèn)的高效性需求與海量的天文觀測數(shù)據(jù)量之間的矛盾，因此交叉證認(rèn)是典型的數(shù)據(jù)密集型、I/O密集型計(jì)算難題！ 研究意義 虛擬天文臺(tái)項(xiàng)目數(shù)據(jù)訪問服務(wù)的核心模塊 LAMOST望遠(yuǎn)鏡大科學(xué)工程三大子課題之一 中國科學(xué)院天文科學(xué)主題

3、庫索引層建設(shè)的必要技術(shù) 統(tǒng)計(jì)分析、數(shù)據(jù)挖掘的基礎(chǔ)8多核環(huán)境下的并行交叉證認(rèn)的研究多核環(huán)境下的并行交叉證認(rèn)的研究 研究意義： 當(dāng)今處理器芯片已經(jīng)步入多核時(shí)代，多核計(jì)算資源的普及所帶來的強(qiáng)大的計(jì)算能力為天文學(xué)中很多大規(guī)模計(jì)算難題的解決提供了新的途徑 畫框：降低計(jì)算復(fù)雜度 基于偽二維球面索引的劃分方法2121_)2/ )_cos(_rrBDECADECBDECADECrrBRAARAHEALPixHTM9 使用偽二維球面索引的好處 嵌套的層次編號(hào)方式: 臨近塊的ID編碼只區(qū)別在低位，且如果Q1區(qū)域包含Q2區(qū)域，則Q2的編碼以Q1的編碼為前綴。適合B-tree索引，物理上相近的塊 其塊號(hào)在數(shù)值上也連續(xù)

4、或相近，自然地實(shí)現(xiàn)了臨近區(qū)域的聚類，適合于一切SQL系統(tǒng)。一次索引，可進(jìn)行多級(jí)精度上的計(jì)算，便于選取最合適索引塊和計(jì)算塊的級(jí)數(shù)。不同密度、速度的星體可選擇不同距離閾值。 等面積與簡單網(wǎng)格天區(qū)劃分方式相比，省去了對(duì)赤經(jīng)的修正(spherical-polar distortion problem )，避免了復(fù)雜的球面坐標(biāo)任務(wù)分配方式簡單，容易實(shí)現(xiàn)負(fù)載平衡 通用性10 邊界漏源問題的解決快速相鄰塊編碼計(jì)算算法簡單網(wǎng)格天區(qū)劃分方式11 并行方法設(shè)計(jì)12 實(shí)驗(yàn)結(jié)果及分析Aladin 可視化結(jié)果：8412方法星表A來源星表A數(shù)據(jù)量星表B來源星表B數(shù)據(jù)量運(yùn)行總耗時(shí)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、時(shí)簡單網(wǎng)格天區(qū)劃分方法SDSS100,106,8112MASS470,992,97078分鐘高丹（KD-tree+HTM）Part of GSC 2.3 295,832 Generat from GSC2.3 295,832 5.8分鐘9412741284813 分析 與原高丹的方法相比，效率提高顯著 計(jì)算耗時(shí)與查詢數(shù)據(jù)耗時(shí)間的平衡：劃分粒度過細(xì)，邊緣數(shù)據(jù)的比例升高， B-tree索引特性決定非連續(xù)數(shù)據(jù)查詢效率較低；劃分粒度過粗，則計(jì)算量較高。 HTM索引與HEALPix索引相比： 相同面積下正三角形的周長大于正方形的邊長14基于基于Boundary Growing Model的改進(jìn)方法的改進(jìn)

7、方法 數(shù)據(jù)庫B-tree索引特性的利用 數(shù)據(jù)加載計(jì)算流程：Boundary Growing Model 減少I/O讀取耗時(shí)，抑制內(nèi)存填充速度解決最主要性能瓶頸：頻繁的解決最主要性能瓶頸：頻繁的I/O操作耗時(shí)操作耗時(shí)15 最大生長塊概念 自頂向下的最大生長塊快速確定方式增強(qiáng)Boundary Growing Model效果自適應(yīng)于天體密度過濾空白區(qū)域16 并行算法設(shè)計(jì)17 實(shí)驗(yàn)結(jié)果及分析 實(shí)驗(yàn)一：稀疏數(shù)據(jù)集上的實(shí)驗(yàn) SDSS DR6星表（約1億條數(shù)據(jù)）、2MASS星表（約4.7億條數(shù)據(jù)） 原始方法與改進(jìn)方法的對(duì)比：7412841294127412841294121041218 實(shí)驗(yàn)二：非稀疏數(shù)據(jù)集

8、上的實(shí)驗(yàn)數(shù)據(jù)集：SDSS：47949212條記錄、2MASS：35476377條記錄 原始方法與改進(jìn)方法的對(duì)比：7412841294127412841294121041219面向面向HTM索引的可行性分析索引的可行性分析 優(yōu)化邊界問題的解決方法 限制生長模型20基于基于MapReduce分布式模型的交叉證認(rèn)分布式模型的交叉證認(rèn) 意義： 數(shù)據(jù)急速增長，長期考慮，多核單機(jī)環(huán)境并不現(xiàn)實(shí) 突破關(guān)系數(shù)據(jù)庫在處理海量數(shù)據(jù)時(shí)的瓶頸 利用大規(guī)模集群獲得更強(qiáng)大的計(jì)算能力，進(jìn)一步提高效率，為實(shí)現(xiàn)在線實(shí)時(shí)交叉證認(rèn)和聯(lián)合查詢打下基礎(chǔ)21MapReduce模型模型 概念： MapReduce是Google在2004年提

9、出的一個(gè)編程模型，并已于2010年年初正式申請(qǐng)獲批該項(xiàng)技術(shù)的專利。它主要用以進(jìn)行大規(guī)模數(shù)據(jù)集上的并行運(yùn)算，其主要概念“Map（映射）”和“Reduce（規(guī)約）”最初借鑒于函數(shù)式編程語言。 優(yōu)點(diǎn)： 適合處理海量數(shù)據(jù)，尤其適合于數(shù)據(jù)間存在較強(qiáng)獨(dú)立性的應(yīng)用； 成本低廉，使原本必須借助于非常高昂的超級(jí)計(jì)算機(jī)才能獲得的計(jì)算能力可以在大量廉價(jià)機(jī)器上同樣實(shí)現(xiàn)； 易于編程，將任務(wù)分發(fā)、任務(wù)調(diào)度、數(shù)據(jù)分布、容錯(cuò)處理、負(fù)載平衡等并行計(jì)算中不可避免的復(fù)雜控制細(xì)節(jié)隱藏于系統(tǒng)的運(yùn)行時(shí)后臺(tái)處理中22Step1:數(shù)據(jù)分布式存放（數(shù)據(jù)分布式存放（Map+Reduce）輸入星表數(shù)據(jù)MapMapMapMapMapMapReduc

10、eReduceShuffle/SortChop/replicate（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）（塊號(hào)+來源，屬性）Reduce數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組23Step2:

11、證認(rèn)計(jì)算（證認(rèn)計(jì)算（Map）數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組MapMapMapMapMapResultResultResultResultResult證認(rèn)結(jié)果24實(shí)驗(yàn)實(shí)驗(yàn) 實(shí)驗(yàn)結(jié)果： 證認(rèn)部分耗時(shí)：25秒 達(dá)到接近線性的加速比 意義： 確認(rèn)了文件數(shù)據(jù)庫在處理海量數(shù)據(jù)方面的優(yōu)勢(shì) 大幅度縮短大星表交叉證認(rèn)計(jì)算用時(shí)，為最終實(shí)現(xiàn)實(shí)時(shí)聯(lián)合查詢服務(wù)提供了條件 充分利用了廉價(jià)的計(jì)算資源，對(duì)于快速增長的天文數(shù)據(jù)量具有良好的可擴(kuò)展性，為今后天

12、文數(shù)據(jù)處理提供了一種可行的方案。25面向面向HEALPix和和HTM索引的快速鄰域編碼計(jì)算算法索引的快速鄰域編碼計(jì)算算法 研究意義 各種交叉證認(rèn)方法得以高效實(shí)現(xiàn)的必要前提26 在各種天文數(shù)據(jù)查詢、數(shù)據(jù)處理上有著廣泛的應(yīng)用空間，如“錐形檢索服務(wù)”r（ ， ）27HEALPix索引下的鄰接塊編碼計(jì)算算法索引下的鄰接塊編碼計(jì)算算法異或運(yùn)算之第二操作數(shù)求解規(guī)則：如果最終目標(biāo)是求東北方向的共邊鄰接塊，即圖中標(biāo)志為“2”的鄰接塊，則其異或運(yùn)算符右側(cè)的第二操作數(shù)的確定方式為：對(duì)原塊編碼從低位向高位尋找第一次出現(xiàn)的“00”或“10”，從該位開始直到最后一位間的每兩位均變成“01”，而更高位上均為“0”；如果最

13、終目標(biāo)是求西南方向的共邊鄰接塊，即圖中標(biāo)志為“6”的鄰接塊，則其異或運(yùn)算符右側(cè)的第二操作數(shù)的確定方式為：對(duì)原塊編碼從低位向高位尋找第一次出現(xiàn)的“00”或“01”，從該位開始直到最后一位間的每兩位均變成“01”，而更高位上均為“0”；如果最終目標(biāo)是求東南方向的共邊鄰接塊，即圖中標(biāo)志為“4”的鄰接塊，則其異或運(yùn)算符右側(cè)的第二操作數(shù)的確定方式為：對(duì)原塊編碼從低位向高位尋找第一次出現(xiàn)的“11”或“10”，從該位開始直到最后一位間的每兩位均變成“10”，而更高位上均為“0”；如果最終目標(biāo)是求西北方向的共邊鄰接塊，即圖中標(biāo)志為“8”的鄰接塊，則其異或運(yùn)算符右側(cè)的第二操作數(shù)的確定方式為：對(duì)原塊編碼從低位向高

14、位尋找第一次出現(xiàn)的“00”或“01”，從該位開始直到最后一位間的每兩位均變成“10”，而更高位上均為“0”； 28 塊“2”編碼： 塊“4”編碼： 塊“6”編碼： 塊“8”編碼： 塊“1”編碼： 塊“3”編碼： 塊“5”編碼： 塊“7”編碼： 1101101000010101110011111100110100000010110011111100111000000001110011111110010100101010110011111101101000010101110011111111000000101010110110101101101000010101110011111101100000

15、0000101101101011001101000000101100111111001100000000011001101111001110000000011100111111100100001010101100111029HTM索引下的鄰接塊編碼計(jì)算算法索引下的鄰接塊編碼計(jì)算算法異或運(yùn)算之第二操作數(shù)求解規(guī)則：如果最終目標(biāo)是求1號(hào)角對(duì)邊方向的鄰接三角形編碼，即標(biāo)記為“1”的鄰接塊，則其異或運(yùn)算符右側(cè)的第二操作數(shù)的確定方式為：對(duì)原塊編碼從低位向高位尋找第一次出現(xiàn)的“01”或“11”位，如果找到的是“01”，則從該位開始直到最后一位間的每兩位均為“11”，如果找到的是“11”，則從該位開始直到最后

16、一位間的每兩位均為“10”，而更高位上均為“0”；如果最終目標(biāo)是求0號(hào)角對(duì)邊方向的鄰接三角形編碼，即標(biāo)記為“0”的鄰接塊，則其異或運(yùn)算符右側(cè)的第二操作數(shù)的確定方式為：對(duì)原塊編碼從低位向高位尋找第一次出現(xiàn)的“00”或“11”位，無論找到的是“00”還是“11”，都從該位開始直到最后一位間的每兩位均設(shè)定為“11”，而更高位上均為“0”；如果最終目標(biāo)是求2號(hào)角對(duì)邊方向的鄰接三角形編碼，即標(biāo)記為“2”的鄰接塊，則其異或運(yùn)算符右側(cè)的第二操作數(shù)的確定方式為：對(duì)原塊編碼從低位向高位尋找第一次出現(xiàn)的“10”或“11”位，無論找到的是“10”還是“11”，都從該位開始直到最后一位間的每兩位均設(shè)定為“01”，而更

17、高位上均為“0”； 30 塊“0”編碼： 塊“1”編碼： 塊“2”編碼： 00111011000000110011100000111101000001010011100000010010001010100011100031 實(shí)驗(yàn)結(jié)果： 計(jì)算 個(gè)HEALPix計(jì)算塊中的每個(gè)計(jì)算塊周圍一圈的 個(gè)鄰接HEALPix原子塊的全部HEALPix編碼（包含 次“同等劃分級(jí)別下的鄰接塊編碼計(jì)算”和 次“塊內(nèi)邊界小塊編碼計(jì)算”） 總耗時(shí)：0.82秒 計(jì)算全天區(qū) 個(gè)HTM計(jì)算塊中的每個(gè)計(jì)算塊周圍一圈的 個(gè)鄰接HTM原子塊的全部HTM編碼（包含 次“同等劃分級(jí)別下的鄰接塊編碼計(jì)算”和 次“塊內(nèi)邊界小塊編碼計(jì)算”） 總耗時(shí)：1.23秒 結(jié)論： 為高效交叉證認(rèn)方法的實(shí)現(xiàn)奠定了基礎(chǔ)，同時(shí)也在多種面向海量數(shù)據(jù)的天文數(shù)據(jù)處理中有著重要的應(yīng)用價(jià)值。84884834888412528