大數(shù)據(jù)計算：理論、實踐與標(biāo)準(zhǔn)化

1、大數(shù)據(jù)計算：理論、實踐與標(biāo)準(zhǔn)化大數(shù)據(jù)計算：理論、實踐與標(biāo)準(zhǔn)化內(nèi)容提要內(nèi)容提要 對大數(shù)據(jù)的理解 背景 大數(shù)據(jù)計算的“3-I”挑戰(zhàn) 大數(shù)據(jù)計算研究：北航初步實踐理論方面：大數(shù)據(jù)計算的基礎(chǔ)理論擴展系統(tǒng)方面：多核I/O棧的性能優(yōu)化系統(tǒng)方面：高時效計算平臺應(yīng)用方面：基于社會網(wǎng)絡(luò)的突發(fā)事件檢測 大數(shù)據(jù)的標(biāo)準(zhǔn)化：W3C的實踐 開放數(shù)據(jù) W3C的Data Activity 小結(jié)3網(wǎng)絡(luò)信息空間大數(shù)據(jù) 規(guī)模巨大，快速變化4Chomolungma 8,800m1PB data in DVD:25km1ZB=1PB106Airplane15,000m社會網(wǎng)絡(luò)4 Micro-blogger Provider inChi

2、na:800M Users, 200M tweetseveryday, 20M+ Photos.互聯(lián)網(wǎng)搜索Baidu：1PB log data per Day.Handling 1000PBGoogle：Processing 20PB dataeverydayIDC統(tǒng)計及預(yù)測Data doubled every 18 monthsData in CyberspaceIDC Report :2009: 0.8ZB2012: 2.7 ZB2020(E): 35ZB大數(shù)據(jù)中廣泛提到的“4V”特性5VolumeIn PB or EBDistributed dataVarietyHeterogeneou

3、sSemi-structuredor unstructuredValue Biz opportunity Sensitive DataVelocityDynamic ChangesUpdated constantlyWikipedialarge and complex datasets, which is quite difficult toprocess using existing data management tools, andtraditional data processing applicationsData Deluge大數(shù)據(jù)的挑戰(zhàn)真實世界樣本數(shù)據(jù)知識統(tǒng)計學(xué)的采樣方法統(tǒng)計分布

4、假設(shè)檢驗等總體Population大數(shù)據(jù)的挑戰(zhàn)真實世界樣本數(shù)據(jù)統(tǒng)計學(xué)的采樣方法統(tǒng)計分布假設(shè)檢驗等總體Population問題相關(guān)的采日志，傳感設(shè)備攝像頭，社會網(wǎng)絡(luò)周姑娘的人預(yù)處理挖掘，學(xué)習(xí)知識基于模型的預(yù)測總體Population多源大數(shù)據(jù)集樣數(shù)據(jù)新的計算理論和算法設(shè)計方法大規(guī)模分布式計算基礎(chǔ)設(shè)施新的統(tǒng)計理論和數(shù)學(xué)工具?大數(shù)據(jù)的挑戰(zhàn)真實世界樣本數(shù)據(jù)統(tǒng)計學(xué)的采樣方法統(tǒng)計分布假設(shè)檢驗等總體Population問題相關(guān)的采樣數(shù)據(jù)新的計算理論和算法設(shè)計方法大規(guī)模分布式計算基礎(chǔ)設(shè)施新的統(tǒng)計理論和數(shù)學(xué)工具?日志，傳感設(shè)備攝像頭，社會網(wǎng)絡(luò)周姑娘的人數(shù)據(jù)質(zhì)量？糾偏？如何讓數(shù)據(jù)集代表總體？知識基于 挖掘，學(xué)習(xí)模

5、型的預(yù)測如何從數(shù)據(jù)中尋找知識并用于預(yù)測總體Population預(yù)處理多源大數(shù)據(jù)集重采樣？降維？如何將大數(shù)據(jù)變小大數(shù)據(jù)的計算特征3個IAvoid exactresult to reducecostInexact butacceptableResultsInexact非精確Datasets areinexact: Noisy,Erros.Target are inexact.Eg. to find themacro trends.4-V用戶強交互性跨多通道快大數(shù)據(jù)的計算特征3個IData arrivescontinueslyOnline/RealtimeprocessingHard to get

6、anStatic View ofDataBatch/Full datais not enoughInexact非精確Incremental增量用戶強交互性跨多通道快4-V973大數(shù)據(jù)的計算特征3個IFeatures of Big Data ComputingInexact非精確Incremental增量Inductive歸納性Multi-sourceDatasetsReferencesbetweenDatasetsUse the datacorrelations toadjust the errorsTransferLearning用戶強交互性跨多通道快4-VEXPTIME-hard, und

7、ecidable12數(shù)據(jù) Good: PTIME Bad: NP-Hard Ugly: PSPACE-hard, or大數(shù)據(jù)難解問題大數(shù)據(jù)易解問題大數(shù)據(jù)研究的幾個問題 問題1: 大數(shù)據(jù)計算有“新的”理論問題嗎?計算問題算法不可判定問題難解問題可判定問題易解問題近似算法(in PTIME)大數(shù)據(jù)研究的幾個問題 問題2: Hadoop(或MapReduce)是否是數(shù)據(jù)處理所必須的? 不同的計算需求，不同的用戶場景，不同的算法設(shè)計思想13MapReduce (OSDI 2004)分布式的數(shù)據(jù)處理方式MR顯然不是唯一的解決方案增量計算:Percolator by Google (OSDI 2010)新

8、的算法設(shè)計思想 重采樣 查詢保持的數(shù)據(jù)壓縮 Partial evaluation and distributedprocessing Top-k 查詢和可終止計算 增量性3I大數(shù)據(jù)研究的幾個問題 問題3: 如何讓計算更加“可操作”? 領(lǐng)域相關(guān)的計算特征分析 數(shù)據(jù)模式，數(shù)據(jù)動態(tài)特征, 查詢的特征, 通用 vs. 專用 領(lǐng)域相關(guān)的知識及其利用 數(shù)據(jù)挖掘和機器學(xué)習(xí)方法 分布式系統(tǒng)離線計算Offline/在線計算Online批處理/增量處理/流式處理內(nèi)存計算新器件帶來的新機會14內(nèi)容提要內(nèi)容提要 對大數(shù)據(jù)的理解 背景 大數(shù)據(jù)計算的“3-I”挑戰(zhàn) 大數(shù)據(jù)計算研究：北航初步實踐理論方面：大數(shù)據(jù)計算的基礎(chǔ)理

9、論擴展系統(tǒng)方面：多核I/O棧的性能優(yōu)化系統(tǒng)方面：高時效計算平臺應(yīng)用方面：基于社會網(wǎng)絡(luò)的突發(fā)事件檢測 大數(shù)據(jù)的標(biāo)準(zhǔn)化：W3C的實踐 開放數(shù)據(jù) W3C的Data Activity 小結(jié)1516973大數(shù)據(jù)國際研究中心（RCBD）International Research Centre on BigData (Founded in Sept 2012)http:/ U.U. EdinburghHKUSTU.PennsylvaniaBaidu17973大數(shù)據(jù)研究計劃 大數(shù)據(jù)的計算理論 (2014-2018) 科技部973計劃支持 共8家單位參與 主要關(guān)注大數(shù)據(jù)計算的特征、理論、分布式系統(tǒng)等18WP1

10、. Data Model andUnderstanding(Semantic/Visulization)WP2.ComputingComplexity Theory andAlgorithms DesignWP4.Data Mining and Analyzing for Big DataWP3.Energy Efficient Distributed Data Processing973大數(shù)據(jù)研究計劃WP5.Pilot Applications(Social Data, Internet Search Engine Data)部分初步的研究進(jìn)展 理論和算法 大數(shù)據(jù)易解類問題（BD-Tract

11、able） 分布式系統(tǒng) 多核I/O的性能優(yōu)化 高時效性的計算平臺 圖模式匹配及分布式算法 大數(shù)據(jù)應(yīng)用 基于社會網(wǎng)絡(luò)的突發(fā)事件檢測1920BD-tractable queries: queries feasible on big dataBD-Tractable with Preprocessing 當(dāng)數(shù)據(jù)量大時，多項式時間的查詢也變得無法處理Polynomial time queries become intractable on big data 我們需要回答一個查詢在考慮了數(shù)據(jù)量后（大數(shù)據(jù)）是否仍是易解（feasible）NP and beyondPTIMEBD-tractablenotB

12、D-tractable21BD-Tractable with Preprocessing How do we dealing with SQL querys on a largeDATABASE? Scan through all the records? NO! Using Index to get better query performance! B-Tree index, from O(n) to O(logn) Query Optimizations! Two steps of computing Set up the “index”: preprocessing Doing que

13、ry on the “index”22BD-Tractable with PreprocessingA class Q of queries is BD-tractable if there exists a PTIME preprocessingfunction such thatfor any database D on which queries of Q are defined,all queries Q QBD-tractable queries are feasible on big dataD = (D) hence D is of polynomial size for pos

14、sible rewriting defined on D, Q(D) can be computed by evaluatingparallel logk(|D|, |Q|)15 seconds when D is of 1 PB instead of 1.99 days18 seconds when D is of 1 EB rather than 5.28 yearsD(D)Q1(D)Q2(D)。Does it work? If a linear scan of D could be done in log(|D|) time:多核平臺的I/O可擴展性問題 Background Many

15、core architecture Increase computing capability by increasing corenumber Server Consolidation: Place multiple independentworkloads within a single server for higherresource utilization, including data processingworkload. Multiple Virtualization approaches: Full System Virtualization: Xen, KVM, VMWar

16、e Lightweight container: Open VZ, vserver, LinuxContainer23The sharing of I/O stackcontainercontainercontainerNamespace virtualizationVirtual file systemhost file systemDriverHard DrivesPCIe-PCMPCIe-flashOS-level virtualization (e.g., OpenVZ)Can it be still neglectedmight lead to scalabilityissues o

17、n many coresThe interference is usuallymasked by the slowhardware performance onfast devices?24多核平臺的I/O可擴展性問題 Scalability Issue within shared I/O stack多核平臺的I/O可擴展性問題25Scalability bottleneck becomes a dominant factor in the performance of virtualizedenvironments on a RAM diskMultiLanes 面向多核的高效可擴展存儲 面

18、向數(shù)據(jù)處理節(jié)點多容器間性能干擾 已有研究：如何細(xì)粒度劃分和調(diào)度硬件，提供好的性能隔離 在多核快速存儲平臺，共享的I/O軟件棧造成競爭嚴(yán)重，可擴展性差 解決方案：面向多核的高效、可擴展的隔離數(shù)據(jù)I/O軟件棧 為每個容器提供完全隔離的數(shù)據(jù)I/O軟件棧：切分的虛擬文件系統(tǒng)和設(shè)備 設(shè)計實現(xiàn)的挑戰(zhàn) 高效性：最小化處理數(shù)據(jù)I/O的干擾開銷 可擴展性：在不可擴展的宿主機文件系統(tǒng)上，實現(xiàn)數(shù)據(jù)處理能力的擴展MultiLanesBaselineMySQL on Ext3FAST 2014高時效計算平臺 CEP、數(shù)據(jù)流應(yīng)用對高時效性計算的需求 大規(guī)模神經(jīng)網(wǎng)絡(luò)/KnowledgeGraph/PageRank計算：整個

19、是一個大網(wǎng)絡(luò)，實效性要求高 Realtime（時） Quality / Cost balance （效） Freshness（時效） 時效計算與傳統(tǒng)離線計算等往往是一個業(yè)務(wù)的不同環(huán)節(jié)，需要“整合” 資源利用率、動態(tài)調(diào)節(jié)增加時效的可能方法 大量的內(nèi)存Cache Memcache、RamCloud 內(nèi)存與計算節(jié)點的關(guān)系 Share All, or Share Nothing 數(shù)據(jù)流驅(qū)動 流式結(jié)構(gòu) 特定應(yīng)用場景的軟硬結(jié)合，F(xiàn)PGA硬件輔助 算法層面 增量算法分布式的圖模式匹配 Graph patter matching Providing evaluation algorithms andoptim

20、izations for graph simulation in adistributed setting29分布式圖計算的算法庫30最短路徑/距離（靜態(tài)、動態(tài)）圖模擬/強模擬流式Hotspot檢測圖數(shù)據(jù)庫分布式計算集群和框架(Hadoop, Spark)31社會網(wǎng)絡(luò)的突發(fā)事件檢測 社會網(wǎng)絡(luò)數(shù)據(jù)反映了現(xiàn)實生活 基于社會網(wǎng)絡(luò)數(shù)據(jù)的突發(fā)事件檢測Population TrendsEvent 期望的特點 語法上: streaming processing, realtime,scalable 語義上: Early detection. Ranking, Story tellingand event a

21、nalysis 流式數(shù)據(jù)圖式數(shù)據(jù)內(nèi)存計算分布式存儲高效分析與處理數(shù)據(jù)特征：分析方法?系統(tǒng)特征：處理技術(shù)？實時檢測實時性：檢測時機?有效性：主題及關(guān)聯(lián)性？數(shù)據(jù)獲取突發(fā)事件檢測增量聚類、異常檢測、圖處理、數(shù)據(jù)查詢等算法流式數(shù)據(jù)技術(shù)事件深度分析（用戶、傳播）應(yīng)用面臨挑戰(zhàn)問題問題：如何從海量、動態(tài)數(shù)據(jù)中快速檢測突發(fā)事件？社會網(wǎng)絡(luò)數(shù)據(jù)融合突發(fā)事件事件深度分析檢測（用戶、傳播）增量聚類、異常檢測內(nèi)存流式圖彈性實時計算處理索引分布式存儲34數(shù)據(jù)源應(yīng)用算法技術(shù)面臨挑戰(zhàn)問題系統(tǒng)效率 實時監(jiān)測實時性：信息秒級傳播數(shù)據(jù)量：具有突發(fā)特征多元輸入、噪音過濾多元性：時間地點人物數(shù)據(jù)質(zhì)量：稀疏性與噪音多維溯源、關(guān)聯(lián)分析多維

22、分析：反應(yīng)不同側(cè)面事件關(guān)聯(lián)：互為因果關(guān)系突發(fā)事件檢測基于情緒 Motion plays important role in social media How to detect theuser motion throughthe weibo text?35Work done by Prof. Ke Xu &Prof. Junjie Wu BeihangUniversity.突發(fā)事件檢測基于情緒 Classification 95 motion icons selected from 1000 icons Use the text with motion icons as the tra

23、iningsets36突發(fā)事件檢測基于情緒 Abnormal event detection Mood Searchhttp:/3738突發(fā)事件檢測基于關(guān)鍵詞的聯(lián)合出現(xiàn) Localized, Distributed, Stream ProcessingLocalizedFeature ExtractionGraph CommunityDetectionLocalizedAnomaly DetectionData PreprocessingCo-occurrence GraphBuildingAnalytical PreprocessingWord-Pair Co-occuranceMatrix

24、, Say NO.WordCo-occcurance Frequency array is the key elementWordWord Pair FrequencyWordWordEvent 1Event 2WordRing: 實時事件檢測系統(tǒng)39微博搜索實時微博實時熱點事件預(yù)警地域熱點Ring: 實時事件檢測系統(tǒng) 統(tǒng)計、事件檢測及場景還原40事41SanxiaFujian合肥地震Ring: 實時事件檢測系統(tǒng) 追蹤一個事件的產(chǎn)生、發(fā)展過程 案例：地震 四川地震 件 (2014.7.15-2014.7.30)Single EventTweet Forwarding轉(zhuǎn)發(fā):四川身邊事原創(chuàng)：四川同

25、城會MotionsRing: 實時事件檢測系統(tǒng) 追蹤一個事件的產(chǎn)生、發(fā)展過程 案例：地震事件 (2014.7.15-2014.7.30) 子事件檢測與關(guān)聯(lián)分析 Timeline: Reason-Result Analysis Drill Down: Get sub-event view.42Ring: 實時事件檢測系統(tǒng) 分布式爬蟲 From April 2014 10M Tweets per day 分布式系統(tǒng)支持 Distributed in-memory computing platform Distributed elastic indexing 核心算法 Event detection

26、 Realtime statistics43內(nèi)容提要內(nèi)容提要 對大數(shù)據(jù)的理解 背景 大數(shù)據(jù)計算的“3-I”挑戰(zhàn) 大數(shù)據(jù)計算研究：北航初步實踐理論方面：大數(shù)據(jù)計算的基礎(chǔ)理論擴展系統(tǒng)方面：多核I/O棧的性能優(yōu)化系統(tǒng)方面：高時效計算平臺應(yīng)用方面：基于社會網(wǎng)絡(luò)的突發(fā)事件檢測 大數(shù)據(jù)的標(biāo)準(zhǔn)化：W3C的實踐 開放數(shù)據(jù) W3C的Data Activity 小結(jié)442014: Web誕生25周年 Web 25周年 1989 Tim Berners Lee, Technical Report45W3C: 國際萬維網(wǎng)聯(lián)盟 成立于1994年，近400家會員單位 全球四總部，約80名全職員工，制定Web領(lǐng)域的技術(shù)標(biāo)準(zhǔn)

27、 Open, Royalty Free 開放Web平臺 HTML5系列 多語言 WAI 服務(wù)更多行業(yè)移動互聯(lián)網(wǎng)數(shù)字電視電子出版Web支付車載平臺46 W3C China Host () 2006年設(shè)立辦事處, 2013年設(shè)立W3C中國總部 36家會員單位（約占全球會員總數(shù)十分之一），成為互聯(lián)網(wǎng)產(chǎn)業(yè)與標(biāo)準(zhǔn)的橋梁 ChineseW3C 中國開放數(shù)據(jù)與數(shù)據(jù)標(biāo)準(zhǔn)化 數(shù)據(jù)是Web上的資源 Data on the Web Tim B-Lee的四條規(guī)則 (2006) 使用URI作為“事物”的代表 使用HTTP URIs幫助用戶查找 當(dāng)用戶訪問

28、一個URI時，通過RDF*, SPARQL提供更多信息 包括指向其他URI的鏈接，幫助用戶發(fā)現(xiàn)更多信息 /DesignIssues/LinkedData.html W3C在語義網(wǎng) (Semantic Web)的努力48開放數(shù)據(jù)與數(shù)據(jù)標(biāo)準(zhǔn)化 開放互聯(lián)：評價數(shù)據(jù)的5星準(zhǔn)則 數(shù)據(jù)在Web上開放 數(shù)據(jù)以機器可讀的結(jié)構(gòu)化數(shù)據(jù)格式公開 采用開放格式 數(shù)據(jù)可以通過開放格式由第三方引用 數(shù)據(jù)與第三方數(shù)據(jù)交叉引用以提供更多上下文49LDP:Linked Data Platform（互聯(lián)數(shù)據(jù)平臺） LDP希望提供一個數(shù)據(jù)資源互聯(lián)的網(wǎng)絡(luò) 類比Web Page構(gòu)成的網(wǎng)絡(luò) 2014.6.

29、19 Linked Data Platform CR50容器容器客戶端容器圖查詢W3C的數(shù)據(jù)標(biāo)準(zhǔn)計劃 W3C在關(guān)注越來越多的Web數(shù)據(jù) 2013年11月設(shè)立: Information & Knowledge Domain(INK) 技術(shù)領(lǐng)域 Data Formats: XML, CSV on the Web, GeospatialData Data Semantics: RDFa, RDF Data Shapes Data APIs for Web Apps: Web Storage Linked Data Platform: LDP, e-Government Data Securi

30、ty & Privacy: Privacy Protection Use Cases: Data on the Web Best Practice Applications: Social Web, Government Linking Data51APIs for Web Apps: Web Storage52歡迎RDFa, RDF DataW3C的數(shù)據(jù)標(biāo)準(zhǔn)計劃 W3C在關(guān)注越來越多的Web數(shù)據(jù) 2013年11月設(shè)立: Information & Knowledge Domain(INK) 技術(shù)領(lǐng)域 Data Formats: XML, CSV on the Web, Geo

31、spatialData Data Semantics: 您的關(guān)注和參與 Shapes Data提供標(biāo)準(zhǔn)化需求、案例，定義基于 Linked Data Platform: LDP, e-Government Data Security & Privacy: Privacy Protection Use Cases: Data on the Web Best Practice Applications: Social Web, Government Linking Data內(nèi)容提要內(nèi)容提要 對大數(shù)據(jù)的理解 背景 大數(shù)據(jù)計算的“3-I”挑戰(zhàn) 大數(shù)據(jù)計算研究：北航初步實踐理論方面：大數(shù)據(jù)計算的

32、基礎(chǔ)理論擴展系統(tǒng)方面：多核I/O棧的性能優(yōu)化系統(tǒng)方面：高時效計算平臺應(yīng)用方面：基于社會網(wǎng)絡(luò)的突發(fā)事件檢測 大數(shù)據(jù)的標(biāo)準(zhǔn)化：W3C的實踐 開放數(shù)據(jù) W3C的Data Activity 小結(jié)53小結(jié) 大數(shù)據(jù)計算: 從4V到3I特征 非精確：Inexact 增量：Incremental 遞歸性：Inductive 大數(shù)據(jù)：交叉學(xué)科 應(yīng)用驅(qū)動的垂直整合 理論、算法、分布式系統(tǒng)、挖掘和機器學(xué)習(xí) 開放數(shù)據(jù)與標(biāo)準(zhǔn)化 開放數(shù)據(jù)的“五星”分類 開放數(shù)據(jù)、數(shù)據(jù)格式、數(shù)據(jù)語義的標(biāo)準(zhǔn)化有助于建造更豐富的大數(shù)據(jù)應(yīng)用生態(tài)環(huán)境54致謝 Part of the slides borrowed fromProf. Wenfei Fan at RCBD,Prof. Ke Xu at NLSDE, Beihang UniversityProf. Shuai Ma, Dr. Jianxi