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

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

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

最多叶子生成树问题的核化算法2211-2218

摘要：对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为（N＋6）/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O（n2）时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.

基于阈值的概率图可达查询2219-2228

摘要：图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定图的可达查询不能有效地处理不确定性,因此该文研究用概率语义描述的图可达性查询.具体的,该文使用可能世界概率模型定义不确定图（称为概率图）,基于该模型,研究了基于阈值的概率可达查询（T-PR）.首先为避免枚举所有可能世界,给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法,给出3种改进方法,它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计.

GRkNN：空间数据库中组反k最近邻查询2229-2238

摘要：反k最近邻（Reversek-Nearest-Neighbor,RkNN）查询是在k最近邻（k-Nearest-Neighbor,kNN）查询问题的基础上产生的,获得将查询对象作为kNN的数据对象集合,RkNN可以用于评价查询对象的影响力.根据实际应用中需要查询一组对象的RkNN,如评价连锁店或商业区的影响.文中提出了针对空间数据库的组反k最近邻（Group RkNN,GRkNN）的概念,并设计了相关算法.查询点集合是一组邻近的空间对象,计算查询对象的最小覆盖圆,将最小覆盖圆中的对象作为一个整体进行过滤,设计了基于R树的剪枝方法,通过提炼获取了最终的GRkNN结果.针对真实数据集进行的大量实验表明,提出的GRkNN算法的效率明显优于目前最好的RkNN算法.

面向SaaS应用基于键值对模式的多租户索引研究2239-2247

摘要：面向SaaS应用的多租户数据库为满足租户的数据隔离和按需定制的需求,需要提供支持隔离和易于定制的数据存储机制及索引机制.基于键值对存储方式,提出元数据驱动的映射表索引模型,该模型根据租户定制需求,为租户业务数据形成各自的索引元数据,通过元数据驱动实现了索引数据的隔离及定制效果;给出索引的维护策略,根据租户数据访问请求进行索引切片,以逐渐细化的索引切片作为数据访问的基本单位,快速返回租户结果集.实验结果表明,该方案在数据访问分布均衡的情况下,使索引维护及数据访问具有较好的总体性能.

空间网络间的空间关系的表示和推理2248-2257

摘要：空间网络间的空间关系的表示和推理在空间数据库领域具有重要的意义.为了对复杂的空间网络间的空间关系进行定义和区分,首先提出了空间网络间的空间关系的谓词表示和交集模型表示方法,给出了空间网络间的空间关系模型的特征条件式和蕴涵条件式,进一步给出了空间网络间的空间关系的划分定理和推论;系统研究了空间网络间的空间关系的推理方法,针对空间网络间的空间关系推理特点,提出了推理相斥规则和推理蕴涵规则.研究成果为空间网络间的空间关系在空间数据库中的应用奠定了基础,极大地增强了空间数据库处理复杂对象的空间关系的能力.

HV-Recovery：一种闪存数据库的高效恢复方法2258-2266

摘要：和磁盘相比,闪存作为一种新型的存储设备,具有读写速度快、抗震、省电、体积小等优点.因此,当前的研究普遍认为闪存将取代磁盘成为新一代的数据库二级存储设备.但是,由于闪存具有和磁盘不同的一些固有的读取特性,将当前基于磁盘设计的数据库直接移植到闪存上时,并不能充分发挥闪存设备的优越性.在数据库的恢复过程中,由于闪存的异地更新和重写之前先擦除的特性将带来大量高代价的小的随机写,直接使用传统的恢复方法在闪存数据库中就更难以充分利用闪存的优越性.因此,文中提出了一种对闪存中天然存在的数据的历史版本来进行管理和利用的恢复方法HV-recovery,来改进undo恢复的性能.通过和开源数据库Oracle Berkeley DB的比较,实验结果表明HV-recovery是原有的恢复算法性能的2~8倍,充分说明了其优越性.

使用联合链接相似度评估爬取Web资源2267-2280

摘要：如何从Web上获取感兴趣的资源是许多Web研究领域重要的研究内容.目前针对特定领域Web资源的获取,主要采用聚焦爬行策略.但目前的聚焦爬行技术在同时解决高效率爬行和高质量的爬行结果等方面还存在许多问题.文中提出了一种基于联合链接相似度评估的爬行算法,该算法在评估链接的主题相似度时,联合使用了关于链接主题相似度的直接证据和间接证据.直接证据通过计算链接的锚链文本的主题相似度来获得,而间接证据则是通过一个基于Q学习的Web链接图增量学习算法获取.该算法首先利用聚焦爬行过程中得到的结果页面,建立起一个Web链接图.然后通过在线学习Web链接图,获取链接和链接主题相似度之间的映射关系.通过对链接进行多属性特征建模,使得链接评估器能够将当前链接映射到Web链接图的链接空间中,从而获得当前链接的近似主题相似度.在3个主题域上对该算法进行了实验,结果表明,该算法可以显著提高爬行结果的精度和召回率.

XML的结构完整性约束推理2281-2290

摘要：为了有效地优化XML路径表达式查询,给出了一个XML结构完整性约束体系,这个体系全面描述了XML文档中节点或路径之间的结构关系,包括必需性包含、排他性包含、路径蕴涵、路径互斥和路径同现.在此基础上研究了XML结构完整性约束的逻辑蕴涵和一致性问题.文章首先采用约束重写技术将各种约束改写为路径蕴涵约束;然后给出了一组路径蕴涵的推理规则;最后以路径蕴涵闭包为工具证明了推理规则的完备性并给出了XML结构完整性约束的一致性判断方法.

基于Nearest-Biclusters协作过滤技术的效用图结构学习算法2291-2299

摘要：在多议题协商研究中,议题之间的依赖关系增加了协商Agent效用函数的复杂性,从而使得多议题协商变得更加困难.基于效用图的多议题依赖协商模型是体现议题间依赖关系的多议题协商模型.在该协商模型中,协商双方仅需要较少的协商步数就能够找到满足Pareto效率的协商结局.如何有效地学习买方Agent的效用图结构是该协商模型的关键.文中基于Nearest-Biclusters协作过滤技术的思想提出了一种新的效用图结构学习算法（NBCFL算法）.该算法首先利用Nearest-Biclusters协作过滤技术发现买方偏好的局部匹配特性,提取与当前买方Agent类型相同的买方Agent所产生的协商历史记录,然后通过计算各议题间的依赖度学习买方Agent的效用图结构.实验表明在参与协商的买方Agent类型不同的条件下,NBCFL算法比IBCFL算法能更好地学习买方Agent的效用图结构.

基于综合判据的无线Mesh网路由协议2300-2311

摘要：为用户提供高质量、高性能的通信链路是无线Mesh网路由协议所面临的重要挑战,而当前从AdHoc网络沿袭下来的路由协议并不能够满足无线Mesh网的性能要求.文中以OLSR协议为原型,结合跨层优化理论,为基础设施架构的无线Mesh网提出了一种新颖的、基于综合判据的路由协议.该协议通过跨层操作机制综合考虑无线链接的长度及通信效率对链接性能的影响,从而达到优化路由选择的效果.仿真结果表明,所提出的路由协议能够有效地提高网络中分组的递交率,降低端到端的延时,并且能够在一定程度上达到负载均衡的路由效果.

修改客户操作系统优化KVM虚拟机的I/O性能2312-2320

摘要：目前,运行在虚拟机上的客户操作系统（GuestOS）是面向物理机器开发的普通操作系统,其中存在不适应虚拟化环境的因素,影响虚拟机的I/O性能.作者通过测试发现了影响虚拟机I/O性能的一些问题,针对这些问题提出了优化方法：一方面,通过合并客户操作系统中连续的I/O指令,降低虚拟机的时钟中断频率,从而降低环境切换的开销;另一方面,消除客户操作系统中的冗余操作,包括在虚拟化环境下无效的函数、冗余的I/O调度以及虚拟网卡驱动对NAPI的支持,使虚拟机只执行必要的操作,从而提高系统的性能.

支持运行监控的可信软件体系结构设计方法2321-2334

摘要：近年来,软件的可信性成为软件质量的焦点,对软件可信性的分析、度量和应用支撑成为热点问题.对软件实施有效的监控是提升软件可信性的一种重要途径.然而目前的研究工作主要集中在软件编码以及相关技术的实现层,缺乏一套系统的软件体系结构设计方法以指导、支持运行监控的可信软件的分析和设计.通过引入面向侧面的软件体系结构设计方法及其相关概念,文中提出一种支持运行监控的可信软件体系结构设计方法.在支持运行监控的可信软件构造模型TSCM的基础上,利用一种面向侧面的体系结构描述语言AC2-ADL描述具有监控能力的软件体系结构,试图为分析和设计具有监控能力的系统的软件体系结构提供一种有效的解决方案.通过结合网上拍卖系统的案例展示该方法的主要步骤和结果,讨论了研究中存在的问题和进一步的工作.

通过增大边际权重提高基于频谱的错误定位效率2335-2342

摘要：基于频谱的错误定位技术通常利用覆盖信息来求出程序中每条语句的可疑度,并将语句按照可疑度降序排序以寻找错误语句.文中对已有的基于频谱的错误定位算法进行改进,将失败测试用例的边际权重引入到可疑度计算的过程中,即针对某一特定语句,令失败测试用例的权重随着其对该语句覆盖次数的增加而增大.实验结果表明,相对于其它方法,文中提出的方法对错误定位效率有一定的促进作用,即只需检查更少的语句即可找到出错位置.

类选择排序的可逆逻辑综合算法2343-2352

摘要：可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.由于搜索空间随电路规模增长成指数增长,现有的可逆逻辑综合算法虽然能够得到近似最优的解,但是都存在计算时间过长的问题.文中提出了一种类似选择排序的可逆逻辑综合算法,其实质为基于变换规则的合成法.它采用一个无向无权图表示所有可以进行变换的路径,在综合的过程中,采用选择排序思想每次从小到大的选择需要交换的输出项,然后从路径选择图中找到最优的路径进行变换,最终使得函数的输出序列有序即完成综合.此外,文中还对得到的量子电路进行了优化.实验表明,相比其它综合算法,该算法不仅总能获得最优解或近似最优解,而且效率高、易于实现.

SAN-EBON：一种基于结构化对等网的P2P工作流系统节点定位网络2353-2363

摘要：基于P2P的工作流系统符合工作流去中心化的发展趋势.目前,P2P工作流系统主要是基于非结构化P2P网络构建的.然而,非结构化P2P网络提供的泛洪或基于超级节点的中心化发现策略和中心化的负载分配机制无法满足大型P2P工作流系统在动态环境下的需求.因此,在基于非结构化P2P网络构建的工作流系统中,节点发现和任务负载均衡成为制约系统性能的关键因素.文中提出一种新的基于结构化P2P网络的工作流系统节点定位网络——SAN-EBON.该系统采用分层逐步求精的节点发现策略,外层在服务聚类的基础上首次在工作流系统中引入服务定位网络组织服务联盟,构建一种新的多层结构化P2P网络SAN,实现服务的快速发现;内层构建一种新的负载均衡网络EBON,使用基于随机图的增强算法实现服务联盟内部实时的去中心化负载均衡,与SAN结合,从而达到提高发现效率和精度、降低通信带宽的目的.

异构集群系统中安全关键实时应用调度研究2364-2377

摘要：在集群系统中,为有安全需求的实时应用提供安全保障得到了广泛关注,但将实时应用的安全需求与调度算法相结合的研究并不多.文中提出了一种异构集群系统中安全关键实时应用的2阶段调度策略——TPSS.该策略综合考虑了任务的安全需求与时间限制.在TPSS的第1阶段,提出了一种自适应调度算法DSRF,当系统负载较重时,DSRF算法能在保证任务安全需求的基础上,通过降低新到任务和等待队列中任务的安全级别来提高任务的调度成功率.相反,当系统负载较轻时,DSRF算法能在保证系统具有较高调度成功率的基础上充分利用任务在截止期前的空闲时间提高新任务的安全级别.在TPSS的第2阶段,提出了一种新的算法FMSL,用来为所接收任务提供较为公平的安全服务,同时进一步提高了任务的整体安全级别.文中通过大量的模拟实验对TPSS策略与DSRF算法、SAEDF算法和RF算法进行了比较.实验结果表明,TPSS策略优于其它方法,使系统具有较强的安全性与灵活性.

多摄像机监控中基于贝叶斯因果网的人物角色识别2378-2386

摘要：很多传统视觉监控的研究工作集中于行人跟踪、行为和事件检测、步态或人脸识别等,然而角色识别却研究较少.针对多摄像机监控中角色识别的应用问题,该文作者提出了一种基于贝叶斯因果网的角色识别方法.该方法不仅用到了通常的一些人物视觉特征,而且还考虑了时间特征、空间统计特征和一些其它特征.作者将这些特征向量的概率分布参数化,特征向量成员之间的因果关系通过有向无环图的方式来表达,然后通过提取的特征来计算概率以识别人物角色.实验的结果证明了方法的有效性.

一种基于多级弦长函数的傅立叶形状描述子2387-2396

摘要：提出了一种用于形状检索的基于多级弦长函数的傅立叶形状描述子（MCLFD）.它产生于对形状轮廓线的等弧长分割.相对于其它的傅立叶描述子,MCLFD不仅计算非常简单,而且对形状的整体特征和细节信息都能进行很好的描述.作者用MPEG-7的标准轮廓线形状测试集和从野外采集的植物叶片形状库,对MCLFD进行了检索性能测试,并和其它的傅立叶描述子进行了对比,实验结果表明,MCLFD具有更优的检索性能,通过加噪声实验也证明了其鲁棒性.