摘要:在参数计算与复杂性理论中,一个参数问题是固定参数可解的问题当且仅当该问题是可核心化的.核心化技术是参数化算法设计中应用最为广泛、有效的技术,是参数理论中的一个研究热点.通过实例分析对比了最主要的4种核心化技术的基本思想、应用特点和方法,总结了核心化技术在cover类、packing类和cut类等几个重要领域中的应用成果,展望核心化技术的进一步研究方向并加以分析讨论,针对核心化新技术研究和某些热点问题,提出了可能采取的核心优化方法和思路.

摘要:长流分段是提高流处理器上流寄存器文件(stream register file,简称SRF)带宽利用率的重要途径之一.其中,量化受段大小影响的程序运行时间是获得最优分段的关键.为此提出了一种基于参数模型的长流分段技术,旨在获得理论上的最优分段以最小化程序运行时间.首先,建立了一个预取和重用优化指导的参数模型,以反映段大小对流处理器上程序性能的影响.然后,基于该模型分析,分别研究了计算密集型程序和访存密集型程序的最优分段策略.最后提出一种面向任意程序的最优分段技术.实验结果表明,该长流分段技术能够有效地避免和隐藏片外访存延迟,从而充分开发流处理器强大的计算能力.

摘要:最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.

摘要:旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P?NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法——动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.

摘要:增量搜索是一种利用先前的搜索信息提高本次搜索效率的方法,通常可以用来解决动态环境下的重规划问题.在人工智能领域,一些实时系统常常需要根据外界环境的变化不断修正自身,这样就会产生一系列变化较小的相似问题,此时应用增量搜索将会非常有效.另外,基于BDD(binary decision diagram)的启发式搜索,结合了基于BDD的搜索和启发式搜索这两种方法的优点.它既用BDD这一紧凑的数据结构来表示系统的状态空间,又通过使用启发信息来进一步压缩搜索树的大小.在介绍基于BDD的启发式搜索和增量搜索之后,结合这两种方法给出了基于BDD的增量启发式搜索算法——BDDRPA^*.大量的实验结果表明,BDDRPA^*算法是非常有效的,它可以被广泛地应用到智能规划、移动机器人问题等领域中.

摘要:近年来基于字的方法极大地提高了中文分词的性能,借助于优秀的学习算法,由字构词逐渐成为中文分词的主要技术路线.然而,基于字的方法虽然在发现未登录词方面有其优势,却往往在针对表内词的切分效果方面不及基于词的方法,而且还损失了一些词与词之间的信息以及词本身的信息.在此基础上,提出了一种结合基于字的条件随机场模型与基于词的Bi-gram语言模型的切分策略,实现了字词联合解码的中文分词方法,较好地发挥了两个模型的长处,能够有效地改善单一模型的性能,并在SIGHAN Bakeoff3的评测集上得到了验证,充分说明了合理的字词结合方法将有效地提高分词系统的性能,可以更好地应用于中文信息处理的各个方面.

摘要:在数据挖掘研究领域,现有的大多数聚类算法都受到数据可伸缩性和结果可解释性的限制.为了解决这一难题,提出了一种基于概念的数据聚类模型.该模型从描述数据样本的数据本身出发,首先在预处理后的数据集上提取基本概念,再对这些概念进行概化,形成表示聚类结果的高层概念,最后基于这些高层概念进行样本划分,从而完成整个聚类过程.该模型能够在保证聚类准确性的基础上,很大程度地减少要处理的数据量,提高原算法的可伸缩性.另外,该模型基于概念进行知识的发现与分析,能够提高聚类结果的可解释性,便于与用户交互.实验结果表明,该模型对于聚类结果较好且复杂度较高的算法尤为有效.

摘要:利用信息检索领域中的相关算法,分析研究通过信息检索相关技术得到的相关信息,建立了一个网络新闻影响力模型来定量地计算一则新闻的影响力,从而估计它对社会安全产生影响的程度.在对大量实验结果的统计分析中发现,此方法可以有效地对新闻文章进行排序,发现不同新闻类型中最值得关注的新闻,其结果与人的定性判断结果具有较高的一致性.

摘要:提出采用黎曼流形描述研究对象和基于坐标卡生成Voronoi图的算法思路.讨论了黎曼流形上研究Voronoi图的难点,并给出了存在定理,该定理说明了坐标卡上Voronoi图的存在条件.按照算法思路和存在定理,详细描述了二维黎曼流形上创建坐标卡的算法,并给出流形上转换函数和混合函数的定义方法.最后描述了基于坐标卡生成Voronoi图的算法,并给出了具体实例.

摘要:播音员镜头的检测是新闻视频结构化的关键步骤之一.提出了一种基于人脸检测与SIFT特征点匹配的播音员镜头自动检测算法.该方法首先利用人脸检测器过滤出具有人脸的候选镜头,然后利用颜色直方图判断镜头是否可能相似,再利用SIFT特征点匹配从候选镜头关键帧中找出相关的镜头组,最后利用各镜头组的信息判断出哪些是播音员镜头.对比传统的方法,该方法除了训练一个通用的人脸检测器外,不需要模板,也不需要针对某类新闻节目训练特别的分类器,可以直接利用算法对新类型的新闻节目提取播音员镜头.实验结果表明,该算法能够广泛地适应于各种不同种类的新闻节目、不同视觉质量的视频,可以有效地应用于新闻视频分析.

摘要:提出了异常轨迹检测算法,通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配,进而检测异常轨迹.算法要点如下:(1) 为了有效地表示轨迹的局部特征,以k个连续轨迹点作为基本比较单元,提出一种计算两个基本比较单元间不匹配程度的距离函数,并在此基础上定义了局部匹配、全局匹配和异常轨迹的概念;(2) 针对异常轨迹检测算法普遍存在计算代价高的不足,提出了一种基于R-Tree的异常轨迹检测算法,其优势在于利用R-Tree和轨迹间的距离特征矩阵找出所有可能匹配的基本比较单元对,然后再通过计算距离确定其是否局部匹配,从而消除大量不必要的距离计算.实验结果表明,该算法不仅具有很好的效率,而且检测出来的异常轨迹也具有实际意义.

摘要:研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.

摘要:图像语义的自动标注是一个具有挑战性的研究课题,目前常见的机器学习方法,如统计生成模型(generative model)与判别模型(discriminative model)都被用于该问题的研究中.然而由于语义鸿沟的存在、图像训练数据的不平衡性以及图像标注的多标签特性等问题,使得上述方法的性能都有待进一步提高.提出一种基于可判别超平面树的生成模型图像标注方法.该方法根据待标注目标图像的高生成概率邻域,建立局部超平面分类树,进而利用同层类间可判别信息,按自顶向下的层次分类得到待标注图像的语义相关图像集合.由此得到的相关类信息与新的生成模型框架相结合对待标注图像与语义关键词的联合概率进行估计,实现对目标图像的标注.其特点在于生成模型与判别模型方法得到了有效结合,可判别超平面树对隐含语义聚类的判别分析是对待标注图像的生成“邻域”的逐步求精过程,有效地提高了生成模型标注准确度;而对于判别分析难以解决的多标签分类、训练数据不平衡等问题,此方法通过联合概率估计自然地实现目标图像的多标签分配.在常用的包含5 000幅图像的ECCV2002数据集进行了实验,结果表明,与目前已知的具有较好标注效果的基于生成模型的MBRM模型(采用图像分割方法)以及基于辨别分析的ASVM-MIL相比,此方法的F1因子分别提高了14%和13%.

摘要:给出一种基于CEI(containment-encoded intervals)的存储优化的数据流查询区间索引结构.在数据流处理中涉及到大量的数值型区间查询操作,构造一个基于主存并支持快速查询的区间索引结构十分必要.对CEI索引结构而言,虽然支持高速查询,但存储利用率较低.针对该问题,提出了索引结构ACEI(advanced-CEI).在CEI索引结构的基础上,通过数据结构调整和参数优化,ACEI可在保持原有查询速度的前提下将CEI的空间复杂度由O(R+N·W/L+N·log(L))降为O(sqrt(R·N)+ N·sqrt(W)).实验结果表明,ACEI结构可以极大地提高索引结构的存储利用率,并且可以用于大端点值域下的区间索引.

摘要:首先概述了网络距离预测的基本概念,从不同角度对网络距离预测技术进行了分类讨论.然后根据预测机理的差异将现有网络距离预测技术划分为基于虚拟坐标的预测技术、基于网络拓扑结构的预测技术以及网络邻近度估计技术.在对典型的预测技术进行分析对比后,详细综述了网络距离预测的研究现状,对现有的各种预测技术以及研究成果进行了分析,指出了需要进一步研究的问题.最后探讨了网络距离预测技术的未来发展方向.

摘要:基于无线信号的广播本质,利用传统MAC协议所忽略的串音(overhearing)数据,提出一种方法以在媒介访问控制层去除数据的空间相关性.根据串音所接收到的数据,事件监测节点间协同地对自身的数据进行压缩后再发送,从而在链路层减少冗余信息的传输.首先针对节点间的协同数据压缩问题进行量化,建立线性规划模型;进而提出一种近似最优的、更低时间复杂度(O(N²))的启发式节点筛选算法.在此基础上,设计一种能量有效的、基于协同压缩方法的MAC协议(CCP-MAC),可分布式地控制节点实现该节点筛选算法,相应节点可从筛选出的被压缩节点子集中接收串音数据,融合冗余数据以后再进行发送.实验结果表明,CCP-MAC利用串音数据协调节点进行数据压缩,可在很大程度上节约能量,延长网络的生命周期.

摘要:针对网格应用中对委托限制的多方面需求,提出了基于层次角色委托的服务网格授权执行模型.模型支持委托角色授予与撤销功能以及相应的关联性限制特性.通过加入信任度,细化了关联性限制的表达粒度.通过定义角色树作为委托授权的基本单位并对角色树进行剪枝,改善了部分委托实现的难度.通过定义带信任度的委托传播树,细化了对委托传播限制的控制.提出的委托凭证全面支持了角色委托的临时性、关联性、部分性、传播性限制需求.对模型中的委托授权执行规则作了形式化描述,并证明了执行规则能够细粒度地控制委托授权的执行过程.实例展示表明,模型能够满足网格应用对委托限制多方面的需求.

摘要:在移动IPv6网络中,为确保移动节点的可寻址性,提升网络系统的服务可用性和系统性能,有必要在家乡链路部署多HA,并有效平衡负载.提出了基于主动过载预防的多HA负载均衡方法.该方法通过主动地为移动注册请求动态选择最优HA,预防HA过载,而不同于原有方案仅仅基于被动的负载迁移的思路.所提方法引入动态加权负载评估算法,为负载均衡的实施提供最佳决策依据,采用负载切片机制减小信令开销.通过理论分析证明了提出的方法比原有各方法能够更有效地减小由于HA过载造成的移动注册失败率、平均注册延时,同时引入的系统开销更小,更显著地提升MIPv6网络系统服务的可用性和系统性能.

摘要:服务环境中的动态性会对故障诊断算法性能造成影响.为了降低这种影响,分析了服务环境中的动态性,提出多层管理模型建模服务系统:二分贝叶斯网络建立依赖模型和二元对称信道建模噪声.针对故障自动修复机制导致的动态故障集环境,在故障持续时间统计的基础上修正当前窗口内先验故障概率;针对动态模型环境,基于当前窗口内原始模型和观察症状时间建立期望模型.仿真结果显示,算法可以有效地诊断动态环境下的互联网服务故障.

摘要:设计安全、合理的密钥管理方法是解决无线传感器网络安全性问题的核心内容.基于exclusion basis system(EBS)的动态密钥管理方法由于安全性高,动态性能和可扩展性好,受到了广泛关注.但在这种方法中存在共谋问题,即对于被捕获节点通过共享各自信息实施的联合攻击抵抗性较差.针对这一问题,分析了传感器节点形成共谋过程中的特点,以最短共谋链的长度为目标提出了共谋问题的优化模型.在此基础上,提出了基于离散粒子群算法的无线传感器网络共谋问题优化方法.仿真实验结果表明,与前人的工作相比,采用此优化模型和方法不仅提高了捕获网络难度,而且显著增强了网络对捕获节点的抵抗性.

摘要:将已有的生命周期路由算法分成两类:普通Max-Min(GMM)算法和条件Max-Min(CMM)算法,然后为这两类算法分别提出它们的诚实机制.通过给予中继节点适当的报酬,这些诚实机制可以确保已有的算法在面对自私节点的时候也可以实现它们的设计目标.说明生命周期路由算法的本质可以使这种报酬率相对较低且比较稳定,实验结果也进一步证明了这一点.

摘要:研究传统的客户端难题方案,之后提出一种自适应客户端难题方案.该方案采用一种轻量级的协议交互 方式来获取客户端和服务器双方的实时状态信息,并据此自适应地调整客户端难题的难度.为了评估该方案的适用 性,结合传统和自适应两种客户端难题方案,在对等(P2P)网络中提出了一种抵御DoS 攻击的自适应安全框架.理论 分析和实验结果表明,甚至在高度恶意的网络环境中,自适应客户端难题方案都可以在不明显影响合法客户端性能 的前提下有效地抵御各种DoS 攻击.

摘要:在分析了信任评估过程中攻击手段及其相互间关系的基础上,提出了基于贝叶斯决策理论的根据推荐偏差度修正对推荐的信任度方法.使用贝塔分布描述推荐偏差度,依据最小损失原则修正对推荐的信任度,并将具备推荐信任修正机制的信任模型运用在自组网的路由协议中,以便优化路由选择.MATLAB下的仿真结果表明,该方法能够有效抵御一些针对信任管理的威胁并提升信任管理的正确率,进而提高自组网环境下检测恶意节点的效率.

摘要:对分组密码算法CLEFIA进行不可能差分分析.CLEFIA算法是索尼公司在2007年快速软件加密大会(FSE)上提出来的.结合新发现和新技巧,可有效过滤错误密钥,从而将算法设计者在评估报告中给出的对11圈CLEFIA-192/256的攻击扩展到11圈CLEFIA-128/192/256,复杂度为2^103.1次加密和2^103.1个明文.通过对明文附加更多限制条件,给出对12圈CLEFIA-128/192/256的攻击,复杂度为2^119.1次加密和2^119.1个明文.而且,引入一种新的生日筛法以降低预计算的时间复杂度.此外,指出并改正了Tsunoo等人对12圈CLEFIA的攻击中复杂度计算方面的错误.

摘要:针对复杂遮挡环境下多摄像机协同的问题,提出一种基于三焦点张量点转移的多摄像机协同目标定位方法.该方法利用单摄像机视图中头部检测的结果进行对极匹配,然后利用虚拟顶视图和摄像机视图之间的三焦点张量关系进行点转移,确定行人在虚拟顶视图中的位置.该方法的优势在于:不需要标定摄像机参数,不需要假设物体在共同平面上运动,不存在利用对极关系进行点转移时出现的交点退化的问题.与传统方法的实验结果对比表明了该方法的有效性和准确性.

摘要:局部线性嵌入算法极大地依赖于邻域是否真实地反映了流形的内在结构,现有方法构造的邻域结构是拓扑不稳定的,对噪音和稀疏数据敏感.根据认知的相对性规律提出了相对变换,并用其构造了相对空间和相对流形.相对变换可以提高数据之间的可区分性,并能抑制噪音和数据稀疏的影响.在构造的相对空间和相对流形上确定数据点的邻域能够更真实地反映流形的内在结构,由此提出了增强的局部线性嵌入算法,明显地提高了性能,特别是基于流形的方法还同时提高了速度.标准数据集上的实验结果验证了该方法的有效性.

摘要:针对移动用户的实时显示需求,提出一种基于逆细分的三角网格压缩算法.通过改进逆Butterfly简化算法,采用逆改版Loop模式,将细密的三角网格简化生成由稀疏的基网格和一系列偏移量组成的渐进网格;然后,通过设计偏移量小波树,将渐进网格进行嵌入式零树编码压缩.实验结果表明:该算法与以往方法相比,在获得较高压缩比的同时,运行速度较快.适用于几何模型的网络渐进传输和在移动终端上的3D图形实时渲染.