计算机研究与发展杂志社
分享到:

计算机研究与发展杂志

《计算机研究与发展》杂志在全国影响力巨大,创刊于1958年,公开发行的月刊杂志。创刊以来,办刊质量和水平不断提高,主要栏目设置有:综述、计算机技术、计算机网络、人工智能、计算机软件、计算机应用等。
  • 主管单位:中科院出版委员会
  • 主办单位:中国科学院计算技术研究所
  • 国际刊号:1000-1239
  • 国内刊号:11-1777/TP
  • 出版地方:北京
  • 邮发代号:2-654
  • 创刊时间:1958
  • 发行周期:月刊
  • 期刊开本:A4
  • 复合影响因子:2.65
  • 综合影响因子:1.654
相关期刊
服务介绍

计算机研究与发展 2013年第S2期杂志 文档列表

Hadoop系统性能优化与功能增强综述

摘要:Hadoop已成为大数据关键部件,并获得了越来越多的支持.由于认识到Hadoop的巨大潜力,更多的用户在使用现有Hadoop平台技术的同时,着手研发和优化现有技术,以对Hadoop进行补充.在给出Hadoop系统基本框架的基础上,阐述了MapReduce并行计算框架优化、作业调度优化、HDFS性能优化、HBase性能优化和Hadoop功能增强等研究现状,分析已有技术的优势和不足,并探讨了未来的研究方向.
1-15

第一届CCF大数据学术会议组织机构

摘要:主办单位中国计算机学会承办单位中国计算机学会大数据专家委员会协办单位中国人民大学中国科学院计算技术研究所南京大学大会名誉主席李国杰中国科学院计算技术研究所华云生香港中文大学大会主席李建中哈尔滨工业大学张良杰金蝶国际软件集团程序委员会主席孟小峰中国人民大学金海华中科技大学出版主席靳小龙中国科学院计算技术研究所宣传主席黄宜华南京大学赞助单位
3-3

第一届CCF大数据学术会议程序委员会

摘要:查礼(中国科学院计算技术研究所)陈恩红(中国科学技术大学)陈华钧(浙江大学)陈一昕(华盛顿大学)杜小勇(中国人民大学)高宏(哈尔滨工业大学)高阳(南京大学)郭毅可(英国伦敦帝国理工大学)胡斌(兰州大学)华云生(香港中文大学)季统凯(广东电子工业研究院)金波(公安部第三研究所)李翠平(中国人民大学)李国杰(中国科学院计算技术研究所)李克秋(大连理工大学)李仁发(湖南大学)刘际明(香港浸会大学)刘伟(EMC北京研发中心)刘政(赛仕软件)马华东(北京邮电大学)
4-4

前言

摘要:近年来,大数据已经成为国内外学术界、产业界和政府部门都高度关注的热点话题,在国内外掀起了一个空前的研究热潮.为了促进大数据技术的研究与发展,推动大数据学术的研究和交流、大数据应用与产业的发展以及大数据的信息共享,中国计算机学会决定举办"CCF大数据学术会议".经过近一年时间紧张的筹备工作和会务组织工作,第一届CCF大数据学术会议(CCF Big Data 2013)于2013年12月7—8日北京国家会议中心举行.会议由中国计算机学会主办,中国计算机学会大数据专家委员
5-5

基于帧时隙二进制树的RFID标签识别方法

摘要:无线射频识别(radio frequency identification,RFID)系统中的标签识别速率直接决定了系统性能,设计一个高效的标签防碰撞方法能够有效提升读写器的识别效率,并降低读写器和标签所消耗的能量.在分析已有的两类防碰撞算法性能的基础上,提出了一类融合帧时隙ALOHA思想与二进制树思想的新型防碰撞算法.4种新型算法在算法性能上稳步提升,系统能量消耗也呈递减趋势,特别适合手持式电池供能的读写器.仿真结果表明,自适应帧的二进制防碰撞算法(SA-FBS)在减少碰撞时隙上明显优于传统的防碰撞算法.
16-22

适用于网络大数据的属性基广义签密方案

摘要:网络大数据应用对安全性的需求多样而灵活.属性基广义签密能够根据用户属性来确定接收者,且能根据不同的需求自适应地提供独立的或者复合的机密、不可伪造性,克服了传统公钥密码的瓶颈.提出了一个适用于大数据的属性基广义签密方案,能实现在签密、加密和签名间的自适应转换.方案利用非单调访问结构,支持与、或、非和门限操作,能提供更灵活的访问控制;利用零内积加密方法实现了密文长度固定,在加密模式下为2|G|+nm,在签名模式下为3|G|+nm,在签密模式下为5|G|+nm,与属性数目无关.在标准模型下基于q-DBDHE问题证明了签密及加密模式下的机密性和签密及签名模式下的不可伪造性.
23-29

覆盖网络上基于内容的混合路由方法

摘要:内容?订阅系统是一种完全解耦的基于事件的中间件系统,能独立地仅依赖消息内容实现事件匹配和路由,提供了更细粒度的匹配和更高的透明性.在现有基于内容的路由协议中,订阅路径上的节点需存储所有的订阅以构建路由表,从而通过查询路由表实现事件路由.由于系统的路由计算开销受订阅数目影响,因此无法支持大规模应用.为解决这一问题,提出了一种快速的基于内容的路由协议HCBR(hybrid content-based routing).它采用路标的方式建立路由表,从而避免事件在每个节点都进行基于内容的匹配,极大降低事件匹配开销.实验结果表明,在采用27个节点、订阅数目达到10万级别时,基于HCBR协议的系统节点的吞吐量为原系统的10倍;而当事件传输跳数达到27跳时,基于HCBR协议的系统事件端到端传输平均时间缩短到原系统的1?5.
30-36

NTar:基于网络拓扑的纠删码树型修复方法

摘要:大规模分布式容错存储系统采用纠删码作为数据冗余技术能够比多副本技术以更低的额外存储空间开销获得相同的数据可靠性.然而,基于纠删码的数据冗余技术在修复一个失效编码块时需要从其他节点下载多个编码块,不仅占用了大量网络资源,也严重降低了修复速度.现有的修复方法都没有考虑网络拓扑的影响.为此,提出并实现了一种基于网络拓扑的纠删码树型修复方法 NTar.NTar依据网络拓扑将参与修复的节点组织成网络距离最小的树型结构,缩短修复期间数据的传输距离,从而减少占用的网络资源并缩短修复时间.此外,提出了节点选择算法Optree.Optree可快速地从所有可用节点中选出最优的参与修复的节点组合,并同时生成最优的树型修复结构.实验结果表明,相比于传统的星型修复,NTar可将修复占用的网络资源降低30%~45%,修复时间减少50%~70%.
37-44

二元再生码在分布式存储系统的应用

摘要:分布式存储系统以其高效的可扩展性和高可用性成为存储大数据的主要系统.为了提高可靠性,需要在分布式存储系统中引入冗余.因此如何最优化存储空间、最小化修复带宽和最小化计算复杂度是衡量冗余存储系统效率的关键问题.再生码存储是一类可以达到存储空间与网络修复带宽最佳折中的存储方法,但现有的再生码的构造方法有大量有限域的乘法运算,其高昂的计算复杂度成为用于分布式存储系统中的主要瓶颈.实验结果表明,在保留再生码优势的前提下,采用移位和异或运算取代有限域的乘法运算可以大幅度地降低计算复杂度.创新之处在于提出了二元再生码(binary regenerating codes,BRGC),并给出了构造二元再生码的两类最佳再生码,即最小带宽二元再生码和最小存储二元再生码的方法.通过评估和对比主流的RS码和基于矩阵乘法的再生码,发现BRGC在计算复杂度方面有着明显的优势,在实际海量数据的分布式存储系统中具备更好的应用价值.BRGC在修复和解码性能均优于柯西(Cauchy Reed-Solomon)码.
45-53

基于二元再生码的大数据存储系统研究

摘要:随着信息数据量越来越大,大数据存储的可靠性变得尤为重要,因而需要在存储系统中引入冗余.基于复制的传统策略虽然简单,但其存储效率和系统可靠性均不高.纠删码提供了一种不同于复制策略的有效存储方式,然而,当系统中有文件丢失时,纠删码(如Reed-Solomon,RS)需要较高的通信负载来进行文件修复,而且编解码效率不高.针对RS码的不足,在分布式系统中引入一种新颖的再生码,称为二元再生码(binary regenerating codes,BRGC).在Hadoop分布式存储系统中部署和实施了二元再生码和RS码.实验结果表明,BRGC在编解码效率和修复带宽上均优于RS码.
54-63

一种支持海量数据备份的可扩展分布式重复数据删除系统

摘要:现代信息化社会中,数据的爆炸式增长使得存储和管理数据的成本越来越高,数据备份和恢复的时间越来越长,数据中心的能耗越来越严重.重复数据删除技术在缓解数据的高速增长和节约成本方面有很好的应用前景.然而面对日益增长的海量数据,重复数据删除技术需要在数据路由和指纹查询方面提供高可扩展的支持.对于数据路由,提出了基于分布式布隆过滤器(Bloom Filter)的有状态数据路由技术:拆分Bloom Filter并将其分布于多节点并发管理,可以在提高数据路由的扩展性同时降低其通信开销.对于去重节点内的指纹查询,提出了基于取样机制的指纹查询优化方法:通过可扩展Hash结构组织海量取样指纹信息,并根据取样指纹的时间局部性原理对指纹缓存进行管理.为了对研究工作进行评价,设计并实现了分布式重复数据删除系统3D-deduper(distributed data deduplication system),并进行了数据路由和去重性能相关的测试.实验结果表明,基于分布式布隆过滤器的数据路由技术能够使得分布式重复数据删除系统维持与单节点重复数据删除系统相当的去重率,波动低于5%.在取样查询方面,数据去重率在取样率为1?32时仍能达到非取样重复数据删除系统数据去重率的95%以上.在去重性能方面,单节点去重带宽最高可达到200MBps.在节点扩展时,去重带宽仍能保持近似线性的扩展性.
64-70

基于释放和重构的科学工作流数据布局策略

摘要:科学工作流是典型的大数据应用,每个任务涉及的数据体量大,分布式环境下移动的网络代价高,良好的数据布局策略对于降低跨数据中心的传输代价、提高科学工作流运行效率至关重要.随着大数据时代来临,科学工作流计算任务涉及到的数据集和数据存储节点增多,使得求解数据布局最优方案变得更加困难.使用传统数据布局策略往往只能得到局部最优方案.为此,提出一种基于释放和重构的数据布局策略,使得在超大规模的解空间中尽快找到更加接近全局最优的数据布局方案.策略首先基于前期研究成果产生初始解,然后通过解的局部释放和重构,对解空间的不同邻域进行搜索,不断提高解的质量.通过实验验证并与传统方法比较,结果显示该数据布局方案数据传输代价更小,性能更好.
71-76

MapReduce上基于抽样的数据划分最优化研究

摘要:MapReduce是一个目前应用广泛的并行计算框架,如何解决Reduce节点的负载平衡问题是MapReduce程序执行效率的一个重要研究方向.基于抽样的划分是一种比较有效的数据划分方法,为了使得抽样方法发挥最大程度的效益,研究了抽样效果与其重要影响因素之间的定量关系,并给出了相关理论及其证明推导,同时通过实验进一步验证了理论的正确性.基于研究的结果,可以在给定MapReduce环境中,通过分析数据特征,找到最优抽样样本规模,从而通过尽可能小的抽样代价来得到满足要求的数据划分.通过将研究成果应用在改进的Terasort算法上,以实例验证了其在MapRedece平台上的实际意义.
77-84

PHCC:一种处理稀疏变化的封闭数据立方体算法

摘要:完全数据立方体是一种需要在数据集上对属性列进行上卷聚集运算的复杂模型,而封闭数据立方体是一种对应的高效压缩模型.近年来海量数据管理系统的发展使得在大数据上进行数据立方体的计算成为可能,但是大数据环境中的数据可能稀疏也可能密集,因此,要求在不同的数据稀疏程度下算法都要有稳定的表现.面对这样的要求,提出了一种基于大数据环境的封闭数据立方体并行化方法,首先通过构造2种树结构进行本地封闭数据子立方体的构造,然后利用位运算的方式在遍历树结构的同时进行封闭数据立方体的判断和聚集运算,最后经过合并得到查询的最终结果.并且通过在大数据中进行对比实验证明混合并行封闭数据立方体(parallel hybrid closed cubing,PHCC)算法能够满足在稀疏数据变化的数据中进行稳定聚集运算的条件.
85-93

StepMatch:一种基于BSP计算模型的SPARQL基本图模式匹配算法

摘要:随着语义网的发展,越来越多的数据通过资源描述框架(resource description framework,RDF)格式出来.目前有很多研究使用MapReduce计算模型处理大规模RDF数据,将SPARQL查询拆分成多步迭代.对于更适合使用消息传递模型来解决的图计算问题,MapReduce并非是最佳的选择.StepMatch算法基于整体同步并行(bulk synchronous parallel,BSP)计算模型,能有效解决SPARQL的基本图模式匹配查询.StepMatch是一个面向顶点的算法,RDF图中每一个顶点都被视为一个计算单元,顶点可以执行计算并向其他顶点发送消息.对于一个给定的SPARQL查询,StepMatch算法的超步数量与SPARQL查询包含的子句数目相等.最后,实现了StepMatch算法,并在合成的LUBM(Lehigh University Benchmark)数据集和真实的DBpedia数据集上进行了性能实验.
94-102

一种基于Hadoop的语义大数据分布式推理框架

摘要:随着语义万维网(sematic Web)和关联数据集项目(linked data project)的不断发展,各领域的语义数据正在大规模扩增.同时,这些大规模语义数据之间存在着复杂的语义关联性,这些关联信息的挖掘对于研究者来说有着重要的意义.为解决传统推理引擎在进行大规模语义数据推理时存在的计算性能和可扩展性不足等问题,提出了一种基于Hadoop的语义大数据分布式推理框架,并且设计了相应的基于属性链(property chain)的原型推理系统来高效地发现海量语义数据中潜在的有价值的信息.实验主要关注于医疗和生命科学领域各本体之间的语义关联发现,实验结果表明,该推理系统取得了良好的性能———扩展性以及准确性.
103-113

基于改进DPhyp算法的Impala查询优化

摘要:针对目前基于动态规划查询超图(dynamic programming hypergraphs,DPhyp)优化SQL查询算法产生指数运行时间、传统代价模型难以直接适用于Impala大数据实时查询系统等问题,提出基于改进DPhyp算法的Impala查询优化方法.首先,构建满足左线性树的搜索策略,缩小整个执行计划的搜索空间;接着,综合考虑数据移动代价及Hash join算法运行等关键因素,结合提出的代价模型,生成最佳的join顺序;最后,在生成的join顺序基础上构建执行计划,执行后返回最终查询结果.大量实验结果表明,改进的DPhyp算法与DPhyp生成的join顺序一致,且前者算法运行效率比后者要快近一倍.另外,改进的DPhyp算法结合提出的代价模型,比原始的Impala查询响应时间平均减少67%~80%.
114-120

海量多版本文档的加权持久性top-k检索

摘要:提出并研究了针对海量多版本文档的加权持久性top-k检索问题.加权持久性top-k检索能够返回在一个限定时间区间内与查询关键词组持续相关的k个结果,并且考虑不同时间区间有不同的权重.针对这一问题,把现有时空查询和针对多版本文档查询的方法进行扩展,使其支持加权持久性top-k检索问题,并分析总结了该方法的缺点,进而又提出了一种新的基于时间区间窗口的算法.基于时间区间窗口的算法能够支持多种经典top-k算法并有效地解决加权持久性top-k检索问题.最后使用Wikipedia多版本数据进行了一系列性能试验,对比测试了基于区间窗口的算法和扩展算法.结果表明区间窗口算法在各个测试下的效率和可扩展性明显优于扩展算法.
121-131