王立杰 , 李萌 , 蔡斯博 , 李戈 , 谢冰 , 杨芙清
2012, 23(6):1335-1349. DOI: 10.3724/SP.J.1001.2012.04088
摘要:随着Web 服务技术的不断成熟和发展,互联网上出现了大量的公共Web 服务.在使用Web 服务开发软件系统的过程中,其文本描述信息(例如简介和使用说明等)可以帮助服务消费者直观有效地识别和理解Web 服务并加以利用.已有的研究工作大多关注于从Web 服务的WSDL 文件中获取此类信息进行Web 服务的发现或检索,调研发现,互联网上大部分Web 服务的WSDL 文件中普遍缺少甚至没有此类信息.为此,提出一种基于网络信息搜索的从WSDL 文件之外的信息源为Web 服务扩充文本描述信息的方法.从互联网上收集包含目标Web 服务特征标识的相关网页,基于从网页中抽取出的信息片段,利用信息检索技术计算信息片段与目标Web 服务的相关度,并选取相关度较高的文本片段为Web 服务扩充文本描述信息.基于互联网上的真实数据进行的实验,其结果表明,可为约51%的互联网上的Web 服务获取到相关网页,并为这些Web 服务中约88%扩充文本描述信息.收集到的Web 服务及其文本描述信息数据均已公开发布.
2012, 23(6):1350-1367. DOI: 10.3724/SP.J.1001.2012.04051
摘要:在开放的Web 服务环境中,由于无法保证用户使用服务后给出的反馈等级是真实可靠的,导致服务的信誉度评估结果与实际值存在较大偏差,进而服务选择失败率较高.为了克服上述问题,提出了一种用于Web 服务选择的信誉度评估方法.该方法的主要思想是,通过反馈核查、校正和检测这3 个信誉度评估模块对服务的信誉度进行评估.仿真结果表明,所提出的方法不仅有效提高了信誉度评估的客观性,还显著减小了服务选择的偏离度.
2012, 23(6):1368-1381. DOI: 10.3724/SP.J.1001.2012.04072
摘要:当对软件进行修改时,肯定会对软件的其他部分造成一些潜在的影响,从而带来软件的不一致性;如果该修改所带来的影响波及到整个系统,可能就需要考虑其他修改方案来实施该修改.因此在实施修改之前,需要对所提出的修改方案进行修改分析,从而确定是否需要进行修改或者选择什么方案进行修改.基于形式概念分析技术,提出了一种紧凑的面向对象程序中间表示——类与方法依赖格(LoCMD);然后,基于LoCMD,提出了一种修改分析模型,该模型包含了修改实施前一系列软件修改分析活动,包括与修改相关的程序理解、影响分析以及修改评估.实验结果表明了所提出的LoCMD 和修改模型的有效性,从而有助于维护人员对所提出的修改建议做出正确的理解与决策.
2012, 23(6):1382-1396. DOI: 10.3724/SP.J.1001.2012.04078
摘要:随着处理器功耗不断增大,功耗问题逐渐成为高性能计算机系统设计与实现的首要问题.当前,异构系统已成为高性能计算机的发展趋势之一.与传统同构体系结构相比,异构体系结构具有更高的理论峰值性能和能效,但是如何在满足应用性能的条件下充分发掘异构系统的能效优势,仍是一个挑战性问题.通过将应用程序抽象为由串行段和并行段组成的一般程序模型,建立了异构并行系统能耗优化模型.通过分析方法依次给出并行段以及全程序(多程序段)能耗最优时处理器间满足的关系,分别给出了时间约束下能耗最优的处理器频率选择算法.最后,以CPU-GPU 异构系统为平台,通过8 个典型应用程序验证了方法的有效性.
2012, 23(6):1397-1412. DOI: 10.3724/SP.J.1001.2012.04084
摘要:由于传统QoS感知的Web 服务选择方法无法保证服务选择的可靠性和实时性,提出了一种基于云模型的不确定性QoS 感知的Skyline 服务选择方法.该方法首先通过云模型计算QoS 的不确定性,然后采用Skyline 计算提取Web 服务中的Skyline 服务,剔除冗余服务,最后采用混合整数规划在Skyline 服务中进行服务选择.在公共有效数据集和合成数据集上的实验结果表明,所提出的方法能够为用户提供可靠、快速的服务选择.
2012, 23(6):1413-1428. DOI: 10.3724/SP.J.1001.2012.04102
摘要:路径剖析是动态分析的一项重要技术,通过获取和分析程序中各条路径的执行次数,在编译优化、软件调试和测试等诸多方面发挥重要作用.针对现有技术剖析能力不足的情况(即只能或者剖析非循环路径,或者首先界定循环体执行次数的上限、然后对于执行循环体不多于该次数的路径进行剖析),对使用单个探针变量剖析过程内路径的方法进行了改进,提出了全路径剖析PAP 方法,利用探针插装和回溯过程获取路径的执行次数,可以剖析过程内包含任意有限长度的路径;进一步地,针对PAP 方法所需探针数目多于EPP 方法的问题,通过对控制流图中包含的可规约无环子图实施EPP 方法,可以减少PAP 方法所需探针的数目.另外,作为PAP 方法的一个典型应用,还讨论了如何通过在方法调用图中添加返回边,再利用PAP 方法获取方法层次的执行序列的基本思想,满足了某些方法级动态影响分析技术的需要.实验和实例分析表明,PAP 在处理循环路径剖析的问题上是有效的,并有很好的效率.
2012, 23(6):1429-1443. DOI: 10.3724/SP.J.1001.2012.04047
摘要:非形式化仿真模型验证方法易受主观因素的影响且具有不完备性,而传统的形式化模型检验方法由于受到状态空间爆炸问题的影响,很难处理大规模的仿真模型.并行模型检验方法以其完备性、高效性已经在工业界中得到了成功的应用,但是由于涉及到形式化规约、逻辑学以及并行计算等多项技术,应用难度较大.针对上述问题,提出了基于事件图的离散事件仿真模型并行检验方法.该方法首先对事件图在模型同步方面进行了扩展,给出了扩展事件图的形式化定义、语法及语义;然后将扩展事件图模型转换到分布并行验证环境的DVE 模型,成功地将并行模型检验方法应用于仿真模型验证领域.该方法使得仿真人员无须学习新的形式化验证语言就能采用并行模型检验方法对仿真模型进行形式化验证,可降低模型并行验证的难度,从而有效提高模型验证的效率和完备性.实验结果表明了该方法的有效性,有利于扩展并行模型检验方法在仿真领域中的应用.
2012, 23(6):1444-1457. DOI: 10.3724/SP.J.1001.2012.04067
摘要:提出一种扩展双极辩论模型EBAF(extended bipolar argumentation framework).该模型不仅包括攻击和支援两种独立的语义关系,还允许攻击和支援的递归交互,即对攻击和支援关系进行攻击或支援,且递归次数不受限制.围绕该模型的可接受集合的确定问题,首先将该模型中的攻击和支援关系进行分离,得到攻击辩论框架和支援辩论框架;然后将攻击关系和支援关系作为实体,把递归攻击和递归支援转化为关系视角下的攻击和支援.在此基础上,定义了EBAF 的基本语义概念和可接受集合,并给出了可接受集合的确定算法.最后将EBAF 与其他相关辩论模型进行了比较.
2012, 23(6):1458-1471. DOI: 10.3724/SP.J.1001.2012.04071
摘要:为了提高球形分类器的分类性能,受支持向量机和小球体大间隔等方法的启发,提出一种大间隔最小压缩包含球(large margin and minimal reduced enclosing ball,简称LMMREB)学习机,其在Mercer 核诱导的特征空间,通过优化一个最小包含球,以寻求两个同心的分别包含二类模式的压缩包含球,且使二类模式分别与压缩包含球间最小间隔最大化,从而可以同时实现类间间隔和类内内聚性的最大化.分别采用人工数据和实际数据进行实验,结果显示, LMMREB 的分类性能优于或等同于相关方法.
2012, 23(6):1472-1485. DOI: 10.3724/SP.J.1001.2012.04069
摘要:基于实例的机器翻译(example-based machine translation,简称EBMT)使用预处理过的双语例句作为主要翻译资源,通过编辑与待翻译句子匹配的翻译实例来生成译文.在EBMT系统中,翻译实例选择及译文选择对系统性能影响较大.提出利用统计搭配模型来增强EBMT 系统中翻译实例选择及译文选择的能力,提高译文质量.首先,使用单语统计词对齐从单语语料中训练统计搭配模型.然后,利用该模型从3 个方面提高EBMT 的性能:(1) 利用统计搭配模型估计待翻译句子与翻译实例之间的匹配度,从而增强系统的翻译实例选择能力;(2) 通过引入候选译文与上下文之间搭配强度的估计来提高译文选择能力;(3) 使用统计搭配模型检测翻译实例中被替换词的搭配词,同时根据新的替换词及上下文对搭配词进行矫正,进一步提高EBMT系统的译文质量.为了验证所提出的方法,在基于词的EBMT 系统上评价了英汉翻译的译文质量.与基线系统相比,所提出的方法使译文的BLEU 得分提高了4.73~6.48个百分点.在半结构化的EBMT系统上进一步检验了基于统计搭配模型的译文选择方法,从实验结果来看,该方法使译文的BLEU 得分提高了1.82 个百分点.同时,人工评价结果显示,改进后的半结构化EBMT 系统的译文能够表达原文的大部分信息,并且具有较高的流利度.
2012, 23(6):1486-1499. DOI: 10.3724/SP.J.1001.2012.04073
摘要:半监督文档聚类,即利用少量具有监督信息的数据来辅助无监督文档聚类,近几年来逐渐成为机器学习和数据挖掘领域研究的热点问题.由于获取大量监督信息费时费力,因此,国内外学者考虑如何获得少量但对聚类性能提高显著的监督信息.提出一种结合主动学习的半监督文档聚类算法,通过引入成对约束信息指导DBSCAN的聚类过程来提高聚类性能,得到一种半监督文档聚类算法Cons-DBSCAN.通过对约束集中所含信息量的衡量和对DBSCAN 算法本身的分析,提出了一种启发式的主动学习算法,能够选取含信息量大的成对约束集,从而能够更高效地辅助半监督文档聚类.实验结果表明,所提出的算法能够高效地进行文档聚类.通过主动学习算法获得的成对约束集,能够显著地提高聚类性能.并且,算法的性能优于两个代表性的结合主动学习的半监督聚类算法.
2012, 23(6):1500-1516. DOI: 10.3724/SP.J.1001.2012.04074
摘要:网络协议流不平衡环境下,流样本分布的变化对基于机器学习的流量分类器准确性及稳定性有较大的影响.选择合适的机器学习算法以适应网络协议流不平衡环境下的在线流量分类,显得格外重要.为此,首先通过单因子实验设计,验证了C4.5 决策树、贝叶斯核估计(NBK)和支持向量机(SVM)这3 种分类算法统计TCP 连接开始的前4 个数据包足以分类流量.接着,比较了上述3 种分类算法的性能,发现C4.5 决策树的测试时间最短,SVM 分类算法最稳定.然后,将Bagging 算法应用到流量分类中.实验结果表明,Bagging 分类算法的稳定性与SVM 相似,且测试时间与建模时间接近于C4.5 决策树,因此更适于在线分类流量.
林旺群 , 卢风顺 , 丁兆云 , 吴泉源 , 周斌 , 贾焰
2012, 23(6):1517-1530. DOI: 10.3724/SP.J.1001.2012.04076
摘要:提出了一种基于带权图并行分解的层次化社区发现方法,该方法采用图划分的方式定义社区结构,并在这种社区结构之上实现了社会网络社区发现并行算法P-SNCD(parallel social network community discovery).P-SNCD 算法有效地避免了传统的基于“模块度”的社区发现方法倾向于发现相似规模社区的弊端.同时,该算法能够以可扩展的方式,在处理器规模为O(hmn)或O(hn2)的条件下,以并行计算时间复杂度为O(logn)高效地挖掘大规模复杂社会网络中社区密度为h 的社区,其中,n 为社会网络节点数,m 为边数,h 为用户指定的任意社区密度.所提出的算法对用户参数输入要求简单,从而使得算法具有较强的实用性.充分的实验数据验证了所提出算法的精确性和高效性.
2012, 23(6):1531-1541. DOI: 10.3724/SP.J.1001.2012.04090
摘要:CP-nets 是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点.然而,任意二值CP-nets 上的强占优算法还没有给出,CP-nets 可表示的偏好的完备性还无人研究,CP-nets 所能表示的偏好是否一致也还未彻底解决.基于CP-nets 上的强占优运算研究CP-nets 的完备性和一致性.首先,通过构造CP-nets 导出图及其性质的研究,得出强占优的本质是求取翻转关系的传递闭包,从而利用Warshall 算法求出可判断任意CP-nets 的强占优;其次,通过求取3 种不同结构(可分离的、链表结构和树形结构)的CP-nets 的偏好个数,给出了CP-nets 可表达的偏好的不完备性定理,并给出了可分离的CP-nets 中偏好的计数公式;最后,研究CP-nets 的一致性,给出了CP-nets 的一致性判定定理及其算法.所做工作不仅解决了Boutilier 和Goldsmith 提出的一些难题,还深化了CP-nets 的基础理论研究.
2012, 23(6):1542-1560. DOI: 10.3724/SP.J.1001.2012.04200
摘要:高效Top-K 查询处理在涉及大量数据交互的应用中是一项重要技术,随着应用中不确定性数据的大量涌现,不确定性数据的管理逐渐引起人们的重视.不确定性数据上Top-K 查询从语义和处理上都呈现出与传统Top-K查询不同的特点.在主流不确定性数据模型和可能世界语义模型下,学者们已经提出了多种不确定性Top-K 查询的语义和处理方法.介绍了当前不确定性Top-K 查询的研究工作,并对其进行分类,讨论包括语义、排序标准、算法以及应用等方面的技术.最后提出不确定性Top-K 查询面临的挑战和下一步的发展方向.
2012, 23(6):1561-1577. DOI: 10.3724/SP.J.1001.2012.04114
摘要:利用关键字可以在模式未知的情况下对XML 数据进行查询.在当前的XML数据流上的关键字查询处理中,打分函数往往不能都满足各种用户不同的需求.提出了一种基于skyline 的XML 数据流上的Top-K 关键字查询.对于这种查询,不需要考虑影响结果与查询相关性的复杂因素,只需利用skyline 挑选与查询最相关的结果.提出了两种XML 数据流上的有效的基于skyline 的Top-K 关键查询处理算法,包括对单查询和多查询的处理算法.通过扩展实验对两种算法的有效性和可扩展性进行了验证.经过实验验证,所提出的查询处理算法的效率几乎不受关键字个数、查询结果数量、查询数量等参数的影响,运行时间和文档大小大致呈线性关系.
2012, 23(6):1578-1587. DOI: 10.3724/SP.J.1001.2012.04111
摘要:随着网络信息飞速的发展,收集并组织相关信息变得越来越困难.话题检测与跟踪(topic detection andtracking,简称TDT)就是为解决该问题而提出来的研究方向.话题检测是TDT 中重要的研究任务之一,其主要研究内容是把讨论相同话题的故事聚类到一起.虽然话题检测已经有了多年的研究,但面对日益变化的网络信息,它具有了更大的挑战性.提出了一种基于增量型聚类的和自动话题检测方法,该方法旨在提高话题检测的效率,并且能够自动检测出文本库中话题的数量.采用改进的权重算法计算特征的权重,通过自适应地提炼具有较强的主题辨别能力的文本特征来提高文档聚类的准确率,并且在聚类过程中利用BIC 来判断话题类别的数目,同时利用话题的延续性特征来预聚类文档,并以此提高话题检测的速度.基于TDT-4 语料库的实验结果表明,该方法能够大幅度提高话题检测的效率和准确率.
2012, 23(6):1588-1601. DOI: 10.3724/SP.J.1001.2012.04110
摘要:基于可能世界的不确定集合的相似查询,从语义上或者从计算方法的角度来看,都有别于传统的确定型集合上的技术.由于集合中的项存在不确定性,即一个项出现在集合中是有一定概率的,使得传统处理集合的技术不再适用.提出了一个基于可能世界的集合期望相似度的度量公式.在期望的度量公式中,如果一对集合(X,Y)的期望相似度大于给定的阈值τ∈(0,1),则被称为相似集合对.一般的算法,在基于可能世界的情况下计算不确定集合的期望相似度,其复杂度是指数级的.提出了利用动态规划来计算集合期望相似度的算法,该算法的复杂度是多项式级别,极大地减少了计算时间.实验结果表明了基于该算法查询的可用性和高性能.
杨智 , 殷丽华 , 段洣毅 , 吴金宇 , 金舒原 , 郭莉
2012, 23(6):1602-1619. DOI: 10.3724/SP.J.1001.2012.04083
摘要:动态调整安全级是目前提高强制访问控制模型可用性的主要途径,它大致包括两类方法.其中,安全级范围方法对主体权限最小化的支持不够,而污点传播方法存在已知隐蔽通道.提出了保护操作系统保密性和完整性的广义污点传播模型(generalized taint propagation model,简称GTPM),它继承了污点传播在最小权限方面的特点,拓展了污点传播语义,以试图关闭已知隐蔽通道,引入了主体的降密和去污能力以应对污点积累;还利用通信顺序进程(CSP)语言描述了模型的规格,以明确基于GTPM 的操作系统的信息流控制行为的形式化语义;基于CSP 的进程等价验证模型定义了可降密无干扰,并借助FDR工具证明形式化构建的抽象GTPM系统具有可降密无干扰安全性质.最后,通过一个示例分析了模型的可用性提升.
2012, 23(6):1620-1634. DOI: 10.3724/SP.J.1001.2012.04118
摘要:进程重放用于程序调试,无法重现系统全部状态,难以分析错误根源.而系统级重放复杂且难于实现,尚无模型分析方法提供理论指导,确保重放执行与记录执行等价.为了使执行重放系统适用于系统调试,建立虚拟机指令执行模型,提出了虚拟机执行重放的定义,给出并证明了成功重放的充分条件.根据该充分条件,设计实现了基于Xen的虚拟机重放系统CASMotion.CASMotion 讨论了Xen DomU 中不确定事件的种类,给出各类事件的重放方法以及时间点的匹配算法.CASMotion 成功实现了不确定事件的准确重放,实验结果表明其具有较低的性能损失.