计算机学报杂志社
分享到:
《计算机学报》杂志在全国影响力巨大,创刊于1978年,公开发行的月刊杂志。创刊以来,办刊质量和水平不断提高,主要栏目设置有:研究论文与技术报告、短文、学术通信、学术活动、中国计算机学会学术动态等。
  • 主管单位:中国科学院
  • 主办单位:中国计算机学会;中国科学院计算技术研究所
  • 国际刊号:0254-4164
  • 国内刊号:11-1826/TP
  • 出版地方:北京
  • 邮发代号:2-833
  • 创刊时间:1978
  • 发行周期:月刊
  • 期刊开本:A4
  • 复合影响因子:3.18
  • 综合影响因子:2.580
相关期刊
服务介绍

计算机学报 2012年第12期杂志 文档列表

计算机学报杂志综论

复杂文本网数据的主题建模进展

摘要:文中介绍了大规模文本网数据的主题建模研究的特点和近年来的重要进展.主题建模方法吸引了世界范围的广泛兴趣,并且促进了许多重要的数据挖掘、计算机视觉和计算生物应用系统的发展,包括文本自动摘要、信息检索、信息推荐、主题检测和追踪、自然场景理解、人体动作识别以及微阵列基因表达分析等.文中重点介绍文本网数据的4个主要特点以及对应的主题模型.文本网数据含有动态、高阶、多通路及分布式的结构,而之前的主题模型仅对部分的结构进行建模.而文中讨论了在三维马尔可夫模型的框架下统一对文本网数据的4个结构特点进行建模,并分析了结合三维马尔可夫模型和二型模糊系统对分布式单词计算和主题建模应用的可能性.除了对文本网数据的结构建模之外,还讨论了一些对三维马尔可夫模型能量最小化的机器学习算法.
2431-2445

布料动画方法研究进展及问题

摘要:布料动画技术是计算机动画领域的热点研究方向,可以广泛应用于数字娱乐、三维游戏以及服装工业等多个领域.布料动画技术最为核心的研究问题是布料动画方法,其旨在构建动画模型,驱动布料产生形变,继而生成连续动画.好的布料动画方法是保证富有动感、且视觉逼真的布料动画生成的根本因素.近年,由于实际应用对布料动画模拟逼真性与实时性等需求的迫切增长,许多新技术和新方法应运而生.文中重点围绕布料动画方法的研究进展进行介绍.首先在对国内外研究工作进行全面分析与总结的基础上,根据生成布料动画所采用的技术不同,将其分为几何法、物理法、混合法、自适应网格法、约束动力学法、实例数据法、并行计算法等7大类,详细阐述每一类方法的原理及特点,并重点介绍每类方法近期出现的新工作;其次,对各类方法的优缺点及产业影响进行对照分析;最后,结合实际应用需求,针对目前工作中存在的不足,提出一些可继续深入研究的问题,并指出布料动画技术研究与应用的前景方向.
2446-2458

XML关键字查询处理研究

摘要:关键字查询作为一种有效的信息检索手段,一直以来都是XML数据管理领域研究的热点问题,每年均有大量最新研究成果出现在各种顶级会议和期刊上.针对众多国内外研究者在XML关键字查询领域所作出的创新性工作,该文以XML关键字查询处理系统为框架来组织现有工作,重点分析和比较了查询生成、语义定义、排序机制、查询算法及结果展示等5个关键技术点所涉及的代表性工作的特点,并结合最新的应用需求从有效性和高效性的角度归纳出XML关键字查询技术后续研究面临的问题和挑战.
2459-2478
计算机学报杂志研究论文

群体随机运动下可信联盟的约束演化方程及其概率计算

摘要:联盟合作是自组织网络中一个热点研究领域,Agent间的信息具有不确定性、不完全性和局部性等特征,个体Agent节点出于风险的考虑会在不同的联盟间迁移,因此在联盟的演化研究中需要融入信任因素.文中研究群体随机运动环境下可信联盟的演化机制,从微观和宏观上对个体Agent运动行为和联盟规模结构进行分析,将基于历史交互的信任信息融入演化过程中,提出演化规则,界定了演化稳定性的标准.从微分动力系统的视角建立约束演化方程并通过概率计算对方程进行转化求解,分析了演化计算的复杂性,并进一步分析了Agent异构性和局部信息感知对联盟演化的影响.最后通过模拟实验对演化进行讨论,并从信息论角度对联盟的有序性进行分析,讨论信任对演化过程的影响,刻画了群体随机活动中可信联盟的构建与演化过程.
2479-2491

一种保持结点紧凑的虚拟网络映射方法

摘要:虚拟网络映射是网络虚拟化中最基本的问题之一.虚拟网络映射可分解成结点映射和链路映射两个阶段,之前的研究更加侧重于链路映射,对结点映射只采取简单的方式进行,不利于资源利用率的提高.之前的结点映射方法有两个主要问题:(1)优先占用带宽较大的结点,不利于资源的合理配置;(2)将结点映射与链路映射完全分隔处理,逻辑相邻的虚拟结点可能映射到分散的物理结点上,致使虚拟链路占用更多的网络资源.文中提出一种结点紧凑的虚拟网络映射方法,将所有符合条件的物理结点都作为虚拟结点的候选宿主,扩大了宿主的选择空间,有利于资源的合理配置;同时选择那些分布紧凑的结点作宿主,将相邻的虚拟结点映射到邻近的物理结点之上,减少虚拟链路对网络资源的占用.实验结果表明:文中方法可以提高资源的利用率,并显著地提高了虚拟网络请求的接受率.
2492-2504

面向InfiniBand数据中心的区别化传输层带宽划分机制

摘要:数据中心已经成为提供资源和服务的重要平台,在虚拟化基础上部署的多种应用对网络性能提出了更加严格和多样化的需求,从而促使改变以传统TCP为中心的传输层结构.文中从数据中心环境的特性出发,归纳得到改进数据中心网络传输层设计的3个方向.在深入剖析InfiniBand(IB)互联传输优化相关技术的基础上,文中提出了一种更好的支持网络可感知、应用可区分、策略可管理的数据中心网络新型传输控制模型.文中对IB传输控制核心的1B拥塞控制算法及其参数进行了深入的分析,证明了在流级通过区别化的拥塞控制参数配置能够实现成比例的带宽划分.最后,在真实系统中的实验验证了通过参数的动态配置能够保持租户级的公平带宽共享,更好支持云数据中心的带宽隔离需求.
2505-2514

一种基于P2P流量规划的网络资源可重构分配方法

摘要:现有IP网络的无连接性和网络资源的松散管理结构使得网络流量存在全局范围内的分布不均情况,造成网络资源利用率低并且对运营商的一些突发的Qos需求很难做到快速响应.具备网络资源集中式管理特征的可重构网络虽然弥补了这一不足,但对特定业务的流量优化能力以及按需合理重构网络资源的能力不足,使得可重构网络资源分配及QoS保障技术仍有待进一步提高,尤其是占据网络流量主体的P2P业务流量和突发性高优先级Qos保障.当前的P2P优化以及流量工程技术不但自身存在不完善,并且也不能高效地直接适用于可重构网络环境中.因此,文中站在网络资源全局统筹的角度,提出了一种应用于可重构网络环境中的、基于P2P流量规划的网络资源动态可重构技术,使得可重构网络的资源管理机制有能力对全网P2P流量进行优化调度,尤其是能够在网络资源不足的情况下,通过调整P2P流量,释放指定网络资源以响应突发高优先级需求.通过仿真验证可见,以P2P流量规划的手段对全网资源进行全局规划、动态重构,形成弹性的可重构网络环境中,网络流量负担、P2P节点出、入度等多方面均有较大幅度提升,从而赋予了运营商一种对各种优先级业务的规划手段.
2515-2527

基于关联挖掘的软件错误定位方法

摘要:基于覆盖率的错误定位(Coverage Based Fault Localization,CBFI。)方法旨在通过分析程序执行的结果预测错误信息,是一种行之有效的错误定位方法.然而,CBFI。方法中代码覆盖率的独立统计忽略了程序内存在的复杂控制依赖和数据依赖,从而忽视了语句间的语义关系,影响错误定位的准确性.该文借助实例重点分析了基于代码覆盖率所得到的错误可疑度与错误代码的表现关系,指出现有CBFI.方法的不足是片面地将基于覆盖率的错误可疑度直接作为错误代码判定的依据;提出程序失效规则及基于覆盖向量的覆盖信息分析模型,并在此模型基础之上,指出高可疑代码与错误代码在执行路径上的覆盖一致性,进而提出用以挖掘与高可疑代码相关联的错误代码的频繁集求解方法.以SIR基准程序为实验对象建立的受控实验结果表明,相比之前的研究,文中方法在…一定程度上能够改进错误定位结果.
2528-2540

基于One-test-at-a-time策略的可变力度组合测试用例生成方法

摘要:组合测试可以有效地检测软件系统中由各个因素间交互作用所引发的软件故障.但传统的组合测试方法对系统中各因素之间的实际交互关系考虑不足,难以有效处理交互力度不统一的情况,进而可能导致测试用例的冗余和检错能力的降低.针对该问题,应在充分考虑因素间实际交互关系的基础上,使用可变力度组合测试方法,从而实现对于因素间实际交互关系的覆盖.为此,文中针对一种新的可变力度组合测试模型,提出了两种基于one—test-at—a—time策略的可变力度组合测试用例集生成算法.实验表明,相对于已有的具备类似功能的测试用例生成算法和工具,文中提出的算法在测试用例集规模和算法运行时间上均具备一定优势,并可适用于固定力度组合测试、可变力度组合测试等不同测试模型.
2541-2552

求解三维装箱问题的多层启发式搜索算法

摘要:文中提出了一个高效求解三维装箱问题的多层启发式搜索算法.该算法基于块装载的思想,按照块选择算法确定每个阶段采用的块,然后以一种固定的装载方式装载块,直到无法继续装载.文中的主要贡献在于发展了一个有效的复合块生成算法,特别的,提出了基于多层搜索的块选择算法,该算法用多层搜索来评价可行块,然后选择最合适的块进行装载.对1500个三维装箱问题测试数据的计算结果表明,提出的算法几乎在所有测试数据上的填充率都超过了目前已知的优秀算法.
2553-2561

低代价锁步EDDI:处理器瞬时故障检测机制

摘要:随着ULSI工艺步入深亚微米时代,处理器内部组合逻辑的瞬时故障敏感性迅速提高,文中在设计初期将硬件寄存器纠检错能力和系统软件检错能力纳入考虑,兼顾处理器内组合逻辑、时序逻辑两类部件,设计应用级“低代价锁步EDDI(Error Detectionby Duplicated Instructions)”机制.创新如下:(1)提出基于概率论的故障漏检率量化估计方法,为纠检错与性能折中进行指导.以往的应用级检错机制在设计过程中并没有考虑到下层操作系统的检错能力,这会造成可靠性估计不足而带来性能损失.文中依照指令流经的部件将故障划分为不同子类,并将操作系统纳入考虑,提出基于概率论的故障漏检率量化估计方法,理论估计与故障注入结果拟合良好.(2)低代价锁步EDDl机制,结合硬件纠检错能力,兼顾处理器内组合逻辑和时序逻辑两类部件,大幅降低了性能代价.提出独特的低代价锁步指令复制规则,并通过编译链前端的寄存器分配,大幅减少了寄存器预留数,有效缓解了寄存器压力,降低了访存代价,提高了寄存器的性能.寄存器预留也保证了本机制无需修改编译器传参规则,无需重新编译系统库,提高了通用性.(3)采用单比特故障模型,基于SPARC体系结构,选取处理器中代表性部件:解码(Decoder Unit)单元、地址生成(Address GEN Unit)单元、算逻单元(ALu)进行故障注入,对低代价锁步EDDI实现代价进行详细评测.与全复制EDDI相比,低代价锁步EDDI仅以故障漏检率SDC(Silent Data Corruption)平均升高0.8%的代价,换取了动态执行指令数平均减少36.1%,执行时间平均降低35.2%的性能优势.
2562-2572

一种任意维Line—Sweep计算的数据划分算法

摘要:数据划分是在当前主流高性能计算平台上高效并行化应用程序的关键技术,它包括数据分割和处理机分配两个主要部分.Line—Sweep计算模式被众多科学工程计算核心采用,目前该计算模式的并行化主要采用多重数据划分.多重数据划分能保证各处理机的计算量、访存量和通讯量相等,但在某些情况下也会导致访存量和通讯量过多,因此无法保证性能最优.为解决这一缺陷,文中提出均衡数据划分,进一步放松对数据分割和处理器分配的非本质约束,以利于在计算、访存和通讯这3种开销之间达到最佳平衡.文中给出生成最佳均衡数据划分的算法,它包含3个关键技术:首先建立性能模型,在该模型中均衡数据划分的性能只与数据分割方式有关;接着基于该模型缩减数据分割方式的搜索空间,并以该模型为判据搜索性能最佳的数据分割方式;最后设计处理机分配函数以满足均衡数据划分的条件.均衡数据划分被应用于NPB并行测试包中的SP程序和高分子材料计算程序IAneABC.实验结果表明,当均衡数据划分与多重数据划分的数据分割方式相同时,二者性能基本一致;当两种数据分割方式不同时(对于sP和LineABC,这种情况所占比例分别高达38.7%和37.9%),采用均衡数据划分的SP程序和LineABC程序的并行效率比多重数据划分平均分别高出44.45%和22.15%.
2573-2586

支持频繁位置更新的不确定移动对象索引策略

摘要:移动数据采集和处理技术的迅速发展给研究人员提出了新的应用需求,如何在频繁位置更新应用中索引不确定移动对象的当前及未来位置信息成为当前的研究热点之一.TPu树是针对不确定移动对象的当前及未来位置信息索引的策略,其具有较高的概率域查询效率,但是其采用的传统自顶向下更新算法,存在频繁位置更新效率低下的问题.通过在TPU树上增加一个记录不确定移动对象状态特征的更新备忘录(UM)内存结构,文中提出了一种支持频繁位置更新的不确定移动对象索引策略TPU2M树,并在此基础之上提出了一种改进的基于备忘录(MMBU/I)的更新/插入算法.代价分析和实验仿真表明,采用MMBU/I算法的TPU2M树频繁更新性能大大优于TPU树和ABx树索引,且概率查询性能与传统索引大致相当,因此具有很好的实用价值和广泛的应用前景.
2587-2597

计数布鲁姆过滤器代数运算

摘要:文中探讨计数布鲁姆过滤器的代数运算和集合运算的一致性关系,研究使用计数布鲁姆过滤器代数运算进行集合成员查询的性能.理论分析和实验结果表明,计数布鲁姆过滤器的并、交、补、减、异或运算产生的新过滤器依然保持计数布鲁姆过滤器的特征,支持元素的删除操作,不会出现假阴性,能用于集合并集、交集、补集、差集及对称差的成员查询;当使用两个原始的计数布鲁姆过滤器查询补集、差集及对称差元素时,会存在部分本来属于补集、差集或对称差的元素被判为不属于补集、差集或对称差的问题,而使用计数布鲁姆过滤器代数运算后的过滤器进行补集、差集及对称差成员查询,则不存在上述问题,空间效率能提高一倍,时间效率亦能显著地得到改善.计数布鲁姆过滤器代数运算的使用有利于进一步扩展计数布鲁姆过滤器的应用范围.譬如计数布鲁姆过滤器减运算可用作一种新的集合调和方法,用于分布式系统中大型文件的分发.
2598-2617

给定限界的势结构分组与联盟结构生成

摘要:联盟形成是多Agent系统中的一个关键问题,寻求能极大化联盟值总和的最优联盟结构是NP完全的.Sandholm等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.当实际应用提出最坏情况下的具体限界要求时,如何通过进一步的最小搜索找到一个能保证在最坏情况下其联盟结构值与最优的联盟结构值相距在一个给定的限界内的联盟结构,是个长期以来值得研究而又尚未解决的问题.文中深刻分析了不同的分组方法对需要搜索的势结构数的影响,针对给定限界,在最坏情况下提出一种新的分组方法和一个新的联盟结构生成算法,使需要搜索的势结构数和联盟结构数比已有的算法都大大减少.
2618-2624

三部图张量分解标签推荐算法

摘要:三部图作为社会标签系统的表示方法,虽然可以简化标签系统元素间关系的表达,但也丢失了部分元素间的相关信息,而且不能有效处理标签系统中具有大量稀疏值和缺失值的数据.基于以上问题,文中提出了基于三部图的三维张量分解推荐算法(TTD算法).首先分析三部图元素间可能丢失的信息,通过定义以三部图为基础的低阶张量分解模型,对高阶稀疏数据进行分析.该模型不仅包含三部图所表达的系统信息,同时还表达了三部图所丢失的元素间相互信息;在此基础上,利用缺失值处理,进行社会标签系统中的标签推荐预测.通过模型对比实验以及标签预测实验,表明TTD模型所揭示的社会标签系统中元素间的相互关系更加全面,同时在进行标签预测时,所得到的预测结果召回率和精确率得到了显著改善.
2625-2632

进化大规模脉冲神经网络的发育方法

摘要:通过自然进化得到的脑包含几十亿的神经元和几万亿的神经连接,并表现出复杂的智能行为.受生物脑进化与发育的启发,研究者给出了进化神经网络的发育编码方法,特点是通过基因重用可在较小的基因空间中进行大规模神经网络的快速搜索.以人工基因组模型为框架描述基因调控网络,用基因表达的动态特性表示细胞命运特化的发育过程,提出了一种进化大规模脉冲神经网络的发育方法.该方法的特点在于可以快速有效地发育生成脉冲神经元、神经连接和突触可塑性.相应的食物采集进化实验突现了以神经驱动的自主智能体的智能行为,并验证了该方法对大规模脉冲神经网络的进化能力.
2633-2644
计算机学报杂志短文

调和聚类-分类方法在电力负荷预测中的应用

摘要:分类和聚类是数据挖掘中两个重要的研究领域,分类需要相关的先验知识,而聚类往往依据某种相似性测度,从数据本身来寻找其内在特征.在电力系统负荷预测过程中,依靠先验知识得到的分类结果与聚类结果之间并不协调.针对这一问题,文中给出了调和矩阵的定义,并在此基础上,提出调和聚类一分类算法,将该方法应用于电力系统负荷预测的样本分类中,实际结果表明,通过文中方法得到的分类结果更加客观和科学,预测结果的可靠性得到了保证.
2645-2651