container container containe大数据研究计划
• 大数据的计算理论 (2014-2018)
– 科技部973计划支持 – 共8家单位参与 • 主要关注大数据计算的特征、理 论、分布式系统等
17
973大数据研究计划
WP5.Pilot Applications (Social Data, Internet Search Engine Data)
•Use the data correlations to adjust the errors •Transfer Learning
大数据研究的几个问题
• 问题1: 大数据计算有“新的”理论问题吗?
计算问题
算法 数据
– Good: PTIME – Bad: NP-Hard – Ugly: PSPACE-hard, or EXPTIME-hard, undecidable
– Full System Virtualization: Xen, KVM, VMWare… – Lightweight container: Open VZ, vserver, Linux Container
23
多核平台的I/O可扩展性问题
• Scalability Issue within shared I/O stack
– 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
大数据的计算特征－3个I
4-V
Features of Big Data Computing
Inexact 非精确
Incremental
增量
Inductive
归纳性
•用户强交 互性 •跨多通道 快
Multi-source Datasets References between 973 Datasets
大数据的挑战
统计分布 假设检验等
样本 数据
统计学的采样方法
总体 [Population]
真实 世界
知识
大数据的挑战
统计分布 假设检验等
样本 数据
统计学的采样方法
总体 [Population]
真实 世界
日志，传感设备 摄像头， 社会网络周姑娘的人
知识 基于 模型的 预测
挖掘，学习 预处理
总体 [Population’]
• 小结
15
大数据国际研究中心（RCBD）
International Research Centre on Big Data (Founded in Sept 2012) /en/index.html
Beihang U. U. Edinburgh
HKUST

D (D)
Q1((D)) Q2((D)) 。 。
Does it work? If a linear scan of D could be done in log(|D|) time:

15 seconds when D is of 1 PB instead of 1.99 days 18 seconds when D is of 1 EB rather than 5.28 years
13
大数据研究的几个问题
• 问题3: 如何让计算更加“可操作”?
– 领域相关的计算特征分析
• 数据模式，数据动态特征, 查询的特征, … • 通用 vs. 专用 • 领域相关的知识及其利用
– 数据挖掘和机器学习方法 – 分布式系统
• • • •
离线计算Offline/在线计算Online 批处理/增量处理/流式处理 内存计算 新器件带来的新机会
WP4.Data Mining and Analyzing for Big Data
WP3.Energy Efficient Distributed Data Processing
WP1. Data Model and Understanding (Semantic/Visulization)
puting Complexity Theory and Algor特征－3个I
4-V
Inexact 非精确
Incremental
增量
Data arrives continuesly
•用户强交 互性 •跨多通道 快
Online/Realtime processing
•Hard to get an Static View of Data •Batch/Full data is not enough
– 开放数据 – W3C的Data Activity
• 小结
3
网络信息空间大数据
• 规模巨大，快速变化
社会网络
•4 Micro-blogger Provider in China: •800M Users, 200M tweets everyday, 20M+ Photos.
1PB data in DVD:
BD-tractable queries are feasible on big data
22
多核平台的I/O可扩展性问题
• Background
– Many core architecture
• Increase computing capability by increasing core number • Server Consolidation: Place multiple independent workloads within a single server for higher resource utilization, including data processing workload. • Multiple Virtualization approaches:
总体 [Population’]
?
如何从数据中寻找 知识并用于预测
问题相 关的采 样数据
多源大 数据集
?
数据质量？纠偏？ 如何让数据集代表总体？
?
重采样？降维？ 如何将大数据变小 大规模分布式 计算基础设施
新的统计理论 和数学工具
新的计算理论和 算法设计方法
大数据的计算特征－3个I
4-V
Inexact 非精确
18
部分初步的研究进展
• 理论和算法
– 大数据易解类问题（BD-Tractable）
• 分布式系统
– 多核I/O的性能优化 – 高时效性的计算平台 – 图模式匹配及分布式算法
• 大数据应用
– 基于社会网络的突发事件检测
19
BD-Tractable with Preprocessing
• 当数据量大时，多项式时间的查询也变得无法处理 Polynomial time queries become intractable on big data • 我们需要回答一个查询在考虑了数据量后（大数据）是否 仍是易解（feasible）
问题相 关的采 样数据
多源大 数据集
新的统计理论 和数学工具
新的计算理论和 算法设计方法
大规模分布式 计算基础设施
大数据的挑战
统计分布 假设检验等
样本 数据
统计学的采样方法
总体 [Population]
真实 世界
日志，传感设备 摄像头， 社会网络周姑娘的人
知识 基于 模型的 预测
挖掘，学习 预处理
4
Chomolung ma 8,800m
大数据中广泛提到的“4V”特性
Volume
Velocity
Variety
Value
•In PB or EB •Distributed data
•Dynamic Changes •Updated constantly
•Heterogeneous •Semi-structured or unstructured
不可判定 问题
可判定 问题 易解问题
难解问题
近似算法 (in PTIME)
大数据 难解问题
大数据 易解问题
12
大数据研究的几个问题
• 问题2: Hadoop(或MapReduce)是否是数据处理所必 须的?
– 不同的计算需求，不同的用户场景，不同的算法设计思想
•MapReduce
(OSDI 2004)
14
内容提要
• 对大数据的理解
– 背景 – 大数据计算的“3-I”挑战
• 大数据计算研究：北航初步实践
– – – –
理论方面：大数据计算的基础理论扩展 系统方面：多核I/O栈的性能优化 系统方面：高时效计算平台 应用方面：基于社会网络的突发事件检测
• 大数据的标准化：W3C的实践
– 开放数据 – W3C的Data Activity
增量性
•分布式的数据处理方式
MR显然不是唯一的解决方案 •增量计算: •Percolator by Google (OSDI 2010)
3I
新的算法设计思想 • 重采样 • 查询保持的数据压缩
• Partial evaluation and distributed processing • Top-k 查询和可终止计算… …
大数据计算：理论、实践与标准化
内容提要
• 对大数据的理解
– 背景 – 大数据计算的“3-I”挑战
• 大数据计算研究：北航初步实践
– – – –
理论方面：大数据计算的基础理论扩展 系统方面：多核I/O栈的性能优化 系统方面：高时效计算平台 应用方面：基于社会网络的突发事件检测