大數(shù)據(jù)熱點(diǎn)研究問題和典型研究介紹黃宜華2013420課件

大數(shù)據(jù)熱點(diǎn)研究問題

和典型研究介紹黃宜華南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室2013.4.20,南京大數(shù)據(jù)熱點(diǎn)研究問題

和典型研究介紹1多核、并行計(jì)算與大數(shù)據(jù)并行計(jì)算多核/眾核單核處理器設(shè)計(jì)達(dá)到極限，2005年Intel多核處理器戰(zhàn)略轉(zhuǎn)移體系結(jié)構(gòu)與處理器技術(shù)行業(yè)需求行業(yè)大數(shù)據(jù)應(yīng)用需求2009-2010年開始，行業(yè)應(yīng)用規(guī)模和數(shù)據(jù)量急劇增長(zhǎng)影響現(xiàn)有計(jì)算技術(shù)各個(gè)層面:體系結(jié)構(gòu)分布并行計(jì)算算法設(shè)計(jì)數(shù)據(jù)庫(kù)操作系統(tǒng)程序設(shè)計(jì)語(yǔ)言應(yīng)用技術(shù)……MapReduce2004年Google發(fā)明MapReduce海量數(shù)據(jù)并行處理技術(shù)，07年Hadoop推廣并行處理技術(shù)方法大數(shù)據(jù)多核、并行計(jì)算與大數(shù)據(jù)并行計(jì)算多核/眾核單核處理器設(shè)計(jì)達(dá)到極2Wiki百科：bigdataisacollectionofdatasetssolargeandcomplexthatitbecomesdifficulttoprocessusingon-handdatabasemanagementtools

大數(shù)據(jù)意指一個(gè)超大的、難以用現(xiàn)有常規(guī)的數(shù)據(jù)庫(kù)管理技術(shù)和工具處理的數(shù)據(jù)集IDC報(bào)告：Bigdatatechnologiesdescribeanewgenerationoftechnologiesandarchitectures,designedtoeconomicallyextractvaluefromverylargevolumesofawidevarietyofdata,byenablinghigh-velocitycapture,discovery,and/oranalysis.

大數(shù)據(jù)技術(shù)描述了一種新一代技術(shù)和構(gòu)架，用于以很經(jīng)濟(jì)的方式、以高速的捕獲、發(fā)現(xiàn)和分析技術(shù)，從各種超大規(guī)模的數(shù)據(jù)中提取價(jià)值什么是大數(shù)據(jù)？Wiki百科：bigdataisacollectio3大數(shù)據(jù)處理技術(shù)的重要性大數(shù)據(jù)(BigData)應(yīng)用需求

出現(xiàn)越來(lái)越多的大數(shù)據(jù)應(yīng)用和行業(yè)需求。2008年，在Google成立10周年之際，《Nature》雜志出版一期?？瘜ｉT討論未來(lái)的大數(shù)據(jù)（BigData）處理相關(guān)的一系列技術(shù)問題和挑戰(zhàn)。大數(shù)據(jù)處理技術(shù)的重要性大數(shù)據(jù)(BigData)應(yīng)用需求4未來(lái)10多年數(shù)據(jù)將急劇增長(zhǎng)IDC研究報(bào)告《DataUniverseStudy》提出“數(shù)據(jù)宇宙”的說(shuō)法描述海量數(shù)據(jù)2007年2008年2009年2010年2011年大數(shù)據(jù)處理技術(shù)的重要性未來(lái)10多年數(shù)據(jù)將急劇增長(zhǎng)2007年2008年2009年205大數(shù)據(jù)處理技術(shù)的重要性未來(lái)急劇增長(zhǎng)的數(shù)據(jù)迫切需要尋求新的處理技術(shù)手段IDC報(bào)告《DataUniverseStudy》全世界權(quán)威IT咨詢公司研究報(bào)告預(yù)測(cè):全世界數(shù)據(jù)量未來(lái)10年將從2009年的0.8ZB增長(zhǎng)到2020年的35ZB,增長(zhǎng)44倍!年均增長(zhǎng)率>40%!大數(shù)據(jù)處理技術(shù)的重要性未來(lái)急劇增長(zhǎng)的數(shù)據(jù)迫切需要尋求新的處理6美國(guó)聯(lián)邦政府發(fā)布大數(shù)據(jù)研發(fā)專項(xiàng)研究計(jì)劃美國(guó)聯(lián)邦政府下屬的國(guó)防部、能源部、衛(wèi)生總署等7部委聯(lián)合推動(dòng)，于2012年3月底發(fā)布了大數(shù)據(jù)研發(fā)專項(xiàng)研究計(jì)劃(BigDataInitiative)，擬投入2億美元用于研究開發(fā)科學(xué)探索、環(huán)境和生物醫(yī)學(xué)、教育和國(guó)家安全等重大領(lǐng)域和行業(yè)所急需的大數(shù)據(jù)處理技術(shù)和工具，把大數(shù)據(jù)研究上升到為國(guó)家發(fā)展戰(zhàn)略。大數(shù)據(jù)處理技術(shù)的重要性7美國(guó)聯(lián)邦政府發(fā)布大數(shù)據(jù)研發(fā)專項(xiàng)研究計(jì)劃美國(guó)聯(lián)邦政府下屬的國(guó)防“大數(shù)據(jù)研究的科學(xué)價(jià)值”李國(guó)杰，《中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊》，vol.8，no.9,2012.92012年3月，美國(guó)奧巴馬政府宣布投資2億美元啟動(dòng)“大數(shù)據(jù)研究和發(fā)展計(jì)劃”，這是繼1993年美國(guó)宣布“信息高速公路”計(jì)劃后的又一次重大科技發(fā)展部署。美國(guó)政府認(rèn)為大數(shù)據(jù)是“未來(lái)的新石油”，將“大數(shù)據(jù)研究”上升為國(guó)家意志，對(duì)未來(lái)的科技與經(jīng)濟(jì)發(fā)展必將帶來(lái)深遠(yuǎn)影響。一個(gè)國(guó)家擁有數(shù)據(jù)的規(guī)模和運(yùn)用數(shù)據(jù)的能力將成為綜合國(guó)力的重要組成部分，對(duì)數(shù)據(jù)的占有和控制也將成為國(guó)家間和企業(yè)間新的爭(zhēng)奪焦點(diǎn)。大數(shù)據(jù)處理技術(shù)的重要性8“大數(shù)據(jù)研究的科學(xué)價(jià)值”大數(shù)據(jù)處理技術(shù)的重要性8數(shù)據(jù)科學(xué)(DataScience)

國(guó)內(nèi)外出現(xiàn)了“數(shù)據(jù)科學(xué)”的概念圖靈獎(jiǎng)獲得者JimGray:2007年最后一次演講中提出“數(shù)據(jù)密集型科學(xué)發(fā)現(xiàn)(Data-IntensiveScientificDiscovery)”將成為科學(xué)研究的第四范式

實(shí)驗(yàn)科學(xué)理論科學(xué)計(jì)算科學(xué)數(shù)據(jù)科學(xué)世界著名存儲(chǔ)技術(shù)公司EMC：提出了“DataScience”的概念，“DataScienceteamswillbecomethedrivingforceforsuccesswithbigdataanalytics”李國(guó)杰院士：“數(shù)據(jù)科學(xué)”研究的對(duì)象是什么？計(jì)算機(jī)科學(xué)是關(guān)于算法的科學(xué)，數(shù)據(jù)科學(xué)是關(guān)于數(shù)據(jù)的科學(xué)。大數(shù)據(jù)處理技術(shù)的重要性9數(shù)據(jù)科學(xué)(DataScience)大數(shù)據(jù)處理技術(shù)的重要性9大數(shù)據(jù)將帶來(lái)巨大的技術(shù)和商業(yè)機(jī)遇

大數(shù)據(jù)分析挖掘和利用將為企業(yè)帶來(lái)巨大的商業(yè)價(jià)值原始信息行業(yè)數(shù)據(jù)知識(shí)報(bào)表制圖電子文檔信息檢索數(shù)據(jù)倉(cāng)庫(kù)海量分析知識(shí)挖掘信息化技術(shù)大數(shù)據(jù)分析PC時(shí)代互聯(lián)網(wǎng)時(shí)代大數(shù)據(jù)時(shí)代大數(shù)據(jù)處理技術(shù)的重要性大數(shù)據(jù)將帶來(lái)巨大的技術(shù)和商業(yè)機(jī)遇大數(shù)據(jù)分析挖掘和利用將為企業(yè)10應(yīng)用數(shù)據(jù)規(guī)模急劇增加，傳統(tǒng)計(jì)算面臨嚴(yán)重挑戰(zhàn)中國(guó)移動(dòng)一個(gè)省電話通聯(lián)記錄(CDR)數(shù)據(jù)每月可達(dá)0.5-1PB，而整個(gè)中國(guó)移動(dòng)每月則高達(dá)7-15PB數(shù)據(jù)；如此巨大的數(shù)據(jù)量使得Oracle等數(shù)據(jù)庫(kù)系統(tǒng)已經(jīng)難以支撐和應(yīng)對(duì)南京市公安局320道路監(jiān)控云計(jì)算系統(tǒng)，數(shù)據(jù)量為三年200億條、總量120TB的車輛監(jiān)控?cái)?shù)據(jù)百度存儲(chǔ)數(shù)百PB數(shù)據(jù)，

每天處理數(shù)據(jù)10PB淘寶存儲(chǔ)14PB交易數(shù)據(jù)，

每天新增數(shù)據(jù)40-50TB大數(shù)據(jù)處理技術(shù)發(fā)展的驅(qū)動(dòng)力11應(yīng)用數(shù)據(jù)規(guī)模急劇增加，傳統(tǒng)計(jì)算面臨嚴(yán)重挑戰(zhàn)大數(shù)據(jù)處理技術(shù)發(fā)展大數(shù)據(jù)處理技術(shù)發(fā)展的驅(qū)動(dòng)力大規(guī)模數(shù)據(jù)處理和行業(yè)應(yīng)用需求日益增加和迫切出現(xiàn)越來(lái)越多的大規(guī)模數(shù)據(jù)處理應(yīng)用需求，傳統(tǒng)系統(tǒng)難以提供足夠的存儲(chǔ)和計(jì)算資源進(jìn)行處理，云計(jì)算技術(shù)是最理想的解決方案。調(diào)查顯示：目前，IT專業(yè)人員對(duì)云計(jì)算中諸多關(guān)鍵技術(shù)最為關(guān)心的是大規(guī)模數(shù)據(jù)并行處理技術(shù)大數(shù)據(jù)并行處理沒有通用和現(xiàn)成的解決方案對(duì)于應(yīng)用行業(yè)來(lái)說(shuō)，云計(jì)算平臺(tái)軟件、虛擬化軟件都不需要自己開發(fā)，但行業(yè)的大規(guī)模數(shù)據(jù)處理應(yīng)用沒有現(xiàn)成和通用的軟件，需要針對(duì)特定的應(yīng)用需求專門開發(fā)，涉及到諸多并行化算法、索引查詢優(yōu)化技術(shù)研究、以及系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)大數(shù)據(jù)處理技術(shù)發(fā)展的驅(qū)動(dòng)力大規(guī)模數(shù)據(jù)處理和行業(yè)應(yīng)用需求日益增12大數(shù)據(jù)處理技術(shù)發(fā)展的驅(qū)動(dòng)力海量數(shù)據(jù)隱含著更準(zhǔn)確的事實(shí)

研究發(fā)現(xiàn)：大數(shù)據(jù)量可顯著提高機(jī)器學(xué)習(xí)算法的準(zhǔn)確性；訓(xùn)練數(shù)據(jù)集越大,數(shù)據(jù)分類精度越高；大數(shù)據(jù)集上的簡(jiǎn)單算法能比小數(shù)據(jù)集上的復(fù)雜算法產(chǎn)生更好的結(jié)果，因此數(shù)據(jù)量足夠大時(shí)有可能使用代價(jià)很小的簡(jiǎn)單算法來(lái)達(dá)到很好的學(xué)習(xí)精度。例如，2001年,一個(gè)基于事實(shí)的簡(jiǎn)短問答研究,如提問:WhoshotAbrahamLincoln？在很大的數(shù)據(jù)集時(shí),只要使用簡(jiǎn)單的模式匹配方法,找到在“shotAbrahamLincoln”前面的部分即可快速得到準(zhǔn)確答案：JohnWilkesBooth大數(shù)據(jù)處理技術(shù)發(fā)展的驅(qū)動(dòng)力海量數(shù)據(jù)隱含著更準(zhǔn)確的事實(shí)13大數(shù)據(jù)的基本特點(diǎn)

大數(shù)據(jù)特點(diǎn):5VVolume:大容量Variety:多樣性Velocity:時(shí)效性Veracity:準(zhǔn)確性Value:大價(jià)值

VeracityVarietyVelocityVolumeValue大數(shù)據(jù)的基本特點(diǎn)大數(shù)據(jù)特點(diǎn):5VVeracityVolu14結(jié)構(gòu)特征結(jié)構(gòu)化數(shù)據(jù)非結(jié)構(gòu)化/半結(jié)構(gòu)化數(shù)據(jù)獲取和處理方式靜態(tài)(線下數(shù)據(jù))/非實(shí)時(shí)數(shù)據(jù)動(dòng)態(tài)(流式/增量式/線上)/實(shí)時(shí)數(shù)據(jù)關(guān)聯(lián)特征無(wú)關(guān)聯(lián)/簡(jiǎn)單關(guān)聯(lián)數(shù)據(jù)(鍵值記錄型數(shù)據(jù))復(fù)雜關(guān)聯(lián)數(shù)據(jù)(圖數(shù)據(jù))大數(shù)據(jù)的類型結(jié)構(gòu)特征大數(shù)據(jù)的類型15數(shù)據(jù)尺度和關(guān)聯(lián)度空間DataconnectednessDatasizeTypicalRDBMSSQLComfortZoneDisk-basedKey-valueStoreColumnStoreDocumentStoreGraphDB引自微軟亞洲研究院，王海勛數(shù)據(jù)尺度和關(guān)聯(lián)度空間DataconnectednessDa16大數(shù)據(jù)問題的基本特點(diǎn)極強(qiáng)的行業(yè)應(yīng)用需求特性規(guī)模極大，超過任何傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)的處理能力技術(shù)綜合性、交叉性很強(qiáng)大多數(shù)傳統(tǒng)算法面臨失效，需要重寫大數(shù)據(jù)研究的基本原則應(yīng)用需求為導(dǎo)向:以行業(yè)應(yīng)用問題和需求為導(dǎo)向領(lǐng)域交叉為橋梁：行業(yè)、IT產(chǎn)業(yè)、學(xué)術(shù)界協(xié)同計(jì)算技術(shù)為支撐：研究解決涉及的計(jì)算技術(shù)問題大數(shù)據(jù)問題的特點(diǎn)和研究原則大數(shù)據(jù)問題的基本特點(diǎn)大數(shù)據(jù)問題的特點(diǎn)和研究原則17以有效的信息技術(shù)手段和計(jì)算方法，獲取、處理和分析各種應(yīng)用行業(yè)的大數(shù)據(jù)，發(fā)現(xiàn)和提取數(shù)據(jù)的內(nèi)在價(jià)值，為行業(yè)提供高附加值的應(yīng)用和服務(wù)技術(shù)手段：信息技術(shù)和計(jì)算方法核心目標(biāo)：價(jià)值發(fā)現(xiàn)效益目標(biāo)：形成高附加值智能化行業(yè)應(yīng)用大數(shù)據(jù)研究的基本目標(biāo)以有效的信息技術(shù)手段和計(jì)算方法，獲取、處理和分析各種應(yīng)用行業(yè)18大數(shù)據(jù)研究的挑戰(zhàn)數(shù)據(jù)規(guī)模導(dǎo)致難以應(yīng)對(duì)的存儲(chǔ)量數(shù)據(jù)規(guī)模導(dǎo)致傳統(tǒng)算法失效大數(shù)據(jù)復(fù)雜的數(shù)據(jù)關(guān)聯(lián)性導(dǎo)致高復(fù)雜度的計(jì)算大數(shù)據(jù)研究的基本途徑三個(gè)基本途徑：尋找新算法降低計(jì)算復(fù)雜度降低大數(shù)據(jù)尺度，尋找數(shù)據(jù)尺度無(wú)關(guān)算法大數(shù)據(jù)并行化處理大數(shù)據(jù)研究的挑戰(zhàn)和基本途徑大數(shù)據(jù)研究的挑戰(zhàn)大數(shù)據(jù)研究的挑戰(zhàn)和基本途徑19大數(shù)據(jù)研究的基本途徑大數(shù)據(jù)研究的挑戰(zhàn)和基本途徑新算法尋找新算法降低計(jì)算復(fù)雜度降低尺度尋找數(shù)據(jù)尺度無(wú)關(guān)近似算法并行化分而治之并行化處理大數(shù)據(jù)大數(shù)據(jù)研究的基本途徑大數(shù)據(jù)研究的挑戰(zhàn)和基本途徑新算法降低尺20大數(shù)據(jù)研究層面從信息處理系統(tǒng)視角以信息系統(tǒng)視角來(lái)劃分大數(shù)據(jù)研究層面

體現(xiàn)大數(shù)據(jù)系統(tǒng)研發(fā)所涉及的各個(gè)層面和問題

同時(shí)兼顧產(chǎn)業(yè)、學(xué)術(shù)和應(yīng)用行業(yè)共同關(guān)注的問題基礎(chǔ)設(shè)施系統(tǒng)平臺(tái)算法應(yīng)用大數(shù)據(jù)研究層面從信息處理系統(tǒng)視角基礎(chǔ)設(shè)施系統(tǒng)平臺(tái)算法應(yīng)用21集群,眾核,GPU,混合式構(gòu)架(如集群+眾核,集群+GPU)云計(jì)算資源與支撐平臺(tái)大數(shù)據(jù)查詢(SQL,NoSQL,實(shí)時(shí)查詢,線下分析)大數(shù)據(jù)存儲(chǔ)(DFS,HBase,RDFDB,MemDB,RDB)大數(shù)據(jù)預(yù)處理MapReduce,BSP,MPI,CUDA,OpenMP,定制式,混合式(如MapReduce+CUDA,MapReduce+MPI)并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法社會(huì)網(wǎng)絡(luò),排名與推薦,商業(yè)智能,自然語(yǔ)言處理,生物信息媒體分析檢索,Web挖掘與檢索,3維建模與可視化計(jì)算…大數(shù)據(jù)研究層面和主要內(nèi)容電信/公安/商業(yè)/金融/遙感遙測(cè)/勘探/生物醫(yī)藥……領(lǐng)域應(yīng)用/服務(wù)需求和計(jì)算模型分析工具/開發(fā)環(huán)境和工具/行業(yè)應(yīng)用系統(tǒng)開發(fā)角色行業(yè)用戶領(lǐng)域?qū)＜覒?yīng)用開發(fā)者計(jì)算技術(shù)研究和開發(fā)者研究層面大數(shù)據(jù)行業(yè)應(yīng)用/服務(wù)層應(yīng)用開發(fā)層應(yīng)用算法層基礎(chǔ)算法層并行編程模型與計(jì)算框架層大數(shù)據(jù)存儲(chǔ)管理層并行構(gòu)架和資源平臺(tái)層應(yīng)用層算法層系統(tǒng)層構(gòu)架層集群,眾核,GPU,混合式構(gòu)架(如集群+眾核,集群22集群,多核,GPU,混合式構(gòu)架(如集群+多核,集群+GPU)云計(jì)算資源和服務(wù)支撐平臺(tái)大數(shù)據(jù)查詢(SQL,NoSQL,實(shí)時(shí)查詢,線下分析)大數(shù)據(jù)存儲(chǔ)(DFS,HBase,MemDB,RDB)大數(shù)據(jù)預(yù)處理MapReduce,BSP,MPI,CUDA,OpenMP,定制式,混合式(如MapReduce+CUDA,MapReduce+MPI)并行化機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法社會(huì)網(wǎng)絡(luò),排名與推薦,商業(yè)智能,自然語(yǔ)言處理,生物信息媒體分析檢索,Web挖掘與搜索,3維建模與可視化…大數(shù)據(jù)研究方式電信/公安/商業(yè)/金融/遙感遙測(cè)/勘探/生物醫(yī)藥……領(lǐng)域應(yīng)用/服務(wù)需求和計(jì)算模型行業(yè)應(yīng)用系統(tǒng)開發(fā)縱向方式：上下層交叉組合單一層面的研究往往難以獲得理想的綜合解決方案，上下層交叉組合可以獲得理想的綜合解決方案，能發(fā)現(xiàn)很多新的研究點(diǎn)集群,多核,GPU,混合式構(gòu)架(如集群+多核,集群23大數(shù)據(jù)十個(gè)典型和熱點(diǎn)研究問題一、大數(shù)據(jù)存儲(chǔ)管理和索引查詢二、Hadoop性能優(yōu)化和功能增強(qiáng)三、并行計(jì)算模型和框架四、并行化機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法五、社會(huì)網(wǎng)絡(luò)分析六、Web信息搜索和排名推薦七、媒體分析檢索八、基于本體的語(yǔ)義分析與挖掘九、大數(shù)據(jù)自然語(yǔ)言處理智能化應(yīng)用十、大數(shù)據(jù)可視化計(jì)算與分析系統(tǒng)層基礎(chǔ)算法典型/共性應(yīng)用算法與技術(shù)大數(shù)據(jù)十個(gè)典型和熱點(diǎn)研究問題一、大數(shù)據(jù)存儲(chǔ)管理和索引查詢系統(tǒng)24一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢大數(shù)據(jù)預(yù)處理技術(shù)大數(shù)據(jù)的采集和傳輸大數(shù)據(jù)的清洗過濾和質(zhì)量管理技術(shù)大數(shù)據(jù)的壓縮技術(shù)記錄型大數(shù)據(jù)索引和查詢技術(shù)靜態(tài)記錄型大數(shù)據(jù)索引技術(shù)流式/增量式記錄型大數(shù)據(jù)索引技術(shù)大數(shù)據(jù)表的高效關(guān)系型操作(如查詢連接)大數(shù)據(jù)并行化查詢技術(shù)SQL/NoSQL查詢語(yǔ)言接口與技術(shù)SQL/NoSQL查詢語(yǔ)言接口并行化查詢執(zhí)行機(jī)制一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢大數(shù)據(jù)預(yù)處理技術(shù)25一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢圖數(shù)據(jù)表示和查詢技術(shù)靜態(tài)圖數(shù)據(jù)的表示和存儲(chǔ)靜態(tài)圖數(shù)據(jù)的查詢流式/增量式圖數(shù)據(jù)的表示和存儲(chǔ)流式/增量式圖數(shù)據(jù)的查詢圖數(shù)據(jù)并行化查詢技術(shù)混合式數(shù)據(jù)表示和存儲(chǔ)管理模型NoSQL數(shù)據(jù)庫(kù)技術(shù)結(jié)構(gòu)化/半結(jié)構(gòu)/非結(jié)構(gòu)化數(shù)據(jù)混合存儲(chǔ)管理模型混合式數(shù)據(jù)下的數(shù)據(jù)關(guān)系和查詢操作技術(shù)一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢圖數(shù)據(jù)表示和查詢技術(shù)26一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢分布式數(shù)據(jù)庫(kù)HBase性能優(yōu)化基于HBase的大數(shù)據(jù)索引和查詢技術(shù)分布式內(nèi)存數(shù)據(jù)庫(kù)存儲(chǔ)技術(shù)

（Google的Dremel，MemSQL，HanaIMDB，Redis…)大規(guī)模RDF語(yǔ)義數(shù)據(jù)庫(kù)基于Hbase的大規(guī)模RDF數(shù)據(jù)存儲(chǔ)管理SPARQL大規(guī)模語(yǔ)義數(shù)據(jù)查詢及并行化算法基于RDFS/OWL的大規(guī)模語(yǔ)義推理并行化算法分布式文件系統(tǒng)HDFS的優(yōu)化一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢分布式數(shù)據(jù)庫(kù)27一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢1.基于HBase的大數(shù)據(jù)索引與查詢技術(shù)問題：HBase缺少類似于RDB中的索引創(chuàng)建能力，通過Hive轉(zhuǎn)換為MapReduce程序處理Hbase中的數(shù)據(jù)性能很慢本課題組正在研究基于HBase和混合樹模型的大數(shù)據(jù)索引和并行化查詢技術(shù)和算法，并利用HBase和CoProcessor、以及分布式內(nèi)存數(shù)據(jù)庫(kù)完成查詢加速。一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢1.基于HBase的大數(shù)據(jù)索引與28一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢2.基于HBase的大規(guī)模RDF語(yǔ)義數(shù)據(jù)庫(kù)問題：大數(shù)據(jù)文本和媒體數(shù)據(jù)語(yǔ)義的分析和挖掘需要提供大規(guī)模RDF語(yǔ)義數(shù)據(jù)存儲(chǔ)管理和查詢系統(tǒng)本課題組正在研究基于HBase和分布式內(nèi)容數(shù)據(jù)庫(kù)的大規(guī)模RDF語(yǔ)義數(shù)據(jù)庫(kù)系統(tǒng)一、大數(shù)據(jù)存儲(chǔ)管理與索引查詢2.基于HBase的大規(guī)模RDF29二、Hadoop性能優(yōu)化與功能增強(qiáng)MapReduceHadoop性能優(yōu)化針對(duì)作業(yè)、任務(wù)和Slot資源的調(diào)度優(yōu)化(Intel-Hadoop,IBM的AMapReduce，F(xiàn)acebook的Corona）針對(duì)I/0的優(yōu)化、針對(duì)充分利用內(nèi)存的優(yōu)化(Berkeley的Spark)針對(duì)流程的優(yōu)化(優(yōu)化Shuffle過程

、SHadoop)MapReduce并行計(jì)算框架改進(jìn)迭代式MapReduce執(zhí)行框架(Twister,HaLoop)流式MapReduce執(zhí)行框架(HadoopOnline)二、Hadoop性能優(yōu)化與功能增強(qiáng)MapReduce301.Hadoop系統(tǒng)性能優(yōu)化問題：Hadoop最初是為批量數(shù)據(jù)線下處理設(shè)計(jì)，當(dāng)使用Hadoop進(jìn)行大數(shù)據(jù)存儲(chǔ)和實(shí)時(shí)查詢分析處理時(shí)，其響應(yīng)性能不夠，因此Hadoop性能優(yōu)化一直是大家關(guān)注的熱點(diǎn)研究問題。本課題組進(jìn)行了HadoopMapReduce框架的性能優(yōu)化研究：1).研究設(shè)計(jì)了新的作業(yè)和任務(wù)處理機(jī)制及任務(wù)調(diào)度通信機(jī)制，實(shí)驗(yàn)結(jié)果顯示，Benchmark程序執(zhí)行性能提升達(dá)到約30%。該項(xiàng)成果經(jīng)過集成和測(cè)試目前已經(jīng)集成到IntelDistributedHadoop（IDH）產(chǎn)品中2).研究了基于資源環(huán)境和作業(yè)開銷感知的Hadoop作業(yè)調(diào)度優(yōu)化技術(shù)，可實(shí)現(xiàn)動(dòng)態(tài)的Slot調(diào)度和均衡的作業(yè)調(diào)度優(yōu)化二、Hadoop性能優(yōu)化與功能增強(qiáng)1.Hadoop系統(tǒng)性能優(yōu)化二、Hadoop性能優(yōu)化與功能增31三、并行編程模型與計(jì)算框架MapReduceHadoop性能優(yōu)化針對(duì)作業(yè)、任務(wù)和Slot資源的調(diào)度優(yōu)化針對(duì)I/0的優(yōu)化、針對(duì)充分利用內(nèi)存的優(yōu)化針對(duì)流程的優(yōu)化MapReduce并行計(jì)算框架改進(jìn)迭代式MapReduce執(zhí)行框架(Twister,HaLoop)流式MapReduce執(zhí)行框架(HadoopOnline)BSP

(BulkSynchronizedParallel)基于BSP模型的并行處理框架三、并行編程模型與計(jì)算框架MapReduce32三、并行編程模型與計(jì)算框架大規(guī)模圖數(shù)據(jù)并行處理框架和系統(tǒng)Google的Pregel微軟的Trinity定制式并行計(jì)算框架全內(nèi)存集群計(jì)算(BakerleySpark)大規(guī)模流式數(shù)據(jù)處理(TwitterStorm,YahooS4)特定應(yīng)用問題的定制式并行計(jì)算框架混合式并行計(jì)算模型和框架MapReduce+CUDA并行計(jì)算框架的設(shè)計(jì)與優(yōu)化MapReduce+MPI和MapReduce+BSP并行計(jì)算框架設(shè)計(jì)優(yōu)化三、并行編程模型與計(jì)算框架大規(guī)模圖數(shù)據(jù)并行處理框架和系統(tǒng)33三、并行編程模型與計(jì)算框架基于IntelXeonPhi眾核協(xié)處理系統(tǒng)MIC的BSP編程模型和示范應(yīng)用研究Intel最新推出商用眾核協(xié)處理器IntelXeonPhi57／61核，以高速

環(huán)形結(jié)構(gòu)互聯(lián)商用級(jí)眾核處理器通用計(jì)算能力價(jià)格：$2000-2650三、并行編程模型與計(jì)算框架基于IntelXeonPhi眾34三、并行編程模型與計(jì)算框架基于IntelXeonPhi眾核協(xié)處理系統(tǒng)MIC的BSP編程模型研究和示范應(yīng)用研究包括三個(gè)層面的工作：基于MIC的BSP并行計(jì)算模型研究機(jī)器學(xué)習(xí)并行化算法研究?jī)蓚€(gè)并行化示范應(yīng)用大規(guī)模圖像檢索+機(jī)器翻譯系統(tǒng)HostProcessorIntelXeonE5-26XXPCIeXeonPhiMIC0XeonPhiMIC1MPIOpenMPBSPParallelizedMachineLearningandNLPAlgorithmsImageRetrieval/DetectionMachineTranslationDemoApplicationsParallelML&NLPAlgorithmsParallelProgrammingModelsMIC-BasedParallelComputingHardwarePlatform三、并行編程模型與計(jì)算框架基于IntelXeonPhi眾35三、并行編程模型與計(jì)算框架2.混合式并行計(jì)算模型和框架研究MapReduce+MIC(或GPU)的混合式并行計(jì)算模型和框架研究問題：在視頻或圖像內(nèi)容分析應(yīng)用中，面向大規(guī)模媒體數(shù)據(jù)分析處理時(shí)，單一的MapReduce構(gòu)架和模型不足以勝任，需要采用MapReduce調(diào)度媒體片段或文件的處理、同時(shí)采用MIC或GPU對(duì)本地的數(shù)據(jù)密集型媒體處理進(jìn)行并行化加速處理

需要在MapReduce模型和框架基礎(chǔ)上開發(fā)對(duì)局部數(shù)據(jù)用MIC或GPU加速處理的編程接口和框架基于Hadoop+內(nèi)存數(shù)據(jù)庫(kù)的混合式并行計(jì)算模型和框架研究對(duì)某些對(duì)響應(yīng)性能要求很高的應(yīng)用，需要考慮基于內(nèi)存數(shù)據(jù)庫(kù)進(jìn)行加速

如：我們進(jìn)行了基于內(nèi)存數(shù)據(jù)庫(kù)的在線機(jī)器翻譯并行化算法研究和系統(tǒng)開發(fā)

三、并行編程模型與計(jì)算框架2.混合式并行計(jì)算模型和框架研究36三、并行編程模型與計(jì)算框架3.定制式并行計(jì)算模型和框架

問題：對(duì)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中的很多算法，現(xiàn)有的MapReduce或其他并行計(jì)算框架可能既過于龐大、適用性也不好，需要研發(fā)輕量級(jí)的、更加適用、效率更高的定制式并行計(jì)算框架例如：我們基于Hadoop的基礎(chǔ)構(gòu)架和底層的RPC協(xié)議自行研發(fā)了面向神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的輕量級(jí)定制式并行計(jì)算框架，提供基于分布內(nèi)存的快速迭代計(jì)算機(jī)制和并行計(jì)算能力三、并行編程模型與計(jì)算框架3.定制式并行計(jì)算模型和框架問題37四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法大數(shù)據(jù)并行化機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法大數(shù)據(jù)處理并行化學(xué)習(xí)和挖掘算法不同并行模型下并行化學(xué)習(xí)和挖掘算法并行化機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘工具和平臺(tái)研究表明：基于大數(shù)據(jù)集的機(jī)器學(xué)習(xí)會(huì)取得更好的學(xué)習(xí)效果，這已經(jīng)成為目前機(jī)器學(xué)習(xí)領(lǐng)域的共識(shí)四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法大數(shù)據(jù)并行化機(jī)器學(xué)習(xí)和數(shù)據(jù)挖38分類算法(Classification)大規(guī)模支持向量機(jī)(LargeScaleSVM)神經(jīng)網(wǎng)絡(luò)(NeuralNetwork)樸素貝葉斯(Na?veBayes)決策樹(DecisionTrees)聚類(Clustering)關(guān)聯(lián)規(guī)則挖掘參數(shù)估計(jì)(ParametersEstimation)高維度數(shù)據(jù)降維(DimensionReduction)集成學(xué)習(xí)(EnsembleLearning)圖數(shù)據(jù)算法圖聚類，圖分類，圖模式匹配(子圖同構(gòu)、最大公共子圖)四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法分類算法(Classification)四、并行化機(jī)器學(xué)習(xí)391.基于MapReduce的K-Means并行化算法輸入：待聚類的N個(gè)數(shù)據(jù)點(diǎn)，期望生成的聚類的個(gè)數(shù)K輸出：K個(gè)聚類算法描述:選出K個(gè)點(diǎn)作為初始的clustercenter

Loop:

對(duì)輸入中的每一個(gè)點(diǎn)p：

｛

計(jì)算p到各個(gè)cluster的距離；

將p歸入最近的cluster;

｝

重新計(jì)算各個(gè)cluster的中心

如果不滿足停止條件，gotoLoop;否則，停止四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法1.基于MapReduce的K-Means并行化算法四、并401.基于MapReduce的K-Means并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法Map階段的處理在Map類的初始化方法setup中讀取全局的聚類中心信息對(duì)Map方法收到的每一個(gè)數(shù)據(jù)點(diǎn)p，計(jì)算p與所有聚類中心間的距離，并選擇一個(gè)距離最小的中心作為p所屬的聚類，輸出<ClusterID,p>鍵值對(duì)對(duì)每個(gè)Map節(jié)點(diǎn)上即將傳遞到Reduce節(jié)點(diǎn)的每一個(gè)<ClusterID,p>鍵值對(duì)，用Combiner進(jìn)行數(shù)據(jù)優(yōu)化，合并相同ClusterID下的所有數(shù)據(jù)點(diǎn)并求取這些點(diǎn)的均值pm以及數(shù)據(jù)點(diǎn)個(gè)數(shù)n1.基于MapReduce的K-Means并行化算法四、并411.基于MapReduce的K-Means并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法Mapper偽代碼classMapper

setup(…){讀出全局的聚類中心數(shù)據(jù)

Centers}

map(key,p)//p為一個(gè)數(shù)據(jù)點(diǎn){minDis=Double.MAXVALUE;index=-1;fori=0toCenters.length{dis=ComputeDist(p,Centers[i]);ifdis<minDis{minDis=dis;index=i;}}emit(Centers[i].ClusterID,p);}1.基于MapReduce的K-Means并行化算法四、并421.基于MapReduce的K-Means并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法Combiner偽代碼classCombiner

reduce(ClusterID,[p1,p2,…]){pm=0.0；n=數(shù)據(jù)點(diǎn)列表[p1,p2,…]中數(shù)據(jù)點(diǎn)的總個(gè)數(shù);fori=0tonpm+=p[i];pm=pm/n;//求得這些數(shù)據(jù)點(diǎn)的平均值emit(ClusterID,(pm,n));}1.基于MapReduce的K-Means并行化算法四、并432.K-最近鄰(KNN)分類并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法基本算法設(shè)計(jì)思想K-最近鄰是分類器算法中最通俗易懂的一種，計(jì)算測(cè)試樣本到各訓(xùn)練樣本的距離，取其中距離最小的K個(gè)，并根據(jù)這K個(gè)訓(xùn)練樣本的標(biāo)記進(jìn)行投票得到測(cè)試樣本的標(biāo)記。加權(quán)K-最近鄰分類算法的思路是，在根據(jù)測(cè)試樣本的標(biāo)記進(jìn)行投票表決時(shí)，將根據(jù)測(cè)試樣本與每個(gè)訓(xùn)練樣本間距離（或相似度）的大小決定訓(xùn)練樣本標(biāo)記的作用大小，基本原則是：距離越近的訓(xùn)練樣本其標(biāo)記的作用權(quán)重越大，反之則越小。據(jù)此，可以建立一個(gè)帶加權(quán)的投票表決計(jì)算模型(比如y’=∑Si*yi/∑Si,k=[0,k-1],Si為取值0-1的相似度數(shù)值，yi為選取出的最鄰近訓(xùn)練樣本的分類標(biāo)記值)決定以最終的測(cè)試樣本的分類標(biāo)記。算法的思路清晰簡(jiǎn)單，然而對(duì)于海量數(shù)據(jù)計(jì)算量很大，耗費(fèi)時(shí)間較長(zhǎng)。2.K-最近鄰(KNN)分類并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)442.K-最近鄰(KNN)分類并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法MapReduce并行化算法設(shè)計(jì)思路基本處理思路是：將測(cè)試樣本數(shù)據(jù)分塊后分布在不同的節(jié)點(diǎn)上進(jìn)行處理，將訓(xùn)練樣本數(shù)據(jù)文件放在DistributedCache中供每個(gè)節(jié)點(diǎn)共享訪問Map階段對(duì)每個(gè)讀出的測(cè)試樣本數(shù)據(jù)ts(trid,A’,y’）計(jì)算其與每個(gè)訓(xùn)練樣本數(shù)據(jù)tr(trid,A,y)之間的相似度S=Sim(A’,A）（1：相似度最大，0：相似度最?。z查S是否比目前的k個(gè)S值中最小的大，若是則將(S,y)計(jì)入k個(gè)最大者根據(jù)所保留的k個(gè)S值最大的(S,y)，根據(jù)模型y’=∑Si*yi/∑Si計(jì)算出ts的分類標(biāo)記值y’，發(fā)射出(tsid,y’)Reduce階段直接輸出(tsid,y’)2.K-最近鄰(KNN)分類并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)452.K-最近鄰(KNN)分類并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法Mapper偽代碼classMapper

setup(…)

{讀取全局訓(xùn)練樣本數(shù)據(jù)文件，轉(zhuǎn)入本地內(nèi)存的數(shù)據(jù)表TR中

}

map(key,ts)//ts為一個(gè)測(cè)試樣本{Φ

MaxS(k)tstsid,A,yfori=0toTR.lenghth){TR[i]tr,A’S=Sim(A,A’);

若S屬于k個(gè)最大者，(S,y)MaxS;}

根據(jù)MaxS和帶加權(quán)投票表決模型計(jì)算出y’

emit(tsid,y’)}2.K-最近鄰(KNN)分類并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)46四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法3.頻繁項(xiàng)集挖掘并行化算法本研究組進(jìn)行了基于MapReduce的頻繁項(xiàng)集挖掘算法研究基本思路是基于傳統(tǒng)的Apriori算法和SON算法，提出并實(shí)現(xiàn)了一個(gè)并行化的頻繁項(xiàng)集挖掘算法PSON，用兩輪MapReduce實(shí)現(xiàn)了大規(guī)模頻繁項(xiàng)集挖掘并行計(jì)算研究論文，發(fā)表于PAAP2011國(guó)際會(huì)議PSON:AParallelizedSONAlgorithmwithMapReduceforMiningFrequentSets

TaoXiao,ShuaiWang,ChunfengYuan,YihuaHuangTheFourthInternationalSymposiumonParallelArchitectures,AlgorithmsandProgramming(PAAP2011)，Tianjin，Dec.9-11,2011四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法3.頻繁項(xiàng)集挖掘并行化算法47FrequentsetsSupposeIisanitemsetconsistingofitemsfromthetransactiondatabaseDLetNbethenumberoftransactionsDLetMbethenumberoftransactionsthatcontainalltheitemsof

IM/NisreferredtoasthesupportofIinD

ExampleHere,N=4,letI={I1,I2},thanM=2becauseI={I1,I2}iscontainedintransactionsT100andT400sothesupportofIis0.5(2/4=0.5)Ifsup(I)isnolessthatanuser-definedthreshold,thenIisreferredtoasafrequentitemsetGoaloffrequentsetsminingTofindallfrequentk-itemsetsfromatransactiondatabase(k=1,2,3,)枚舉計(jì)算的時(shí)間復(fù)雜度是：O(2n*N*t),n是Item的總數(shù)，N是Transaction總數(shù)，t是每個(gè)Transaction平均包含的Item數(shù)FrequentsetsSupposeIisani48SONAlgorithm*BasicideaDividethewholedatabaseintoseveralnon-overlappingpartitionsForeachpartition,discoverallthefrequentitemsetsforit(referredtoaslocalfrequentitemsets)Mergeallthelocalfrequentitemsetsfromallthepartitions(referredtoasglobalcandidateitemsets)Removethosethatarenotactuallyfrequentinthewholedatabase,generating

globalfrequentitemsetsLemmaAnitemsetthatisnotlocalfrequentinanyofthepartitionscannotbeglobalfrequentAglobalfrequentitemsetmustappearaslocalfrequentinatleastoneofthepartitions*A.Savasere,E.Omiecinski,andS.Navathe,“Anefficientalgorithmforminingassociationrulesinlargedatabases,”inproceedingsofthe21stVLDBConferenceZurich,Swizerland,1995SONAlgorithm*Basicidea49PSON:ParallelizedSONAlgorithmMotivationtoParallelizeSONProcessingonepartitiondoesn’tneedanyinformationfromanyotherpartitionEachpartitioncanbeprocessedconcurrentlySONisnaturallysuitableforparallelizationPreparingdataStorethetransactiondatabaseintoDFSThewholedatabasewillbeautomaticallydividedintoseveralnon-overlappingchunksChunkscorrespondtothepartitionsinSONMaptasksEachchunkisprocessedbyonemappernodetofindlocalfrequentitemsetsforthatchunkReducetasksLocalfrequentitemsetsofthesamelengthareprocessedbyonereducenodeEachnodecountsforeachglobalcandidateitemsetitreceivesThusdecideswhichareglobalfrequentitemsetsRuntwoMapReducejobstogenerateallfrequentitemsets1stjob:generateallglobalcandidateitemsets2ndjob:identifyglobalfrequentitemsetsfromglobalcandidateitemsetsPSON:ParallelizedSONAlgorit50The1stMapReduceJobMapphaseEachmapnodetakesinonepartitionandgenerateslocalfrequentitemsetsforthatpartitionusingApriorialgorithm.ForeachlocalfrequentitemsetF,emitskey-valuepair<F,1>.Here,thevalue1isonlytoindicatethatFisalocalfrequentitemsetforthatpartition.ShuffleandSortphaseThesamelocalfrequentitemsetsaresenttoonereducenode.ReducephaseEachreducenodeemitsoneandonlyonekey-valuepair<F,1>toDFSFinallyMergingallthepairsinDFSgivesusallglobalcandidateitemsetsThe1stMapReduceJobMapphase51The2ndMapReduceJobAssumptionEachnodeisgivenafullduplicateoftheglobalcandidateitemsetsgeneratedbythe1stMapReducejobbeforehandMapphaseEachmapnodecountsforeachoftheglobalcandidateitemsetsinthepartitionthemapnodeisassignedThenemitspairslike<C,v>whereCisaglobalcandidateitemsetand

visthecountofitinthatpartitionShuffleandSortphaseEachglobalcandidateitemsetanditscountsinallthepartitionsaresenttoonereducenodeReducephaseForeachglobalcandidateitemsetC,reducenodeaddsupalltheassociativecountsforCandemitsonlytheactualglobalfrequentitemsetstoDFSThe2ndMapReduceJobAssumptio52ExperimentalResults

Thetransactiondatabasesizevariesfrom6GBto60GB，withthenumberoftransactionsvariesfrom1millionto500billionConclusion:WhenthesizeofthedatabasereachesathresholdofhundredsofGB,PSONcanfinishrunninginanacceptableperiodoftime，achievingagoodperformanceinscale-upPSONcanachieveagoodperformanceinspeed-upExperimentalResults Thetrans53四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法4.大規(guī)模短文本多分類并行化算法本研究組進(jìn)行了基于MapReduce的查詢短文本分類并行化算法研究。提供了1萬(wàn)條已經(jīng)標(biāo)注出所屬類別作為訓(xùn)練樣本，一共有480個(gè)類別。原始數(shù)據(jù)有1000萬(wàn)條查詢短文本，其中有少數(shù)不屬于這480類的異類測(cè)試樣本，需要對(duì)這些大量的短文本進(jìn)行分類，并能標(biāo)識(shí)出不屬于以上480類的異類樣本。本研究項(xiàng)目為本系研究生組隊(duì)參加2012年中國(guó)第一屆“云計(jì)算與移動(dòng)互聯(lián)網(wǎng)大獎(jiǎng)賽”的指定的4個(gè)大數(shù)據(jù)并行處理賽題之一，經(jīng)過角逐獲得1、2、3等獎(jiǎng)各一項(xiàng)。四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法4.大規(guī)模短文本多分類并行化54四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法4.大規(guī)模短文本多分類并行化算法本道題目是高維稀疏空間文本的分類問題。由于大量實(shí)踐證實(shí)SVM針對(duì)高維空間數(shù)據(jù)訓(xùn)練效果較好，而且分類器的速度較快，因此我們使用了linearSVM進(jìn)行處理訓(xùn)練階段，對(duì)于多類（480類）問題，為了提高分類精度，我們針對(duì)每個(gè)類做了一個(gè)兩類分類器；同時(shí)為了能識(shí)別出異類樣本，我們用每個(gè)類別下的標(biāo)注樣本訓(xùn)練出一個(gè)OneClassSVM分類器預(yù)測(cè)階段，分別用480個(gè)分類器對(duì)每個(gè)待預(yù)測(cè)的樣本進(jìn)行分類并打分，選擇打分最高的類別作為該樣本可能的預(yù)測(cè)類別；并用OneClassSVM對(duì)該測(cè)試樣本做一個(gè)異類樣本排除為了提升訓(xùn)練和分類速度，上述所有算法都在MapReduce框架下實(shí)現(xiàn)。四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法4.大規(guī)模短文本多分類并行化55四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法4.大規(guī)模短文本多分類并行化算法四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法4.大規(guī)模短文本多分類并行化56四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法4.大規(guī)模短文本多分類并行化算法OneClassSVM排除異類四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法4.大規(guī)模短文本多分類并行化57四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法本研究組基于Hadoop基礎(chǔ)構(gòu)架和底層RPC遠(yuǎn)程過程調(diào)用通信，采用分布內(nèi)存式數(shù)據(jù)緩存機(jī)制，為經(jīng)典的BackPropagation神經(jīng)網(wǎng)絡(luò)算法研究設(shè)計(jì)了一個(gè)定制的輕量級(jí)專用并行化計(jì)算框架，并最終設(shè)計(jì)實(shí)現(xiàn)了并行化的BackPropagation神經(jīng)網(wǎng)絡(luò)算法。神經(jīng)網(wǎng)絡(luò)需要經(jīng)過數(shù)萬(wàn)至數(shù)十萬(wàn)輪的迭代計(jì)算，計(jì)算量巨大。由于實(shí)現(xiàn)了并行化算法，大大縮短了訓(xùn)練時(shí)間，本課題進(jìn)行了800萬(wàn)超大訓(xùn)練樣本的神經(jīng)網(wǎng)絡(luò)訓(xùn)練并行化計(jì)算測(cè)試。四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法58四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法

四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法59四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法

MapReduce顯然不適合做這樣大量的迭代運(yùn)算，因此需要設(shè)計(jì)定制式的輕量級(jí)并行計(jì)算框架。基本思路是把全部樣本劃分為子集給各個(gè)節(jié)點(diǎn)分別進(jìn)行處理四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法Map60四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法

基本算法思路是把整個(gè)樣本數(shù)據(jù)劃分到各個(gè)計(jì)算節(jié)點(diǎn)上完成計(jì)算，然后計(jì)算誤差和權(quán)重差值⊿W，匯總并更新權(quán)重W后繼續(xù)迭代計(jì)算，直至達(dá)到結(jié)束條件四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法基本算61四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法

四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法62四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法

Comparisonofeachepoch'strainingtimecostincNeuralandHadoopwithdifferentnumberofcomputingnodeson1milliontrainingsamples.Performanceofeachepoch'strainingtimecostincNeuralwithvariousnumbersofcomputingnodesandvarioussizesoftrainingsamples四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法5.神經(jīng)網(wǎng)絡(luò)并行化算法Com63四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法6.查詢推薦QUBIC并行化算法本研究組進(jìn)行了基于MapReduce的查詢推薦QUBIC并行化算法?；舅悸肥腔谟脩羧罩驹O(shè)計(jì)查詢推薦算法，首先挖掘用戶日志中Query與URL之間的關(guān)系，尋找Query中若干關(guān)聯(lián)性較大的組，最后基于MapReduce并行構(gòu)造Query-URL二部圖和查詢親和圖QAG，在此基礎(chǔ)上最終完成查詢?cè)~的聚類，并以此為基礎(chǔ)推薦查詢關(guān)鍵詞肖滔，碩士研究論文，2012四、并行化機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法6.查詢推薦QUBIC并行化64五、社會(huì)網(wǎng)絡(luò)分析社團(tuán)發(fā)現(xiàn)(CommunityDetection)網(wǎng)絡(luò)建模(NetworkModeling)中心分析和影響力建模(CentralityAnalysisandInfluenceModeling)分類推薦(ClassificationandRecommendation)隱私安全等(Privacy,SpamandSecurity)五、社會(huì)網(wǎng)絡(luò)分析社團(tuán)發(fā)現(xiàn)(CommunityDetec65六、Web信息搜索與排名推薦文檔倒排索引（InvertedDocumentIndexing）深度Web搜索(DeepWebSearch，精確化、智能化、綜合化信息搜索)頁(yè)面分類(DocumentClassification)頁(yè)面聚類(DocumentCluster)網(wǎng)頁(yè)摘要(DocumentAutomaticSummarization)重復(fù)文檔檢測(cè)與過濾(DuplicateDocumentDetection&Filtering)

Web信息搜索與數(shù)據(jù)挖掘六、Web信息搜索與排名推薦文檔倒排索引（Inverted66六、Web信息搜索與排名推薦常規(guī)排名(Ranking)多樣性排名(DiversifiedRanking)基于內(nèi)容的推薦(Content-basedRecommendation)基于標(biāo)簽的推薦(Tag-basedRecommendation)協(xié)同過濾推薦(CollaborativeFilteringRecommendation)

排名與推薦系統(tǒng)六、Web信息搜索與排名推薦常規(guī)排名(Ranking)排名671.文檔倒排索引算法

搜索引擎中最重要的一個(gè)問題是如何為大量文檔創(chuàng)建倒排索引以便提供全文檢索基于以上索引的搜索結(jié)果：fish

doc1,doc2red

doc2,doc3redfishdoc2doc1：onefishtwofishdoc2：redfishbluefishdoc3：oneredbird倒排索引：one:doc1,doc3fish:doc1,doc2two:doc1red:doc2,doc3blue:doc2bird:doc3六、Web信息搜索與排名推薦1.文檔倒排索引算法基于以上索引的搜索結(jié)果：doc1：doc681.文檔倒排索引算法如果考慮單詞在每個(gè)文檔中出現(xiàn)的詞頻、位置、對(duì)應(yīng)Web文檔的URL等諸多屬性，則前述簡(jiǎn)單的倒排算法就不足以有效工作。我們把每個(gè)單詞對(duì)應(yīng)的文檔ID、單詞詞頻、位置等諸多信息稱為postings六、Web信息搜索與排名推薦1.文檔倒排索引算法如果考慮單詞在每個(gè)文檔中出現(xiàn)的詞頻、位置691.文檔倒排索引算法六、Web信息搜索與排名推薦1.文檔倒排索引算法六、Web信息搜索與排名推薦701.文檔倒排索引算法Map和Reduce實(shí)現(xiàn)偽代碼1:classMapper2:procedureMap(docidn,docd)3:H←newAssociativeArray4:foralltermt∈docddo5:H{t}←H{t}+16:foralltermt∈H

do7:Emit(termt,posting<n,H{t}>)1:classReducer2:procedureReduce(termt,postings[<n1,f1>,<n2,f2>…])3:P←newList4:forallposting<a,f>∈postings[<n1,f1>,<n2,f2>…]do5:Append(P,<a,f>)7:Emit(termt;postingsP)六、Web信息搜索與排名推薦1.文檔倒排索引算法六、Web信息搜索與排名推薦71六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRankPageRank是一種由搜索引擎根據(jù)網(wǎng)頁(yè)之間相互的超鏈接計(jì)算的網(wǎng)頁(yè)排名技術(shù)PageRank是Google用于用來(lái)標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí)或重要性的一種方法；其級(jí)別從1到10級(jí)，PR值越高說(shuō)明該網(wǎng)頁(yè)越受歡迎（越重要）PageRank基本思想從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈接過來(lái)的網(wǎng)頁(yè)，必定還是優(yōu)質(zhì)網(wǎng)頁(yè)。一個(gè)網(wǎng)頁(yè)要想擁有較高的PR值的條件：有很多網(wǎng)頁(yè)鏈接到它有高質(zhì)量的網(wǎng)頁(yè)鏈接到它六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRan722.網(wǎng)頁(yè)排名圖算法PageRank假定一個(gè)上網(wǎng)者從一個(gè)隨機(jī)的網(wǎng)頁(yè)開始瀏覽上網(wǎng)者不斷點(diǎn)擊當(dāng)前網(wǎng)頁(yè)的鏈接開始下一次瀏覽但是，上網(wǎng)者最終厭倦了，開始了一個(gè)隨機(jī)網(wǎng)頁(yè)的瀏覽隨機(jī)上網(wǎng)者訪問一個(gè)新網(wǎng)頁(yè)的概率就等于這個(gè)網(wǎng)頁(yè)的PageRank值。這個(gè)模型更加接近于用戶的行為六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRank假定一個(gè)上網(wǎng)者從一個(gè)隨機(jī)的732.網(wǎng)頁(yè)排名圖算法PageRank采用鄰接表來(lái)表示網(wǎng)頁(yè)之間的連接關(guān)系。隨機(jī)瀏覽模型的PageRank公式：以上公式是遞歸定義的，因此需要通過迭代計(jì)算得到所有節(jié)點(diǎn)最終的PageRank值六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRank采用鄰接表來(lái)表示網(wǎng)頁(yè)之間的742.網(wǎng)頁(yè)排名圖算法PageRankPhase1:GraphBuilder建立網(wǎng)頁(yè)之間的超鏈接圖Phase2:PageRankIter迭代計(jì)算各個(gè)網(wǎng)頁(yè)的PageRank值Phase3:RankViewer按PageRank值從大到小輸出六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRankPhase1:Graph75Phase1：GraphBuilder原始數(shù)據(jù)集：維基百科各網(wǎng)頁(yè)間的鏈接信息。文本文件，共11.2G。每行包含一個(gè)網(wǎng)頁(yè)名，及其所鏈接的全部網(wǎng)頁(yè)名GraphBuilder目標(biāo)：分析原始數(shù)據(jù)，建立各個(gè)網(wǎng)頁(yè)之間的鏈接關(guān)系。Map：逐行分析原始數(shù)據(jù),輸出<URL,(PR_init,link_list)>其中網(wǎng)頁(yè)的URL作為key,PageRank初始值（PR_init）和網(wǎng)頁(yè)的出度列表一起作為value,以字符串表示value，用特定的符號(hào)將二者分開。Reduce:輸出<URL,(PR_init,link_list)>該階段的Reduce不需要做任何處理六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRankPhase1：GraphBuilder原始數(shù)據(jù)集：維基百科各76Phase2：PageRankIterPageRankIer：迭代計(jì)算PR值，直到PR值收斂或迭代預(yù)定次數(shù)。Map對(duì)上階段的<URL,(cur_rank,link_list)>產(chǎn)生兩種<key,value>對(duì)：

Foreachuinlink_list,輸出<u,cur_rank/|link_list|>其中u代表當(dāng)前URL所鏈接到網(wǎng)頁(yè)ID，并作為key；Cur_rank為當(dāng)前URL的PageRank值，|link_list|為當(dāng)前URL的出度數(shù)量，,cur_rank/|link_list|作為value。

同時(shí)在迭代過程中，傳遞每個(gè)網(wǎng)頁(yè)的鏈接信息<URL,link_list>在迭代過程中，必須保留網(wǎng)頁(yè)的局部鏈出信息，以維護(hù)圖的結(jié)構(gòu)。六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRankPhase2：PageRankIterPageRankIer77Phase2：PageRankIterReduce對(duì)Map輸出的<URL,url_list>和多個(gè)

<URL,val>做如下處理：其中<URL,url_list>為當(dāng)前URL的鏈出信息；

<URL,val>為當(dāng)前URL的鏈入網(wǎng)頁(yè)對(duì)其貢獻(xiàn)的PageRank值計(jì)算所有val的和，并乘上d，在加上常數(shù)(1-d)/N得到new_rank。輸出(URL,(new_rank,url_list))。迭代計(jì)算公式：PR(A)=(1-d)/N+d(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRankPhase2：PageRankIterReduce對(duì)Ma78Phase2：PageRankIter

PageRankIter偽代碼六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRankPhase2：PageRankIterPageRankIt79Phase3：RankviewerPageRankViewer：將最終結(jié)果排序輸出。PageRankViewer從最后一次迭代的結(jié)果讀出文件，并將文件名和其PR值讀出，并以PR值為key網(wǎng)頁(yè)名為value，并且以PR值從大到小的順序輸出。排序過程中可以采用框架自身的排序處理，重載key的比較函數(shù)，使其經(jīng)過shuffle和sort后反序（從大到?。┹敵鰌ublicstaticclassDecFloatWritableextendsFloatWritable{…@OverridepublicintcompareTo(Objecto){return-pareTo(o);}}六、Web信息搜索與排名推薦2.網(wǎng)頁(yè)排名圖算法PageRankPhase3：RankviewerPageRankViewe80六、Web信息搜索與排名推薦3.大規(guī)模重復(fù)文檔檢測(cè)算法本研究組進(jìn)行了大規(guī)模重復(fù)文檔檢測(cè)算法研究問題：搜索引擎的結(jié)果中包含大量重復(fù)文檔鏈接本研究項(xiàng)目為本課題組研究生組隊(duì)參加2012年中國(guó)第一屆“云計(jì)算與移動(dòng)互聯(lián)網(wǎng)大獎(jiǎng)賽”的創(chuàng)意類賽題，經(jīng)過角逐獲得2等獎(jiǎng)一項(xiàng)六、Web信息搜索與排名推薦3.大規(guī)模重復(fù)文檔檢測(cè)算法本研究81項(xiàng)目基本內(nèi)容

項(xiàng)目背景與基本問題2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯互聯(lián)網(wǎng)中存在著大量的近似重復(fù)的網(wǎng)頁(yè)。據(jù)統(tǒng)計(jì)，中文網(wǎng)頁(yè)的重復(fù)率達(dá)29%，給用戶和搜索引擎處理帶來(lái)了很多問題：

大大增加了網(wǎng)頁(yè)爬取、索引建立、空間存儲(chǔ)的開銷和負(fù)擔(dān)。大幅影響搜索引擎用戶的使用體驗(yàn)、降低了用戶的滿意度。項(xiàng)目基本內(nèi)容

項(xiàng)目背景與基本問題2012.10.29中國(guó)云﹒82項(xiàng)目基本內(nèi)容

項(xiàng)目背景與基本問題2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯示例1：具有重復(fù)關(guān)系的網(wǎng)頁(yè)項(xiàng)目基本內(nèi)容

項(xiàng)目背景與基本問題2012.10.29中國(guó)云﹒83項(xiàng)目基本內(nèi)容

項(xiàng)目背景與基本問題2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯示例2：具有包含關(guān)系的網(wǎng)頁(yè)項(xiàng)目基本內(nèi)容

項(xiàng)目背景與基本問題2012.10.29中國(guó)云﹒84項(xiàng)目基本內(nèi)容

研究現(xiàn)狀2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯算法特征提取相似度度量方法特點(diǎn)精確性和召回率Shingling（1992）不考慮JaccardSimilarity面向降維，第一個(gè)檢測(cè)重復(fù)網(wǎng)頁(yè)算法精確性和召回率均較低RandomProjection（2002）不考慮CosineSimilarity面向降維精確性和召回率均較低IMatch（2002）IDFCompletelyMatching第一個(gè)考慮過濾噪音內(nèi)容的算法高精確性，低召回率率SpotSigs（2008）SpotSignaturesJaccardSimilarity通過停詞區(qū)分正文內(nèi)容和模板內(nèi)容精確性和召回率較前幾個(gè)有提高，但仍較低CoDet（2011）不考慮CSmeasurement面向包含關(guān)系精確性和召回率均較低目前所提出的算法總體來(lái)說(shuō)在精確性和召回率上不高，尤其在處理中文網(wǎng)頁(yè)的問題上。且面向具有包含關(guān)系網(wǎng)頁(yè)檢測(cè)的研究較少。項(xiàng)目基本內(nèi)容

研究現(xiàn)狀2012.10.29中國(guó)云﹒移動(dòng)85項(xiàng)目基本內(nèi)容

項(xiàng)目主要研究?jī)?nèi)容2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯項(xiàng)目名稱

具有重復(fù)網(wǎng)頁(yè)檢測(cè)和聚類功能的中文新聞搜索引擎。研究?jī)?nèi)容和目的研究大規(guī)模檢測(cè)重復(fù)網(wǎng)頁(yè)（新聞網(wǎng)頁(yè)）的精確與快速算法—CCDet。設(shè)計(jì)并實(shí)現(xiàn)一個(gè)基于重復(fù)網(wǎng)頁(yè)（新聞網(wǎng)頁(yè)）檢測(cè)的原型搜索引擎—Bingo。項(xiàng)目基本內(nèi)容

項(xiàng)目主要研究?jī)?nèi)容2012.10.29中國(guó)云﹒移86項(xiàng)目基本內(nèi)容

項(xiàng)目的主要技術(shù)問題2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯采用何種特征才能有效計(jì)算網(wǎng)頁(yè)相似性？如何度量網(wǎng)頁(yè)之間的重復(fù)關(guān)系？如何過濾網(wǎng)頁(yè)的模板并提取文檔正文？如何高效地檢測(cè)所有重復(fù)網(wǎng)頁(yè)對(duì)？如何將檢測(cè)出的重復(fù)網(wǎng)頁(yè)進(jìn)行有效的歸并，使得搜索引擎可以以簡(jiǎn)潔的文檔結(jié)果展現(xiàn)給用戶？如何針對(duì)大規(guī)模文檔數(shù)據(jù)完成以上重復(fù)文檔檢測(cè)處理？如何實(shí)現(xiàn)一個(gè)帶有重復(fù)文檔檢測(cè)功能的原型搜索引擎？項(xiàng)目基本內(nèi)容

項(xiàng)目的主要技術(shù)問題2012.10.29中國(guó)云﹒87項(xiàng)目基本內(nèi)容

項(xiàng)目基本技術(shù)方法

2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯提出使用句號(hào)特征進(jìn)行重復(fù)網(wǎng)頁(yè)檢測(cè)提出CCS和CLR聯(lián)合度量模型和方法計(jì)算網(wǎng)頁(yè)的相似性，以判定網(wǎng)頁(yè)之間是否為重復(fù)關(guān)系或者包含關(guān)系引入IDF方法過濾噪音特征以進(jìn)一步過濾模板數(shù)據(jù)通過建立倒排文集來(lái)計(jì)算文檔之間的相似性采用圖論中尋找連通子圖的方法將具有重復(fù)關(guān)系和包含關(guān)系的網(wǎng)頁(yè)進(jìn)行有效的歸并采用MapReduce完成重復(fù)文檔檢測(cè)算法的并行化基于開源軟件系統(tǒng)（Hadoop，Nutch等）來(lái)實(shí)現(xiàn)整個(gè)原型系統(tǒng)項(xiàng)目基本內(nèi)容

項(xiàng)目基本技術(shù)方法

2012.10.29中國(guó)云88算法設(shè)計(jì)

句號(hào)特征的作用2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯觀察和研究表明，中文句號(hào)特征對(duì)中文網(wǎng)頁(yè)的相似性比較和重復(fù)文檔檢測(cè)具有顯著作用

1).網(wǎng)頁(yè)上的模板內(nèi)容一般不會(huì)出現(xiàn)句號(hào)，因此，通過提取句號(hào)特征就可以將大量這些模板內(nèi)容過濾2).基于提取的句號(hào)字串特征可以有效的計(jì)算網(wǎng)頁(yè)的相似性。模板內(nèi)容算法設(shè)計(jì)

句號(hào)特征的作用2012.10.29中國(guó)云﹒移動(dòng)互89算法設(shè)計(jì)

句號(hào)字串特征的提取2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯我們采用以下方法提取句號(hào)字串特征：將網(wǎng)頁(yè)中“句號(hào)”前固定長(zhǎng)度（比如10）的字符串作為這個(gè)“句號(hào)”的特征值抽取出來(lái)。如果網(wǎng)頁(yè)中連續(xù)出現(xiàn)的兩個(gè)“句號(hào)”之間的字符串長(zhǎng)度小于所指定的固定長(zhǎng)度，那么取后者到前者之間的字符作為后者的特征值。如果網(wǎng)頁(yè)中連續(xù)出現(xiàn)的兩個(gè)“句號(hào)”之間的字符串長(zhǎng)度為0，則忽略后者的特征值。

句號(hào)字串特征算法設(shè)計(jì)

句號(hào)字串特征的提取2012.10.29中國(guó)云﹒移90算法設(shè)計(jì)

相似性度量模型

和重復(fù)網(wǎng)頁(yè)判定方法2012.10.29中國(guó)云﹒移動(dòng)互聯(lián)網(wǎng)創(chuàng)新大獎(jiǎng)賽答辯假設(shè)A、B為兩個(gè)文檔,a、b為對(duì)應(yīng)的句號(hào)字串特征集合，則定義CCS(CommonContain