计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2009年第11期杂志 文档列表

计算机学报杂志综论

高效时序相似搜索技术2107-2122

摘要：时序相似搜索被认为是将来最有前途的技术之一．然而，时序数据是典型的高维海量数据，如何开发高效算法非常关键．文中概述了时序相似搜索技术的研究现状和进展以及研究的主要内容，讨论了该技术的几个重要应用范例，并对一些典型算法进行了定量分析；然后重点论述了高效时序相似搜索的关键技术，包括边界过滤、三角不等式修剪、多辨析率检索方法、过滤精炼方案等．最后讨论并分析了时序的近似相似搜索技术．上述所有技术通过对比，其正面和反面都被深入分析．最后指出了存在的问题和未来的研究热点和方向．

计算机学报杂志研究论文与技术报告

知识库系统的逻辑基础2123-2129

摘要：针对知识库系统的研究现状和存在的问题，分析了用经典一阶谓词逻辑作为知识库系统逻辑基础的不充分性，根据知识库系统的特点和需求，指出可计算性逻辑既能为知识库系统提供合理的逻辑基础，又能弥补经典逻辑作为知识库系统逻辑基础的不足．并在此基础上用证明论方法，建立了一个基于可计算性逻辑的完备子集CL4的知识库系统的公理系统，显示出易于表达、操作简单的特点．

标准模型下可证安全的基于身份的高效签名方案2130-2136

摘要：基于身份的公钥密码体制克服了传统公钥密码体制所带来的公钥证书存储和管理开销问题；目前大多数基于身份的数字签名方案的安全性是基于随机预言模型进行证明，但随机预言机的实现方式可能会导致方案的不安全，如Hash函数，往往返回的结果并不是随机的．文中提出一种安全、高效的基于身份的签名方案，并且在标准模型下证明该方案对自适应选择消息攻击是存在不可伪造的，方案的安全性可规约为CDH困难假定．与现有的标准模型下安全的基于身份的签名方案相比，方案的通信代价更小，执行效率更高．

求解车间调度问题的自适应混合粒子群算法2137-2146

摘要：针对最小完工时间的流水车间作业调度问题，提出了一种自适应混合粒子群进化算法——AHPSO，将遗传操作有效地结合到粒子群算法中．定义了粒子相似度及粒子能量，粒子相似度阈值随迭代次数动态自适应变化，而粒子能量阈值与群体进化程度及其自身进化速度相关．此外，针对算法运行后期进化速度慢的缺点，提出了一种基于邻域的随机贪心策略进一步提高算法的性能．最后将此算法在不同规模的实例上进行了测试，并与其他几种具有代表性的算法进行了比较，实验结果表明，无论是在求解质量还是稳定性方面都优于其他几种算法，并且能够有效求解大规模车间作业问题．

求解三维装箱问题的混合模拟退火算法2147-2156

摘要：提出了一个高效求解三维装箱问题（Three Dimensional Container Loading Problem 3D—CLP）的混合模拟退火算法．三维装箱问题要求装载给定箱子集合的一个子集到容器中，使得被装载的箱子总体积最大．文中介绍的混合模拟退火算法基于三个重要算法：（1）复合块生成算法，与传统算法不同的是文中提出的复合块不只包含单一种类的箱子，而是可以在一定的限制条件下包含任意种类的箱子．（2）基础启发式算法，该算法基于块装载，可以按照指定装载序列生成放置方案．（3）模拟退火算法，以复合块生成和基础启发式算法为基础，将装载序列作为可行放置方案的编码，在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解．文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试．实验结果表明，混合模拟退火算法的填充率超过了目前已知的优秀算法．

LU分解在Godson—Tv1众核体系结构上的并行化研究2157-2167

摘要：随着集成电路工艺的发展，众核体系结构成为人们日益关注的计算平台．LU分解是科学和工程计算中被广泛使用的核心算法之一，尽管在传统的并行体系结构上已有大量的并行化研究工作，但是结合新型众核体系结构特征的工作还不多．文章从负载均衡、延迟容忍和性能分析模型3个方面系统研究了LU分解在众核体系结构上的并行化问题．该文的贡献在于：首先，针对二维卷帘负载分配方案难以达到良好负载均衡的缺点，提出一种新的“之”字形分配方案，实验表明不经任何优化的情况下性能比前者提高20％，优化后达到了40％；其次，提出了一个性能加速比的分析模型，并用实验定量研究了实测性能加速比和理论值之间的差距，发现在合理利用片上存储优化访存延迟，并恰当选择矩阵分块参数的情况下．实测加速效果能比较接近理论值；通过实验还证明实测性能难以达到理论预测值的两个主要原因：访存带宽有限和片上网络的资源竞争．

基于位宽控制提高SIMD架构并行度的优化算法2168-2177

摘要：随着SIMD功能单元作为多媒体加速部件的广泛应用，如何有效利用这一构架优化应用程序成为编译优化研究的热点．目前典型的SIMD结构为同一操作对不同的数据位宽提供了不同的指令版本，随着操作数位宽的增加，对应的SIMD指令可同时完成的操作个数也随之降低．因此，如何有效识别操作数的有效位宽，对提高优化过程中SIMD指令内操作的并行度将产生至关重要的影响．文中针对SIMD优化面临的并行度问题，提出了一种优化算法，该算法在对操作数的有效位进行分析的基础上，进行溢出控制，从而减少操作数对宽位宽数据类型的依赖．实验数据表明，该算法可以有效提高多媒体程序优化的并行度，对多媒体程序获得较好的加速效果．

有向图并行计算中一种新的结点调度算法2178-2186

摘要：在基于有向图的并行计算中，给定图剖分后，如何设计结点调度方案使得并行执行时间最短，是典型的NP完全问题．针对此问题，文中提出一种新的基于顺逆交替迭代技术的启发式调度算法，并给出该算法的并行实现．严格的理论推导证明，新算法在一定的假设条件下，从任何初始调度方案出发，均可以单调收敛．在数百个处理器上的并行数值实验表明，与常用的调度算法相比，新算法可在付出很少的开销代价下显著提高整体并行效率．

基于反馈机制的网格动态授权新模型2187-2199

摘要：网格现有的授权系统存在静态性问题，表现为没有提供机制来反馈用户对授予的权限的使用情况．当一个本来可信的用户或服务变成不可信时，授权系统不能及时发现，对其权限进行调整可能导致恶意用户对网格系统的破坏．因此，在授权系统中建立反馈机制，根据用户的行为动态地调整用户角色，对于网格系统的安全具有重大意义．文中分析了网格中现有的授权系统及信任模型的特点，指出它们存在的不足．在此基础上提出一种基于反馈机制的动态授权新模型，很好地解决了现有授权系统的静态性的缺点．该模型是对CAS授权系统的改进，增加了反馈机制和信任度计算机制．其中，信任度计算机制中提出的基于行为的分层信任新模型较以往的信任模型相比，使用服务权值来区分重要服务和普通服务，从而保护了网格中的重要服务并且能有效地抑制恶意节点的行为；文中提出了一种新的更加精确地计算域间推荐信任度的方法，从而解决了不诚实反馈的问题．反馈机制则利用基于行为分层信任模型给出的用户信任度的变化，实现了根据用户的行为动态调整他的角色．文中还设计了三组模型实验，分别验证新模型的特点、对网格中恶意实体行为的抑制情况，从不同的角度对模型进行了实验，对基于行为的分层信任模型对行为的敏感性、收敛性、有效性及合理性加以了证明．

面向更新密集型应用的内存数据库高效检查点技术2200-2210

摘要：面向更新密集型应用的内存数据库系统，其检查点技术应符合几个关键的要求，包括检查点操作对正常事务处理的干扰尽可能小、能够处理存取倾斜状况、支持数据库系统的快速恢复、提供恢复过程中的系统可用性等．该文提出一种事务一致的分区检查点技术，采用基于元组的动态多版本并发控制机制，避免了读写事务的加锁冲突，提高系统吞吐能力；检查点操作以只读事务形式实现，在多版本并发控制下，避免检查点操作对正常事务处理的堵塞；由于检查点文件是事务一致的，只需要记录事务的Redo日志信息，在系统恢复过程中，只需要对日志文件进行一遍扫描处理，加快恢复过程；基于优先级的数据分区装载和恢复，使得恢复过程中新事务的数据存取请求迅速得到满足，保证了恢复过程中的系统可用性．由于采用两级版本管理机制以及动态版本共享技术，多版本管理的空间开销降低到可以接受的水平．实验结果表明，文中提出的检查点技术方案获得比模糊检查点技术高27％的系统吞吐量，同时版本管理的空间开销在可接受的范围之内，满足高性能应用的要求．

内积能量与边缘检测2211-2220

摘要：提出了一种新型的边缘检测算子——基于内积能量的边缘检测算子．在基于内积能量的边缘检测算子中，内积能量在增强图像边缘的同时能够有效地抑制图像中的噪声和细节，因而它能较好地解决传统边缘检测算子的噪音抑制和边缘定位精度之间的矛盾．实验结果表明：与经典的Canny边缘检测算子相比。在具有相当边缘定位精度的条件下，基于内积能量的边缘检测算子对图像噪音和细节具有更强的抑制能力．此外，它还具有对参数调节不敏感的优良性质．

用兴趣点凸包和SVM加权反馈实现图像检索2221-2228

摘要：针对采用环状颜色直方图的图像检索方法存在的不足，提出一种基于兴趣点凸包的图像特征提取方法，通过对用小波变换检测出的兴趣点递归求出它们的凸包，并将每个凸包上的兴趣点按一定的算法安插在相应的桶内，对每个桶求出颜色直方图，利用桶与桶之间的相似度定义两幅图像的相似度．这种特征提取方法可有效抑制兴趣点集合中出现游离兴趣点的情况，结合基于兴趣点的空间离散度和Gabor小波纹理等特征实现图像检索，可有效提高图像检索精度．最后，提出一种新的相关反馈方法，通过利用支持向量机分类结果设置权值来改进移动查询点相关反馈方法．实际图像数据库上的实验表明，引入这种反馈方法后可将图像检索的查准率提高20％左右，查全率提高10％左右．

基于非下采样Contourlet的多传感器图像自适应融合2229-2238

摘要：提出了一种基于非下采样Contourlet变换的多传感器图像自适应融合方法，采用黄金分割法搜索最优的低频融合权值，自适应地对多传感器图像的低频子带系数进行融合．非下采样Contourlet变换是一种新的图像多尺度、多方向的表示方法，适合表达具有丰富细节信息及方向信息的图像，且该变换具有平移不变性，可以避免一般方法对融合图像引入的振铃效应，它的高频方向子带捕获了多传感器图像的显著特征，文中采用同一尺度下方向子带信息和取大的规则对高频系数进行融合．实验结果表明，与基于拉普拉斯塔、小波、平稳小波和Contourlet变换的方法比较，文中所提出的方法可以获得较好的融合效果．

计算机学报杂志短文

一种新的适用于广播监视的安全视频水印算法2239-2246

摘要：在广播监视应用中，需要对视频片段进行认证．使用三维离散小波变换和中值量化方法，提出一种新的利用密钥生成鲁棒视频散列的算法．提出的散列算法对于视频编辑以及有损压缩都具有很好的鲁棒性．并在此基础上提出一种适用于广播监视的安全视频水印方案．该方案利用生成的散列值和版权标识形成待嵌入的水印信息，以实现对视频片段的认证．理论分析和实验结果表明，提出的算法具有较高的安全性和鲁棒性．

一个新的图像单幅可视隐藏方案2247-2251

摘要：作为一种数字水印的技术方法，提出了一种新的单幅图像可视隐藏方案．在该方案中，仅使用一幅加密图便能可视恢复密图，加密图本身既是编码又是解码．与已有的基于移位的方案不同，该方案通过加密图逆时针旋转90°后和自身的叠加来恢复原图．给出了实现单幅图像可视隐藏的新方案的设计方法，对方案的性能进行了分析，并且指出新方案具有较好的抗压缩性、抗破损性、抗放缩性，且能充分利用密图的容量．

基于颜色和纹理信息的快速前景提取方法2252-2259

摘要：近年来，研究者们提出了许多算法来处理前景提取和图像抽取问题．然而，这些算法存在许多共同缺点：需要三元图作为输入、计算时间过长、大部分算法仅仅使用颜色信息等等．在这篇文章里，作者提出了一种新的快速多层次前景提取方法．首先，应用一种改进的多层次图分割算法，将输入图像粗略地分割为前景和背景两个部分．然后，使用信念传播算法（belief propagation）估计前景／背景交界处像素的不透明度．不同于通常的信念传播算法，在平滑项和颜色项之外，作者通过构造灰度共生矩阵引入了纹理信息．鉴于数码相机图像的分辨率仍在持续快速增长，作者提出的多层次图分割算法可以在加速上述计算过程的同时，获得可以和当前许多算法相媲美的局部最优解．实验结果证明文中所提出的算法对于大尺寸图像尤其有效．

基于混合线性模型的图像去噪2260-2264

摘要：现有的图像去噪算法大多假设图像为分段平滑信号，通过滤除图像中的振动分量达到去噪的效果．如果将这类方法应用于纹理图像，则会导致图像细节信息的损失．该文针对保留图像细节的问题，提出了基于混合线性模型的去噪方法．新方法不假设图像分段平滑，仅假设图像具有自相似性，利用图像的相似性区分图像信号与噪声．文中使用统计学习的方法对图像区域进行聚类，并得到图像主成份，以主成份作为信号分量重组图像，从而对纹理图像取得很好的去噪效果．

龙芯2号处理器的同时多线程设计2265-2273

摘要：提出了适合龙芯2号处理器的同时多线程处理器模型，并介绍了具体的微体系结构设计以及相应的Linux操作系统的实现方案．通过在设计的龙芯2号同时多线程处理器上启动Linux操作系统，并运行应用程序，例如SPEC CPU2000，进行性能评测．结果表明，龙芯2号同时多线程处理器通过挖掘线程级并行性，将龙芯2号处理器的性能提高了31．1％．