大数据计算：理论、实践与标准化

1、大数据计算：理论、实践与标准化大数据计算：理论、实践与标准化内容提要内容提要 对大数据的理解 背景 大数据计算的“3-I”挑战 大数据计算研究：北航初步实践理论方面：大数据计算的基础理论扩展系统方面：多核I/O栈的性能优化系统方面：高时效计算平台应用方面：基于社会网络的突发事件检测 大数据的标准化：W3C的实践 开放数据 W3C的Data Activity 小结3网络信息空间大数据 规模巨大，快速变化4Chomolungma 8,800m1PB data in DVD:25km1ZB=1PB106Airplane15,000m社会网络4 Micro-blogger Provider inChi

2、na:800M Users, 200M tweetseveryday, 20M+ Photos.互联网搜索Baidu：1PB log data per Day.Handling 1000PBGoogle：Processing 20PB dataeverydayIDC统计及预测Data doubled every 18 monthsData in CyberspaceIDC Report :2009: 0.8ZB2012: 2.7 ZB2020(E): 35ZB大数据中广泛提到的“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大数据的挑战真实世界样本数据知识统计学的采样方法统计分布

4、假设检验等总体Population大数据的挑战真实世界样本数据统计学的采样方法统计分布假设检验等总体Population问题相关的采日志，传感设备摄像头，社会网络周姑娘的人预处理挖掘，学习知识基于模型的预测总体Population多源大数据集样数据新的计算理论和算法设计方法大规模分布式计算基础设施新的统计理论和数学工具?大数据的挑战真实世界样本数据统计学的采样方法统计分布假设检验等总体Population问题相关的采样数据新的计算理论和算法设计方法大规模分布式计算基础设施新的统计理论和数学工具?日志，传感设备摄像头，社会网络周姑娘的人数据质量？纠偏？如何让数据集代表总体？知识基于 挖掘，学习模

5、型的预测如何从数据中寻找知识并用于预测总体Population预处理多源大数据集重采样？降维？如何将大数据变小大数据的计算特征3个IAvoid exactresult to reducecostInexact butacceptableResultsInexact非精确Datasets areinexact: Noisy,Erros.Target are inexact.Eg. to find themacro trends.4-V用户强交互性跨多通道快大数据的计算特征3个IData arrivescontinueslyOnline/RealtimeprocessingHard to get

6、anStatic View ofDataBatch/Full datais not enoughInexact非精确Incremental增量用户强交互性跨多通道快4-V973大数据的计算特征3个IFeatures of Big Data ComputingInexact非精确Incremental增量Inductive归纳性Multi-sourceDatasetsReferencesbetweenDatasetsUse the datacorrelations toadjust the errorsTransferLearning用户强交互性跨多通道快4-VEXPTIME-hard, und

7、ecidable12数据 Good: PTIME Bad: NP-Hard Ugly: PSPACE-hard, or大数据难解问题大数据易解问题大数据研究的几个问题 问题1: 大数据计算有“新的”理论问题吗?计算问题算法不可判定问题难解问题可判定问题易解问题近似算法(in PTIME)大数据研究的几个问题 问题2: Hadoop(或MapReduce)是否是数据处理所必须的? 不同的计算需求，不同的用户场景，不同的算法设计思想13MapReduce (OSDI 2004)分布式的数据处理方式MR显然不是唯一的解决方案增量计算:Percolator by Google (OSDI 2010)新

8、的算法设计思想 重采样 查询保持的数据压缩 Partial evaluation and distributedprocessing Top-k 查询和可终止计算 增量性3I大数据研究的几个问题 问题3: 如何让计算更加“可操作”? 领域相关的计算特征分析 数据模式，数据动态特征, 查询的特征, 通用 vs. 专用 领域相关的知识及其利用 数据挖掘和机器学习方法 分布式系统离线计算Offline/在线计算Online批处理/增量处理/流式处理内存计算新器件带来的新机会14内容提要内容提要 对大数据的理解 背景 大数据计算的“3-I”挑战 大数据计算研究：北航初步实践理论方面：大数据计算的基础理

9、论扩展系统方面：多核I/O栈的性能优化系统方面：高时效计算平台应用方面：基于社会网络的突发事件检测 大数据的标准化：W3C的实践 开放数据 W3C的Data Activity 小结1516973大数据国际研究中心（RCBD）International Research Centre on BigData (Founded in Sept 2012)http:/ U.U. EdinburghHKUSTU.PennsylvaniaBaidu17973大数据研究计划 大数据的计算理论 (2014-2018) 科技部973计划支持 共8家单位参与 主要关注大数据计算的特征、理论、分布式系统等18WP1

10、. Data Model andUnderstanding(Semantic/Visulization)WP2.ComputingComplexity Theory andAlgorithms DesignWP4.Data Mining and Analyzing for Big DataWP3.Energy Efficient Distributed Data Processing973大数据研究计划WP5.Pilot Applications(Social Data, Internet Search Engine Data)部分初步的研究进展 理论和算法 大数据易解类问题（BD-Tract

11、able） 分布式系统 多核I/O的性能优化 高时效性的计算平台 图模式匹配及分布式算法 大数据应用 基于社会网络的突发事件检测1920BD-tractable queries: queries feasible on big dataBD-Tractable with Preprocessing 当数据量大时，多项式时间的查询也变得无法处理Polynomial time queries become intractable on big data 我们需要回答一个查询在考虑了数据量后（大数据）是否仍是易解（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、向数据处理节点多容器间性能干扰 已有研究：如何细粒度划分和调度硬件，提供好的性能隔离 在多核快速存储平台，共享的I/O软件栈造成竞争严重，可扩展性差 解决方案：面向多核的高效、可扩展的隔离数据I/O软件栈 为每个容器提供完全隔离的数据I/O软件栈：切分的虚拟文件系统和设备 设计实现的挑战 高效性：最小化处理数据I/O的干扰开销 可扩展性：在不可扩展的宿主机文件系统上，实现数据处理能力的扩展MultiLanesBaselineMySQL on Ext3FAST 2014高时效计算平台 CEP、数据流应用对高时效性计算的需求 大规模神经网络/KnowledgeGraph/PageRank计算：整个

19、是一个大网络，实效性要求高 Realtime（时） Quality / Cost balance （效） Freshness（时效） 时效计算与传统离线计算等往往是一个业务的不同环节，需要“整合” 资源利用率、动态调节增加时效的可能方法 大量的内存Cache Memcache、RamCloud 内存与计算节点的关系 Share All, or Share Nothing 数据流驱动 流式结构 特定应用场景的软硬结合，FPGA硬件辅助 算法层面 增量算法分布式的图模式匹配 Graph patter matching Providing evaluation algorithms andoptim

20、izations for graph simulation in adistributed setting29分布式图计算的算法库30最短路径/距离（静态、动态）图模拟/强模拟流式Hotspot检测图数据库分布式计算集群和框架(Hadoop, Spark)31社会网络的突发事件检测 社会网络数据反映了现实生活 基于社会网络数据的突发事件检测Population TrendsEvent 期望的特点 语法上: streaming processing, realtime,scalable 语义上: Early detection. Ranking, Story tellingand event a

21、nalysis 流式数据图式数据内存计算分布式存储高效分析与处理数据特征：分析方法?系统特征：处理技术？实时检测实时性：检测时机?有效性：主题及关联性？数据获取突发事件检测增量聚类、异常检测、图处理、数据查询等算法流式数据技术事件深度分析（用户、传播）应用面临挑战问题问题：如何从海量、动态数据中快速检测突发事件？社会网络数据融合突发事件事件深度分析检测（用户、传播）增量聚类、异常检测内存流式图弹性实时计算处理索引分布式存储34数据源应用算法技术面临挑战问题系统效率 实时监测实时性：信息秒级传播数据量：具有突发特征多元输入、噪音过滤多元性：时间地点人物数据质量：稀疏性与噪音多维溯源、关联分析多维

22、分析：反应不同侧面事件关联：互为因果关系突发事件检测基于情绪 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.突发事件检测基于情绪 Classification 95 motion icons selected from 1000 icons Use the text with motion icons as the tra

23、iningsets36突发事件检测基于情绪 Abnormal event detection Mood Searchhttp:/3738突发事件检测基于关键词的联合出现 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: 实时事件检测系统39微博搜索实时微博实时热点事件预警地域热点Ring: 实时事件检测系统 统计、事件检测及场景还原40事41SanxiaFujian合肥地震Ring: 实时事件检测系统 追踪一个事件的产生、发展过程 案例：地震 四川地震 件 (2014.7.15-2014.7.30)Single EventTweet Forwarding转发:四川身边事原创：四川同

25、城会MotionsRing: 实时事件检测系统 追踪一个事件的产生、发展过程 案例：地震事件 (2014.7.15-2014.7.30) 子事件检测与关联分析 Timeline: Reason-Result Analysis Drill Down: Get sub-event view.42Ring: 实时事件检测系统 分布式爬虫 From April 2014 10M Tweets per day 分布式系统支持 Distributed in-memory computing platform Distributed elastic indexing 核心算法 Event detection

26、 Realtime statistics43内容提要内容提要 对大数据的理解 背景 大数据计算的“3-I”挑战 大数据计算研究：北航初步实践理论方面：大数据计算的基础理论扩展系统方面：多核I/O栈的性能优化系统方面：高时效计算平台应用方面：基于社会网络的突发事件检测 大数据的标准化：W3C的实践 开放数据 W3C的Data Activity 小结442014: Web诞生25周年 Web 25周年 1989 Tim Berners Lee, Technical Report45W3C: 国际万维网联盟 成立于1994年，近400家会员单位 全球四总部，约80名全职员工，制定Web领域的技术标准

27、 Open, Royalty Free 开放Web平台 HTML5系列 多语言 WAI 服务更多行业移动互联网数字电视电子出版Web支付车载平台46 W3C China Host () 2006年设立办事处, 2013年设立W3C中国总部 36家会员单位（约占全球会员总数十分之一），成为互联网产业与标准的桥梁 ChineseW3C 中国开放数据与数据标准化 数据是Web上的资源 Data on the Web Tim B-Lee的四条规则 (2006) 使用URI作为“事物”的代表 使用HTTP URIs帮助用户查找 当用户访问

28、一个URI时，通过RDF*, SPARQL提供更多信息 包括指向其他URI的链接，帮助用户发现更多信息 /DesignIssues/LinkedData.html W3C在语义网 (Semantic Web)的努力48开放数据与数据标准化 开放互联：评价数据的5星准则 数据在Web上开放 数据以机器可读的结构化数据格式公开 采用开放格式 数据可以通过开放格式由第三方引用 数据与第三方数据交叉引用以提供更多上下文49LDP:Linked Data Platform（互联数据平台） LDP希望提供一个数据资源互联的网络 类比Web Page构成的网络 2014.6.

29、19 Linked Data Platform CR50容器容器客户端容器图查询W3C的数据标准计划 W3C在关注越来越多的Web数据 2013年11月设立: Information & Knowledge Domain(INK) 技术领域 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的数据标准计划 W3C在关注越来越多的Web数据 2013年11月设立: Information & Knowledge Domain(INK) 技术领域 Data Formats: XML, CSV on the Web, Geo

31、spatialData Data Semantics: 您的关注和参与 Shapes Data提供标准化需求、案例，定义基于 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内容提要内容提要 对大数据的理解 背景 大数据计算的“3-I”挑战 大数据计算研究：北航初步实践理论方面：大数据计算的

32、基础理论扩展系统方面：多核I/O栈的性能优化系统方面：高时效计算平台应用方面：基于社会网络的突发事件检测 大数据的标准化：W3C的实践 开放数据 W3C的Data Activity 小结53小结 大数据计算: 从4V到3I特征 非精确：Inexact 增量：Incremental 递归性：Inductive 大数据：交叉学科 应用驱动的垂直整合 理论、算法、分布式系统、挖掘和机器学习 开放数据与标准化 开放数据的“五星”分类 开放数据、数据格式、数据语义的标准化有助于建造更丰富的大数据应用生态环境54致谢 Part of the slides borrowed fromProf. Wenfei Fan at RCBD,Prof. Ke Xu at NLSDE, Beihang UniversityProf. Shuai Ma, Dr. Jianxi