面向海量數(shù)據(jù)的

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

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

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

4、tree索引，物理上相近的塊 其塊號在數(shù)值上也連續(xù)或相近，自然地實現(xiàn)了臨近區(qū)域的聚類，適合于一切SQL系統(tǒng)。一次索引，可進行多級精度上的計算，便于選取最合適索引塊和計算塊的級數(shù)。不同密度、速度的星體可選擇不同距離閾值。 等面積與簡單網(wǎng)格天區(qū)劃分方式相比，省去了對赤經(jīng)的修正(spherical-polar distortion problem )，避免了復(fù)雜的球面坐標(biāo)任務(wù)分配方式簡單，容易實現(xiàn)負(fù)載平衡 通用性 邊界漏源問題的解決快速相鄰塊編碼計算算法簡單網(wǎng)格天區(qū)劃分方式 并行方法設(shè)計 實驗結(jié)果及分析Aladin 可視化結(jié)果：8412方法星表A來源星表A數(shù)據(jù)量星表B來源星表B數(shù)據(jù)量運行總耗時Par

5、allel HEALPix-index 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,811

6、2MASS470,992,97073小時簡單網(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分鐘94127412848 分析 與原高丹的方法相比，效率提高顯著 計算耗時與查詢數(shù)據(jù)耗時間的平衡：劃分粒度過細(xì)，邊緣數(shù)據(jù)的比例升高， B-tree索引特性決定非連續(xù)數(shù)據(jù)查詢效率較低；劃分粒度過粗，則計算量較高。 HTM索引與HEALPix索引相比： 相同面積下正三角形的周長大于正方形的邊長Versionnumber of bl

7、ocks bordering one compute-blockHealPix4*2n+41HTM3*2(n+1)+61.5基于基于Boundary Growing Model的改進方法的改進方法 數(shù)據(jù)庫B-tree索引特性的利用 數(shù)據(jù)加載計算流程：Boundary Growing Model 減少I/O讀取耗時，抑制內(nèi)存填充速度解決最主要性能瓶頸：頻繁的解決最主要性能瓶頸：頻繁的I/O操作耗時操作耗時 最大生長塊概念 自頂向下的最大生長塊快速確定方式增強Boundary Growing Model效果自適應(yīng)于天體密度過濾空白區(qū)域 并行算法設(shè)計 實驗結(jié)果及分析 實驗一：稀疏數(shù)據(jù)集上的實驗 SD

8、SS DR6星表（約1億條數(shù)據(jù)）、2MASS星表（約4.7億條數(shù)據(jù)） 原始方法與改進方法的對比：741284129412計算塊分塊數(shù)量SDSS數(shù)據(jù)庫查詢2MASS數(shù)據(jù)庫查詢 （中心塊）2MASS數(shù)據(jù)庫查詢(邊界塊)距離計算其他總用時307s59s335s580s40s1321s317s40s639s151s44s1191s427s54s1177s51s72s1781s74128412941210412計算塊分塊數(shù)量SDSS數(shù)據(jù)庫查詢2MASS數(shù)據(jù)庫查詢距離計算其他總用時120s78s2489s48s2735s127s79s690s58s954s191s102s199s57s549s374s23

9、9s58s67s738s 實驗二：非稀疏數(shù)據(jù)集上的實驗數(shù)據(jù)集：SDSS：47949212條記錄、2MASS：35476377條記錄 原始方法與改進方法的對比：741284129412計算塊分塊數(shù)SDSS數(shù)據(jù)庫查詢2MASS數(shù)據(jù)庫查詢 （中心塊）2MASS數(shù)據(jù)庫查詢(邊界塊)距離計算其他總用時33s17s124s96s16s286s33s19s191s24s16s283s43s28s403s11s22s507s74128412941210412計算塊分塊數(shù)SDSS數(shù)據(jù)庫查詢2MASS數(shù)據(jù)庫查詢距離計算其他總用時32s19s421s27s499s36s20s130s27s213s46s27s39s

10、31s143s107s60s11s32s210s面向面向HTM索引的可行性分析索引的可行性分析 優(yōu)化邊界問題的解決方法 限制生長模型基于基于MapReduce分布式模型的交叉證認(rèn)分布式模型的交叉證認(rèn) 意義： 數(shù)據(jù)急速增長，長期考慮，多核單機環(huán)境并不現(xiàn)實 突破關(guān)系數(shù)據(jù)庫在處理海量數(shù)據(jù)時的瓶頸 利用大規(guī)模集群獲得更強大的計算能力，進一步提高效率，為實現(xiàn)在線實時交叉證認(rèn)和聯(lián)合查詢打下基礎(chǔ)MapReduce模型模型 概念： MapReduce是Google在2004年提出的一個編程模型，并已于2010年年初正式申請獲批該項技術(shù)的專利。它主要用以進行大規(guī)模數(shù)據(jù)集上的并行運算，其主要概念“Map（映射）”

11、和“Reduce（規(guī)約）”最初借鑒于函數(shù)式編程語言。 優(yōu)點： 適合處理海量數(shù)據(jù)，尤其適合于數(shù)據(jù)間存在較強獨立性的應(yīng)用； 成本低廉，使原本必須借助于非常高昂的超級計算機才能獲得的計算能力可以在大量廉價機器上同樣實現(xiàn)； 易于編程，將任務(wù)分發(fā)、任務(wù)調(diào)度、數(shù)據(jù)分布、容錯處理、負(fù)載平衡等并行計算中不可避免的復(fù)雜控制細(xì)節(jié)隱藏于系統(tǒng)的運行時后臺處理中Step1:數(shù)據(jù)分布式存放（數(shù)據(jù)分布式存放（Map+Reduce）輸入星表數(shù)據(jù)MapMapMapMapMapMapReduceReduceShuffle/SortChop/replicate（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源

12、，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）（塊號+來源，屬性）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記錄組Step2: 證認(rèn)計算（證認(rèn)計算（Map）數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星

13、表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組數(shù)據(jù)塊頭部星表A記錄組星表B記錄組MapMapMapMapMapResultResultResultResultResult證認(rèn)結(jié)果實驗實驗 實驗結(jié)果： 證認(rèn)部分耗時：25秒 達(dá)到接近線性的加速比 意義： 確認(rèn)了文件數(shù)據(jù)庫在處理海量數(shù)據(jù)方面的優(yōu)勢 大幅度縮短大星表交叉證認(rèn)計算用時，為最終實現(xiàn)實時聯(lián)合查詢服務(wù)提供了條件 充分利用了廉價的計算資源，對于快速增長的天文數(shù)據(jù)量具有良好的可擴展性，為今后天文數(shù)據(jù)處理提供了一種可行的方案。面向面向HEALPix和和HTM索引的快速鄰域編碼計算算法索引的快速鄰域編碼計算算法 研究意義 各種交叉證認(rèn)方法得

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

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

16、塊“8”編碼： 塊“1”編碼： 塊“3”編碼： 塊“5”編碼： 塊“7”編碼： 11011010000101011100111111001101000000101100111111001110000000011100111111100101001010101100111111011010000101011100111111110000001010101101101011011010000101011100111111011000000000101101101011001101000000101100111111001100000000011001101111001110000000011100

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

18、原塊編碼從低位向高位尋找第一次出現(xiàn)的“00”或“11”位，無論找到的是“00”還是“11”，都從該位開始直到最后一位間的每兩位均設(shè)定為“11”，而更高位上均為“0”；如果最終目標(biāo)是求2號角對邊方向的鄰接三角形編碼，即標(biāo)記為“2”的鄰接塊，則其異或運算符右側(cè)的第二操作數(shù)的確定方式為：對原塊編碼從低位向高位尋找第一次出現(xiàn)的“10”或“11”位，無論找到的是“10”還是“11”，都從該位開始直到最后一位間的每兩位均設(shè)定為“01”，而更高位上均為“0”； 塊“0”編碼： 塊“1”編碼： 塊“2”編碼： 001110110000001100111000001111010000010100111000000100100010101000111000 實驗結(jié)果： 計算 個HEALPix計算塊中的每個計算塊周圍一圈的 個鄰接HEALPix原子塊的全部HEALPix編碼（包含 次“同等劃分級別下的鄰接塊編碼計算”和 次“塊內(nèi)邊界小塊編碼計算”） 總耗時：0.82秒 計算全天區(qū) 個HTM計算塊中的每個計算塊周圍一圈的 個鄰接HTM原子塊的全部HTM編碼（包含 次“同等劃分級別下的鄰接塊編碼計算”和 次“塊內(nèi)邊界小塊編碼計算”） 總耗時：1.23秒 結(jié)論： 為高效交叉證認(rèn)方法的實現(xiàn)奠定了基礎(chǔ)，同時也在多種面向海量數(shù)據(jù)的天文數(shù)據(jù)