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

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