面向海量數(shù)據(jù)的高效天文交叉證認的研究.ppt

面向海量數(shù)據(jù)的 高效天文交叉證認的研究,答辯人：趙青 指導老師：孫濟洲 教授 天津大學計算機學院 Email: ,天津大學博士研究生畢業(yè)答辯,主要內(nèi)容,研究背景及意義 面向多核環(huán)境的并行交叉證認方法 面向分布式集群環(huán)境的交叉證認方法 面向HEALPix和HTM索引的快速鄰域編碼計算算法 總結(jié)與展望,研究背景及意義,天文多波段交叉證認的概念 基于位置信息的交叉證認 主要面臨挑戰(zhàn)： 天文觀測設(shè)備的日新月異所帶來的天文數(shù)據(jù)的海量性：TB乃至PB量級，且呈類摩爾定律增長,LAMOST望遠鏡，全稱：大天區(qū)面積多目標光纖光譜天文望遠鏡 2008年10月建成，每夜能觀測上萬個天體的光譜，世界上威力最大，最重要的天文望遠鏡之一,國家“十一五” 開始提出并已開始建設(shè)的世界最大的單口徑射電望遠鏡 500米口徑球面射電天文望遠鏡（FAST）。,美國LSST望遠鏡，8.4米口徑大尺度概要巡天望遠鏡，每晚將產(chǎn)生數(shù)據(jù)量高達18TB，相當于28000張普通光盤的容量。,關(guān)鍵是解決交叉證認的高效性需求與海量的天文觀測數(shù)據(jù)量之間的矛盾，因此交叉證認是典型的數(shù)據(jù)密集型、I/O密集型計算難題！ 研究意義 虛擬天文臺項目數(shù)據(jù)訪問服務(wù)的核心模塊 LAMOST望遠鏡大科學工程三大子課題之一 中國科學院天文科學主題庫索引層建設(shè)的必要技術(shù) 統(tǒng)計分析、數(shù)據(jù)挖掘的基礎(chǔ),多核環(huán)境下的并行交叉證認的研究,研究意義： 當今處理器芯片已經(jīng)步入多核時代，多核計算資源的普及所帶來的強大的計算能力為天文學中很多大規(guī)模計算難題的解決提供了新的途徑 畫框：降低計算復(fù)雜度 基于偽二維球面索引的劃分方法,HEALPix,HTM,使用偽二維球面索引的好處 嵌套的層次編號方式: 臨近塊的ID編碼只區(qū)別在低位，且如果Q1區(qū)域包含Q2區(qū)域，則Q2的編碼以Q1的編碼為前綴。 適合B-tree索引，物理上相近的塊 其塊號在數(shù)值上也連續(xù)或相近，自然地實現(xiàn)了臨近區(qū)域的聚類，適合于一切SQL系統(tǒng)。 一次索引，可進行多級精度上的計算，便于選取最合適索引塊和計算塊的級數(shù)。不同密度、速度的星體可選擇不同距離閾值。 等面積 與簡單網(wǎng)格天區(qū)劃分方式相比，省去了對赤經(jīng)的修正(spherical-polar distortion problem )，避免了復(fù)雜的球面坐標 任務(wù)分配方式簡單，容易實現(xiàn)負載平衡 通用性,邊界漏源問題的解決,快速相鄰塊編碼計算算法,簡單網(wǎng)格天區(qū)劃分方式,并行方法設(shè)計,實驗結(jié)果及分析 Aladin 可視化結(jié)果：,分析 與原高丹的方法相比，效率提高顯著 計算耗時與查詢數(shù)據(jù)耗時間的平衡：劃分粒度過細，邊緣數(shù)據(jù)的比例升高， B-tree索引特性決定非連續(xù)數(shù)據(jù)查詢效率較低；劃分粒度過粗，則計算量較高。 HTM索引與HEALPix索引相比： 相同面積下正三角形的周長大于正方形的邊長,基于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ù)集上的實驗 SDSS DR6星表（約1億條數(shù)據(jù)）、2MASS星表（約4.7億條數(shù)據(jù)） 原始方法與改進方法的對比：,實驗二：非稀疏數(shù)據(jù)集上的實驗 數(shù)據(jù)集：SDSS：47949212條記錄、2MASS：35476377條記錄 原始方法與改進方法的對比：,面向HTM索引的可行性分析,優(yōu)化邊界問題的解決方法 限制生長模型,基于MapReduce分布式模型的交叉證認,意義： 數(shù)據(jù)急速增長，長期考慮，多核單機環(huán)境并不現(xiàn)實 突破關(guān)系數(shù)據(jù)庫在處理海量數(shù)據(jù)時的瓶頸 利用大規(guī)模集群獲得更強大的計算能力，進一步提高效率，為實現(xiàn)在線實時交叉證認和聯(lián)合查詢打下基礎(chǔ),MapReduce模型,概念： MapReduce是Google在2004年提出的一個編程模型，并已于2010年年初正式申請獲批該項技術(shù)的專利。它主要用以進行大規(guī)模數(shù)據(jù)集上的并行運算，其主要概念“Map（映射）”和“Reduce（規(guī)約）”最初借鑒于函數(shù)式編程語言。 優(yōu)點： 適合處理海量數(shù)據(jù)，尤其適合于數(shù)據(jù)間存在較強獨立性的應(yīng)用； 成本低廉，使原本必須借助于非常高昂的超級計算機才能獲得的計算能力可以在大量廉價機器上同樣實現(xiàn)； 易于編程，將任務(wù)分發(fā)、任務(wù)調(diào)度、數(shù)據(jù)分布、容錯處理、負載平衡等并行計算中不可避免的復(fù)雜控制細節(jié)隱藏于系統(tǒng)的運行時后臺處理中,Step1:數(shù)據(jù)分布式存放（Map+Reduce）,輸入星表數(shù)據(jù),Map,Map,Map,Map,Map,Map,Reduce,Reduce,Shuffle/Sort,Chop/replicate,（塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性） （塊號+來源，屬性）,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: 證認計算（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記錄組,Map,Map,Map,Map,Map,Result,Result,Result,Result,Result,證認結(jié)果,實驗,實驗結(jié)果： 證認部分耗時：25秒 達到接近線性的加速比 意義： 確認了文件數(shù)據(jù)庫在處理海量數(shù)據(jù)方面的優(yōu)勢 大幅度縮短大星表交叉證認計算用時，為最終實現(xiàn)實時聯(lián)合查詢服務(wù)提供了條件 充分利用了廉價的計算資源，對于快速增長的天文數(shù)據(jù)量具有良好的可擴展性，為今后天文數(shù)據(jù)處理提供了一種可行的方案。,面向HEALPix和HTM索引的快速鄰域編碼計算算法,研究意義 各種交叉證認方法得以高效實現(xiàn)的必要前提,在各種天文數(shù)據(jù)查詢、數(shù)據(jù)處理上有著廣泛的應(yīng)用空間，如“錐形檢索服務(wù)”,HEALPix索引下的鄰接塊編碼計算算法,異或運算之第二操作數(shù)求解規(guī)則： 如果最終目標是求東北方向的共邊鄰接塊，即圖中標志為“2”的鄰接塊，則其異或運算符右側(cè)的第二操作數(shù)的確定方式為：對原塊編碼從低位向高位尋找第一次出現(xiàn)的“00”或“10”，從該位開始直到最后一位間的每兩位均變成“01”，而更高位上均為“0”； 如果最終目標是求西南方向的共邊鄰接塊，即圖中標志為“6”的鄰接塊，則其異或運算符右側(cè)的第二操作數(shù)的確定方式為：對原塊編碼從低位向高位尋找第一次出現(xiàn)的“00”或“01”，從該位開始直到最后一位間的每兩位均變成“01”，而更高位上均為“0”； 如果最終目標是求東南方向的共邊鄰接塊，即圖中標志為“4”的鄰接塊，則其異或運算符右側(cè)的第二操作數(shù)的確定方式為：對原塊編碼從低位向高位尋找第一次出現(xiàn)的“11”或“10”，從該位開始直到最后一位間的每兩位均變成“10”，而更高位上均為“0”； 如果最終目標是求西北方向的共邊鄰接塊，即圖中標志為“8”的鄰接塊，則其異或運算符右側(cè)的第二操作數(shù)的確定方式為：對原塊編碼從低位向高位尋找第一次出現(xiàn)的“00”或“01”，從該位開始直到最后一位間的每兩位均變成“10”，而更高位上均為“0”；,塊“2”編碼： 塊“4”編碼： 塊“6”編碼： 塊“8”編碼： 塊“1”編碼： 塊“3”編碼： 塊“5”編碼： 塊“7”編碼：,HTM索引下的鄰接塊編碼計算算法,異或運算之第二操作數(shù)求解規(guī)則： 如果最終目標是求1號角對邊方向的鄰接三角形編碼，即標記為“1”的鄰接塊，則其異或運算符右側(cè)的第二操作數(shù)的確定方式為：對原塊編碼從低位向高位尋找第一次出現(xiàn)的“01”或“11”位，如果找到的是“01”，則從該位開始直到最后一位間的每兩位均為“11”，如果找到的是“11”，則從該位開始直到最后一位間的每兩位均為“10”，而更高位上均為“0”； 如果最終目標是求0號角對邊方向的鄰接三角形編碼，即標記為“0”的鄰接塊，則其異或運算符右側(cè)的第二操作數(shù)的確定方式為：對原塊編碼從低位向高位尋找第一次出現(xiàn)的“00”或“11”位，無論找到的是“00”還是“11”，都從該位開始直到最后一位間的每兩位均設(shè)定為“11”，而更高位上均為“0”； 如果最終目標是求2號角對邊方向的鄰接三角形編碼，即標記為“2”的鄰接塊，則其異或運算符右側(cè)的第二操作數(shù)的確定方式為：對原塊編碼從低位向高位尋找第一次出現(xiàn)的“10”或“11”位，無論找到的是“10”還是“11”，都從該位開始直到最后一位間的每兩位均設(shè)定為“01”，而更高位上均為“0”；,塊“0”編碼： 塊“1”編碼： 塊“2”編碼：,實驗結(jié)果： 計算 個HEALPix計算塊中的每個計算塊周圍一圈的 個鄰接HEALPix原子塊的全部HEALPix編碼（包含 次“同等劃分級別下的鄰接塊編碼計算”和 次“塊內(nèi)邊界小塊編碼計算”） 總耗時：0.82秒 計算全天區(qū) 個HTM計算塊中的每個計算塊周圍一圈的 個鄰接HTM原子塊的全部HTM編碼（包含 次“同等劃分級別下的鄰接塊編碼計算”和 次“塊內(nèi)邊界小塊編碼計算”） 總耗時：1.23秒 結(jié)論： 為高效交叉證認方法的實現(xiàn)奠定了基礎(chǔ)，同時也在多種面向海量數(shù)據(jù)的天文數(shù)據(jù)處理中有著重要的應(yīng)用價值。,未來展望,研究基于數(shù)據(jù)挖掘、概率統(tǒng)計等更復(fù)雜交叉證認方法在海量數(shù)據(jù)上的效率