<C8ABD2B3B4ABD5E6CDBCC6AC>

Size: px

Start display at page:

Download "<C8ABD2B3B4ABD5E6CDBCC6AC>"

聆景
7 years ago
Views:

2 主编副主编高福 ( 生命科学与医学科学 ) 王会军 ( 地球科学 ) 许甫荣 ( 物理学力学天文学 ) 韩布兴 ( 化学 ) 刘忠范 ( 材料科学 ) 何雅玲 ( 工程科学 ) 中国科学院微生物研究所 / 中国疾病预防控制中心中国科学院大气物理研究所北京大学物理学院中国科学院化学研究所北京大学化学与分子工程学院西安交通大学能源与动力工程学院编委 ( ) 王锐方盛国白永飞冯友军杨茂君余宏杰宋纯鹏兰州大学基础医学院浙江大学生命科学学院中国科学院植物研究所浙江大学医学院清华大学生命科学学院中国疾病预防控制中心河南大学生命科学学院张先恩张华堂张改平钟扬饶毅桂建芳中国科学院生物物理研究所重庆市科学技术研究院河南农业大学西藏大学 / 复旦大学生命科学学院北京大学生命科学学院中国科学院水生生物研究所董尔丹韩家淮傅小兰詹启敏裴端卿瞿礼嘉国家自然科学基金委员会医学科学部厦门大学生命科学学院中国科学院心理研究所中国医学科学院中国科学院广州生物医药与健康研究院北京大学生命科学学院邓涛中国科学院古脊椎动物与古人类研究所刘禹中国科学院地球环境研究所刘树华北京大学大气与海洋科学系李献华中国科学院地质与地球物理研究所吴立新中国海洋大学环境学院陆全明中国科技大学地球和空间科学学院杨进辉杨顶辉杨海军胡敏宫鹏袁训来中国科学院地质与地球物理研究所清华大学地球系统科学研究中心北京大学大气与海洋科学系北京大学环境科学与工程学院清华大学地球系统科学研究中心中国科学院南京地质古生物研究所柴育成高学杰鹿化煜葛全胜谢树成翦知湣国家自然科学基金委员会地球科学部中国气象局国家气候中心南京大学地理与海洋科学学院中国科学院地理科学与资源研究所中国地质大学 ( 武汉 ) 地球科学学院同济大学海洋与地球科学学院丁大军吉林大学原子与分子物理研究所马琰铭吉林大学超硬材料国家重点实验室邓元勇中国科学院国家天文台仝殿民山东大学物理学院兰岳恒清华大学物理系任治安中国科学院物理研究所孙扬张海澜李京波杨国桢汪景琇陈伟球上海交通大学物理与天文系中国科学院声学研究所中国科学院半导体研究所中国科学院物理研究所中国科学院国家天文台浙江大学工程力学系陈志坚祝世宁高杰章维益蔡荣根薛平北京大学物理学院南京大学物理学院中国科学院高能物理研究所南京大学物理学院中国科学院理论物理研究所清华大学物理系王官武方维海孔继烈申文杰刘志敏刘振宇齐利民中国科学技术大学化学系北京师范大学化学学院复旦大学化学系中国科学院大连化学物理研究所中国科学院化学研究所北京化工大学化工学院北京大学化学与分子工程学院吴骊珠张德清陈景文赵震夏兴华唐功利中国科学院理化技术研究所中国科学院化学研究所大连理工大学环境科学与工程系中国石油大学 ( 北京 ) 化学科学与工程学院南京大学化学化工学院中国科学院上海有机研究所曹荣梁文平尉志武韩艳春景传勇薄志山中国科学院福建物质结构研究所国家自然科学基金委员会化学科学部清华大学化学系中国科学院长春应用化学研究所中国科学院生态环境研究中心北京师范大学化学学院于吉红吉林大学无机合成与制备化学国家重点实验室马旭村清华大学物理系马於光华南理工大学材料科学与工程学院艾华四川大学国家生物医学材料工程技术研究中心成会明中国科学院金属研究所朱贤方厦门大学中国 - 澳大利亚功能纳米材料联合实验室孙洪波吉林大学电子科学与工程学院吴一弦张华张洪杰张跃张锦北京化工大学材料科学与工程学院 School of Materials Science and Engineering, Nanyang Technological University, Singapore 中国科学院长春应用化学研究所北京科技大学材料科学与工程学院北京大学化学与分子工程学院陈立东胡文平高瑞平郭万林韩秀峰焦丽颖中国科学院上海硅酸盐研究所中国科学院化学研究所国家自然科学基金委员会南京航空航天大学纳米科学研究所中国科学院物理研究所清华大学化学系丁汉华中科技大学机械学院马连湘青岛科技大学机电工程学院王如竹上海交通大学机械与动力工程学院孙元章武汉大学电气工程学院宇波中国石油大学 ( 北京 ) 机械与储运工程学院余锡平清华大学水利系吴伟仁张兴张寅平李印实苏万华宣益民国防科技工业局探月与航天工程中心清华大学航天航空学院工程热物理研究所清华大学建筑学院西安交通大学能源与动力工程学院天津大学内燃机燃烧学国家重点实验室南京航空航天大学能源与动力学院胡喜军荣命哲倪晋仁谢和平路新春戴振东香港科技大学化学工程及分子生物工程系西安交通大学电气工程学院北京大学环境科学与工程学院四川大学水利水电学院清华大学精密仪器与机械学系南京航空航天大学航空宇航学院 csb.scichina.com

3 链接到网站 CHINESE SCIENCE BULLETIN (KEXUE TONGBAO) 目次 2015 年 2 月, 第 60 卷, 第 5-6 期专辑 : 大数据研究与应用封面说明大数据是当前 IT 信息技术研究和应用的热点, 面临量大 (Volume) 速度快 (Velocity) 和多样性 (Variety) 等多 V 挑战. 目前的研究多针对量大和速度快的问题, 并集中在系统和应用层面, 而针对多样性和理论基础方面的研究相对较少. 陈国良研究组以计算复杂性理论为基础, 针对大数据多 V 挑战, 着重研究大数据的可计算性及其计算原理, 初步提出了一个大数据并行计算框架. 首先将多种类型的大数据抽象到度量空间进行统一化表示以解决多样性问题, 其次在度量空间中基于距离对大数据进行划分, 最后运用 NC 类计算理论等并行计算理论和方法对大数据问题进行并行求解, 以解决量大和快速等问题. 封面展示了大数据并行计算框架. 详见陈国良等人文 (p566). 编者按 425 : 观点张云泉, 徐葳, 龙桂鲁 427 陈左宁, 王广益, 胡苏太, 韦海亮., 433 : 张平, 崔琪楣, 侯延昭, 徐瑨,.,. 439 陈刚, 崔辰州, 于策, 肖健, 何勃亮, 李长华, 樊东卫, 王传军, 曹子皇, 范玉峰, 洪智, 李珊珊, 米琳莹, 裘实, 万望辉, 王建国, 王甲卫, 尹树成, 郝晋新, 薛艳杰, 刘梁, 陈肖, 张海龙, 谌俊毅, 乔翠兰, 苏丽颖,,. 450 赵岑, 李梦然, 金日峰 ;, csb.scichina.com

4 目次 2015 年 2 月, 第 60 卷, 第 5-6 期 CHINESE SCIENCE BULLETIN 453 刘晓曙,. p p : 王飞跃, 王晓, 袁勇, 王涛, 林懿伦, 470 : 何国金, 王力哲, 马艳, 张兆明, 王桂周, 彭燕, 龙腾飞, 张晓美,., 479 王辉, 刘娜, 逄仁波, 孙晓宇 3 进展 p p : 李武军, 周志华 ( ).,,., 491 魏矿荣, 刘慎超, 魏东霖, 梁智恒, 陈万青,. 评述 499 王书浩, 龙桂鲁.,,, p p 唐杰, 陈文光?. csb.scichina.com

5 CHINESE SCIENCE BULLETIN 2015 年 2 月, 第 60 卷, 第 5-6 期目次 520 : 喻丰, 彭凯平, 郑先隽,,.,,. 534 宁康, 陈挺,.,. 547 周琳, 孔雷, 赵方庆,.,. 558 快讯严鑫, 丁鹏, 刘志红, 王领, 廖晨钟, 顾琼, 徐峻, 论文陈国良, 毛睿, 陆克中., NC.,. 570 MOOCs 李曼丽, 黄振中 p p534 MOOCs? MOOCs? p p csb.scichina.com

6 (Published three issues every month) CHINESE SCIENCE BULLETIN Main Contents Volume 60 Number 5-6 February Independence and controllability of big data security CHEN ZuoNing, WANG GuangYi, HU SuTai & WEI HaiLiang 433 Opportunities and challenges of wireless networks in the era of mobile big data ZHANG Ping, CUI QiMei, HOU YanZhao & XU Jin 439 Challenges of big data in science researches CHEN Gang 445 Astronomy research in big-data era CUI ChenZhou, YU Ce, XIAO Jian, HE BoLiang, LI ChangHua, FAN DongWei, WANG ChuanJun, CAO ZiHuang, FAN YuFeng, HONG Zhi, LI ShanShan, MI LinYing, QIU Shi, WAN WangHui, WANG JianGuo, WANG JiaWei, YIN ShuCheng, HAO JinXin, XUE YanJie, LIU Liang, CHEN Xiao, ZHANG HaiLong, CHEN JunYi, QIAO CuiLan & SU LiYing 450 Privacy in big data era ZHAO Cen, LI MengRan & JIN Garrett 453 Development trend and coping strategies of financing sector in big data era LIU XiaoShu 460 Social computing and computational societies: The foundation and consequence of smart societies WANG FeiYue, WANG Xiao, YUAN Yong, WANG Tao & LIN YiLun 470 Processing of earth observation big data: Challenges and countermeasures HE GuoJin, WANG LiZhe, MA Yan, ZHANG ZhaoMing, WANG GuiZhou, PENG Yan, LONG TengFei & ZHANG XiaoMei 479 Global ocean forecasting and scientific big data WANG Hui, LIU Na, PANG RenBo & SUN XiaoYu 485 Learning to hash for big data: Current status and future trends LI WuJun & ZHOU ZhiHua 491 Influence of big data on the development of cancer registration methods WEI KuangRong, LIU ShengChao, WEI DongLing, LIANG ZhiHeng & CHEN WanQing 499 Big data and quantum computation WANG ShuHao & LONG GuiLu 509 Deep analytics and mining for big social data TANG Jie & CHEN WenGuang 520 Big data and psychology in China YU Feng, PENG KaiPing & ZHENG XianJun 534 Big data for biomedical research: Current status and prospective NING Kang & CHEN Ting 547 Current status and challenges in biological big data visualization ZHOU Lin, KONG Lei & ZHAO FangQing 558 Big data in drug design YAN Xin, DING Peng, LIU ZhiHong, WANG Ling, LIAO ChenZhong, GU Qiong & XU Jun 566 Parallel computing framework for big data CHEN GuoLiang, MAO Rui & LU KeZhong 570 Exploration of educational empirical research based on big data from MOOCs platforms LI ManLi & HUANG ZhenZhong csb.scichina.com

7 n doc 王艳玲 2015 年第 60 卷第 5-6 期 :566 ~ 569 专辑 : 大数据研究与应用快讯 csb.scichina.com 中国科学杂志社 SCIENCE CHINA PRESS 大数据并行计算框架陈国良 123, 毛睿 123* 123, 陆克中 1 深圳大学计算机与软件学院, 深圳 ; 2 广东省普及型高性能计算机重点实验室, 深圳 ; 3 深圳市服务计算与应用重点实验室, 深圳 * 联系人, mao@szu.edu.cn 收稿, 接受, 网络版发表国家高技术研究发展计划 (2012AA01A309) 国家自然科学基金委- 广东联合基金 (U ) 国家自然科学基金( , ) 广东省重点实验室建设项目 (2012A ) 和深圳市科技计划项目 (JCYJ , SGLH , JCYJ ) 资助摘要大数据是当前 IT 信息技术研究和应用的热点, 但目前的研究多集中在系统和应用层面, 而理论基础研究方面相对较少. 本文以计算复杂性理论为基础, 针对大数据量大快速和多样性等挑战, 着重研究大数据的可计算性及其计算原理. 首先将多种类型的大数据抽象到度量空间进行统一化表示以解决多样性问题, 其次在度量空间中基于距离对大数据进行划分, 最后运用 NC 类计算理论等并行计算理论和方法对大数据问题进行并行求解, 以解决量大和快速等问题. 本文从更广的视角, 根据大数据的特性和大数据整个生命周期, 提出处理大数据的策略和技术以及需要变革思维方法研究大数据. 关键词 NC 类计算度量空间数据划分可计算性当今, 除了传统的大科学和工程所产生的大数据外, 网络连接的世界也涌现出了大数据, 同时一些新技术 ( 如传感技术新型通信技术等 ) 和新应用 ( 如物联网和云计算等 ) 也催生了大数据. 大数据 (big data) 的时代已经到来, 大数据潮流汹涌澎湃, 已经成了当代 IT 信息技术研究和应用的热点. 然而目前对大数据的研究, 大多集中在大数据的系统技术和应用实践层面 [1~3], 理论基础方面的探讨相对较少. 本文以计算复杂性理论为基础, 着重研究大数据的可计算性 (computability) 及其计算原理 (computational principle), 主要包括大数据的统一抽象表示, 大数据的划分技术和大数据的 NC 类 (Nick s class) 计算理论. 众所周知, 常规的串行计算问题类主要集中在 P 类问题上, 即在确定的图灵机上多项式 (polynomial) 时间内可求解的一类问题. 然而在大数据时代, 由于计算函数的对象, 即变量和数据, 非常庞大, 例如可在 EB 字节 (E=10 18 ) 数量级, 即使采用非常快的读写设备 ( 例如速度可达 6G b/s 的硬盘 ), 线性扫描此数组, 也可能需要达 5 年多时间! 从实用的角度, 此时间已无法接受, 而此类的问题就变成了不可解 (intractable) 问题了. 即它属于在理论上能解, 而实际上求解时间太长而无法使用的不可解问题 [4]. 如何使不可解问题变成可解问题 (tractable problem) 呢? 其实解决此类问题的思想非常简单朴素, 那就是使用并行计算 (parallel computing) 技术, 即把一个原来大而复杂的计算问题, 分解成若干个规模较小可以应对的子问题, 然后使用多个处理器同时并行求解诸子问题, 最终获得原问题的求解. 如果所分解的子问题的个数是多项式数目个, 且可采用多项式数目个处理器, 在 PRAM 模型上对其在对数多项式时间内 (polylogrithmic time) 快速完成求解, 这就是著名的 NC 类计算 [5]. 大数据除了大容量 (volume) 和快速率 (velocity) 外, 还有一个重要特性就是多样性 (variety), 泛指类型和来源的广泛, 包括结构化的数据库表格数据, 结构化和半结构化的文本图像视频数据, 非结构化的动态间断流数据等. 对这些数据施行计算前, 如何将它进行统一的表示呢? 其中的一种方法就是本节介绍的度量空间表示法. (ⅰ) 距离和度量. 数据, 尤其是复杂数据, 除了用类型 ( 如文本图像视频等 ) 表征外, 还要用距离衡量彼此的关系和相似性, 例如编辑距离海明距离欧几里得距离曼哈顿距离豪斯多夫 (Hausdroff) 距离等. 在数学引用格式 : 陈国良, 毛睿, 陆克中. 大数据并行计算框架. 科学通报, 2015, 60: Chen G L, Mao R, Lu K Z. Parallel computing framework for big data (in Chinese). Chin Sci Bull, 2015, 60: , doi: /N

8 快讯上, 一个非空集合中的元素之间的距离, 叫做度量 (metric), 所以度量就是距离 (distance). 在拓扑学中, 度量往往和度量空间相关联 [6]. (ⅱ) 度量和度量空间. 设 X 为非空集合, d: X X R 为函数, 如果 x, y, z X 满足 : (1) d(x, y) = d(y, x)( 对称性 ); (2) d(x, y) 0 和 d(x, y) = 0 iff x = y( 半正定性 ); (3) d(x, z) d(x, y) + d(y, z)( 三角不等式 ), 则称 d 为 X 上的一个度量 (metric) [6], 偶对 (X, d) 为度量空间 (metric space) [6], d(x, y) 称为是 x 与 y 间的距离. 可见度量空间就是一个带距离函数的数据集合, 距离函数满足对称性半正定性和三角不等性. (ⅲ) 大数据的度量空间表示. 在度量空间中, 不管什么来源的大数据, 其数据元素之间都表示为成对数偶的距离 d(x, y), 这种距离代表了数据之间的关联和相似性. 在下面介绍的数据划分技术中, 划分就是基于距离这个属性参数进行的 [7]. 在度量空间中所有的数偶对 (x, y) 均具有距离 d(x, y), 此距离是个相对值, 其元素 x, y 并没有坐标. 为此我们可以在度量空间选择一些支撑点 (pivots) 作为参考点, 这样就可以将度量空间数据集合中的元素按照距离支撑点的远近实行划分了. (ⅰ) 度量空间的坐标化. (1) 约定 : 令 (M, d) 是一个度量空间, S = {x i x i M, i=1, 2,, n} 是 M 中的一个数据集, S M; 在 S 中选择若干参考点, 称为支撑点 (pivots), P = {p j j = 1, 2,, k}, P S. (2) 映射 : 将度量空间 M 中数据集 S 映射到 k 维实数空间 : S R k : I P,d (x) = (d(x, p 1 ), d(x, p 2 ),, d(x, p k )), x S, 其中 d(x, p i ) 是 x 到 p i 的距离. 这样, 度量空间 M 中的数据集 S 的任意元素 x i 都赋予了坐标 [8]. (ⅱ) 支撑点空间 (pivots space) 的定义. (1) 根据上述的 S R k 映射, 支撑点空间可定义为 : I P,d (S) = {x P x P = I P,d (x) = (d(x, p 1 ), d(x, p 2 ),, d(x, p k )), x S}. 实际上, 支撑点空间就是度量空间中的元素集合 S 在多维实数空间中的映象, 其每个元素的各个坐标是相应的度量空间中数据到各个支撑点的距离. (2) 完全支撑点空间. 将度量空间中的所有点都选为支撑点就得到了完全支撑点空间 [9] : P=S, M R n. I S,d (S) = {x S x S = I S,d (x) = (d(x, x 1 ), d(x, x 2 ),, d(x, x k )), x S}. (ⅲ) 支撑点的选择. 在度量空间中选择一组支撑点的依据就是所讲的元素间的距离. 用什么样的标准, 根据这些不同的距离值 d(x, y) 选取一组好的支撑点呢? 直观上讲, 一组好的支撑点均具有离群点 (outliers) 特点, 即, 一组好的支撑点不仅本身彼此之间距离遥远, 而且这些点距离度量空间中的其余元素也要足够远. 当然并不是所有离群点都可以是好的支撑点 [10]. 数据可以按照不同的属性进行划分. 本文介绍的划分技术是基于距离远近进行划分的, 其中, 数据偶对在度量空间中都具有距离 d(x, y), 进而数据元素本身在支撑点空间中都赋予参照坐标 d(x, p i ). 也就是说, 具体划分时, 数据元素 x 均按照其在支撑点空间中的坐标, 也就是其距离支撑点 p i 的距离 d(x, p i ) 而划分成不同部分 [11]. ( ⅰ ) 超平面 (hyper-plane) 划分. 其步骤为 ( 图 1): 首先选择中心点 ( 支撑点 )C 1 和 C 2 ; 再划一超平面 L( 做 C 1 和 C 2 的垂直平分线 ); 数据按距离 C 1 和 C 2 的远近划分之 [12]. (ⅱ) 有利点 (vantage point, VP) 划分. 划分步骤为 ( 图 2): 选择有利点 VP 1, 以 VP 1 为圆心 R 1 为半径画 1 圆 ; 数据按位于圆内外划分之 ; 以此类推, 图 1 ( 网络版彩色 ) 超平面划分 Figure 1 (Color online) Hyper-plane partitioning 图 2 ( 网络版彩色 ) 有利点划分 Figure 2 (Color online) Vantage point partitioning 可以再从圆内外分别选择有利点 VP 2 1, VP 2 2, 分别以 R 2 1 和 R 2 2 为圆心画圆, 如此递归重复 [13]. (ⅲ ) 包络球 (bounding sphere) 划分. 划分步骤为 ( 图 3): 选择中心点 C 1, 以其为圆心 R(C 1 ) 为半径画 1 圆, 包含了所有数据 ; 在上述圆内另选中心点 C 2, C 3, 再以其为圆心, 以 R(C 2 ) 和 R(C 3 ) 为半径画圆, 将数据划分成 2 部分 ; 此 2 圆均在以 C 1 为圆心的圆内, 且所有点均在 2 圆内 [14]. 大数据的计算理论, 主要是研究大数据的并行计算方法, 问题集中在 P 类问题的并行化上, 特别是 P 类问题的 NC 类并行计算 [15]. 面对大数据, P 类问题往往也成了不可解问题 (intractable problem), 而大数据的 NC 类计算在使用处理器的数目上和问题的求解时间上也有一些值得考虑的问题. C 1 C 2 C 3 图 3 ( 网络版彩色 ) 包络球划分 Figure 3 (Color online) Bounding sphere partitioning 567

9 2015 年 2 月第 60 卷第 5-6 期 (ⅰ) P 类问题及其并行化. 大数据并行化所瞄准的问题是串行计算量 W(n) 为多项式 (polynomial) 时间的 P 类问题, 即在确定的 (deterministic) 的图灵机上, 可在多项式时间内求解的一类问题. 在 P 类问题中, 有些问题, 包括整数的 +, -,, 串行运算, 串行矩阵运算和前缀计算等均可有效地被并行化执行. 然而, 并非所有的 P 类问题都是可有效并行化的, P 类中的有些问题具有天然 ( 固有 ) 的串行性, 例如 P 完全 (P complete) 问题, 包括电路值问题线性不等式最大流问题等, 不能通过并行方法显著加速, 所以被认为是难并行化的问题. 并行化时所选用的处理器数目 P(n) 可基于如下事实 : 因为并行化的主要目标是降低并行计算求解时间 T(n), 而针对 P 类问题的并行化应将并行求解时间 T(n) 减少到低于多项式时间 ( 例如对数多项式时间 ). 根据 P(n) T(n) W(n), 显然当 W(n) 为多项式和 T(n) 低于多项式时间时, P(n) 选择为多项式数目个是合理的. (ⅱ) NC 类问题. 目前大家熟知的, P 类中有些问题, 其中 NC 类问题 (NC P) 是可以被有效地在并行机上求解的, 它使用了 P(n)= 多项式数目处理器, 可在 T(n)= 对数多项式 (polylog) 时间内求解. 常见的 NC 类问题包括整数的 +, -,, 并行运算, 并行矩阵运算和前缀计算, 选择和排序, 图的双连通和连通片极大匹配等. 许多 NC 类计算问题可以是成本最优的, 例如并行扫描 (scan), 其 T(n)=O(logn), P(n)=n/logn, W(n)=O(n). 有些成本最优的 NC 类算法是超快的, 例如并行串匹配算法, 其 T(n)=O(loglogn), P(n)= n/logn. ( ⅲ ) 大数据的 NC 类计算. (1) NC i 类均衡电路定义. NC i 可定义为可计算的一组函数, 它可由一簇均衡电路输出的一组布尔函数值表示, 其中电路有多项式数目个门 ( 每个门至多两个输入 ), 深度为 O(log i n), i 1. 按此, 电路越深, 表示电路的延迟级数越多. (2) NC 类的层次关系. NC 类一般定义 : NC = k 1 NC k ; 显然 NC i 类层次满足如下关系 : NC 1 NC 2 NC i. (3) NC 类与 PRAM 模型关系. 定义 EREW k, CREW k 和 CRCW k 分别由使用多项式数目的处理器运行时间为 O(log k n) 对数多项式的并行计算模型 PRAM-EREW, PRAM-CREW 和 PRAM-CRCW 可计算的一类函数, 则 NC 类与 PRAM(parallel random access machine) 模型的关系如下 : NC k EREW k CREW k CRCW k NC k+1. (4) 大数据的 NC 类计算. 在 PRAM 模型上, 首先将大数据集 D 划分成多项式数目个子集 D i (i=1, 2,, 多项式数目个 ); 然后对 D i 在对数多项式时间内施行并行处理. 如果上述步骤证明是可行的, 则称此类大数据计算为 NC 类计算. 一般而论, 小数据时的 NC 类计算, 可采用高阶多项式数目个处理器, 在低阶对数多项式时间内, 求解几十万个输入的中等大小规模的计算问题 ; 而大数据时的 NC 类计算, 可采用低阶多项式线性或亚线性数目个处理器, 在高阶对数多项式时间内求解数百万以上个输入的大规模计算问题. 本文针对大数据的特征, 以计算复杂性理论为基础, 提出一个大数据并行计算模型. 该模型主要包括 3 方面的内容 : (1) 将多种复杂的数据类型及描述其相似性的距离函数抽象到统一的度量空间, 以期解决大数据的多样性挑战 ; (2) 将大数据在度量空间中按照距离划分, 为后续的并行处理提供条件 ; (3) 以 NC 计算理论为基础, 对大数据问题进行并行处理, 以期解决大数据的大容量和快速率等方面挑战. 本文提出的是一个针对大数据问题的初步并行解决方案, 度量空间并非唯一的大数据抽象表示方法, NC 计算理论也并非唯一的大数据并行计算理论. 后续的工作主要包括如下方面. 首先, 大数据的研究要针对大数据的特性, 提出一般性的应对策略 : 例如, 对于大容量 (volume), 一般可采用面向领域的并行分布式处理系统专用架构 ; 对于快速率 (velocity), 一般应采用在线实时流处理方法, 而不能再局限于常规的离线批处理如 MR 技术 ; 对于多样性 (variety), 一种可行的方法是本文所介绍的大数据统一抽象的度量空间表示方法. 其次, 研究大数据应在大数据的整个生命周期内进行, 即大数据的采集 - 传输 - 存储 - 计算 - 应用. 不同阶段的科学问题可采用不同的技术应对之 : 一般而论, 例如在数据的采集阶段, 可使用 ETL(extraction transformation loading) 技术 ; 在数据传输阶段, 可使用 SDN(software defined network) 技术 ; 在数据存储阶段, 可采用 DAS(directattached storage) 和 SCM(storage class memory) 存储技术 ; 在数据计算阶段, 可采用流计算 (stream computing) 增量计算 (incremental computing) 近似计算 (approximate computing) 压缩计算 (compression computing) 等计算技术 ; 至于应用则应结合具体应用领域行业针对性地解决实际应用问题. 最后, 面对大数据局面, 应该变革思维方法来研究大数据 : 例如在数据获取时, 无法再采用传统的精确采样数据, 而应利用相关事物 ( 事件 ) 的全样数据 ; 在数据分析时, 不能一味追求精确的分析, 而可采用简单粗略的估计方法 ; 在数据解释时, 要从分析因果关系转变为寻找相互关联关系, 知道是什么, 比知道为什么更迫切需要 ; 在数据处理时, 可以暂无理论模型和科学方法, 有简单实用的方法即可, 相信有时候没有严格理论指导, 数据科学照样可以进步! 致谢作者曾和英国爱丁堡大学樊文飞教授香港中文大学华云生教授和上海交通大学陈贵海教授等在大数据的计算理论方面进行了深入的交流和探讨, 对此表示衷心感谢. 568

10 快讯参考文献 1 Zhou B Y, Liu W, Fan C G. Big Data Strategy, Technology, Applications (in Chinese). Beijing: Publishing House of Electronics Industry, 2013 [ 周宝曜, 刘伟, 范承工. 大数据 : 战略技术实践. 北京 : 电子工业出版社, 2013] 2 Tu Z P. The Big Data Revolution (in Chinese). Guilin: Guangxi Normal University Press, 2012 [ 涂子沛. 大数据. 桂林 : 广西师范大学出版社, 2012] 3 Tang X, Li K, Zeng Z, et al. IEEE Trans Computers, 2011, 7: Fan W, Geerts F, Neven F. Making queries tractable on big data with preprocessing. In: Proceeding of the 39th International Conference on Very Large Data Bases (VLDB), Chen G L. Design and Analysis of Parallel Algorithms (in Chinese). Beijing: China Higher Education Press, 2011 [ 陈国良. 并行算法的设计与分析. 北京 : 高等教育出版社, 2011] 6 Xiong J C, Lü J, Tan F Y. Topology (in Chinese). Beijing: China Machine Press, 2013 [ 熊金城, 吕杰, 谭枫, 译. 拓扑学. 北京 : 机械工业出版社, 2013] 7 Chavez E, Navarro G, Baeza-Yates R, et al. ACM Computing Surveys, 2001, 33: Zezula P, Amato G, Dohnal V, et al. Similarity Search: The Metric Space Approach. Heidelberg: Springer, Mao R, Miranker W, Miranker D P. J Discrete Algor, 2012: Benjamin B, Navarro G, Chavez E. Pattern Recogn Lett, 2003, 24: Mao R, Liu S, Xu H L, et al. On data partitioning in tree structure metric-space indexes. In: Proceeding of the 19th International Conference on Database Systems for Advanced Applications (DASFAA2014), Uhlmann J K. Inform Proc Lett, 1991, 40: Yianilos P N. Data structures and algorithms for nearest neighbor search in general metric spaces. In: Proceeding of the Fourth Annual ACM-SIAM Symposium on Discrete algorithms. Soc Industr Appl Math, Ciaccia P, Patella M, Zezula P. M-tree: An efficient access method for similarity search in metric spaces. In: Proceeding of the 23rd International Conference on Very Large Da-ta Bases (VLDB 97), Cook S A. A novel security-driven scheduling algorithm for precedence-constrained tasks in heterogeneous distributed systems. In: Proceeding of the Eleventh Annual ACM Symposium on Theory of Computing, Parallel computing framework for big data CHEN GuoLiang 1,2,3, MAO Rui 1,2,3 & LU KeZhong 1,2,3 1 Guangdong Province Key Laboratory of Popular High Performance Computers, Shenzhen , China; 2 Shenzhen Key Laboratory of Service Computing and Applications, Shenzhen , China; 3 College of Computer Science and Software Engineering, Shenzhen University, Shenzhen , China Big data has received a great deal of attention with respect to its use in research and application in information technology. However, most current efforts focus on systems and applications instead of the theoretical foundation. Based on computational complexity theory, according to the volume, velocity, and variety challenges of big data, we study the computability and computational principles of big data. First, various types of big data can be abstracted into metric space for universal representation to handle the variety challenge. Big data can then be partitioned in metric space according to distance. Finally, NC-class computing theory can be applied to solve big data problems in parallel and handle the volume and velocity challenges. Last of all, from a wider perspective, we propose a processing strategy according to the challenges and innovation of big data research methodology. NC-class computation, metric space, data partitioning, computability doi: /N

11 1950,.,,,., (2 ).,,. Science Bulletin SCI, Academic Search Complete, Chemical Abstracts, Current Contents, Environmental Engineering Abstracts, Environmental Sciences and Pollution Management, Inspec, Pollution Abstracts, Water Resources Abstracts, Zoological Record. 1. : (1) :,, ( 6 ). :,, ( 10 ). (2) : ( 4 ). : ( 7 ). (3) :, (2 ). :, (4 ). : ; (3 ). (4) : (1 ). : (2 ). : (Science Bulletin) (1 ). : (1 ). 2. : csb.scichina.com,.,,. 3., 30.,,. 60,.,.. 4.,, ( ). ( ). 5.. 科学通报编辑部 : 北京市东城区东黄城根北街 16 号 : : csb.scichina.com csb@scichina.org 中国科学杂志社主任安瑞 anrui@scichina.org ( 兼生命科学与医学科学编辑 ) 副主任张莉 zhangli@scichina.org ( 兼地球科学编辑 ) 责任编辑王元火 wyh@scichina.org ( 生命科学与医学科学 ) 李军青 lijunqing@scichina.org ( 物理学 ) 王晶 wangj@scichina.org ( 物理学力学天文学工程科学 ) 智欣 zhixin@scichina.org ( 化学 ) 肖鸣 xiaoming@scichina.org ( 材料科学 ) 本期责任编辑王晶生产编辑程剑侠封面设计胡煜广告部 : ads@scichina.org 销售市场部 : sales@scichina.org

<D2BDC1C6BDA1BFB5CDB6C8DAD7CAB8DFB7E5C2DBCCB3B2CEBBE1C3FBB5A52E786C7378>

<D2BDC1C6BDA1BFB5CDB6C8DAD7CAB8DFB7E5C2DBCCB3B2CEBBE1C3FBB5A52E786C7378> 参会人员名单 Last Name 姓名公司 Tel Fax Bai 柏煜康复之家 8610 8761 4189 8610 8761 4189 Bai 白威久禧道和股权投资管理 ( 天津 ) 有限公司 8610 6506 7108 8610 6506 7108 Bao 包景明通用技术集团投资管理有限公司 8610