基于动作空间求解二维矩形Packing问题的高效算法
摘要：对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局,且在普通PC机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的.非线性循环的终止性分析
摘要：单重线性循环程序的终止性问题已被广泛研究,而有关非线性循环终止性判定的结果甚少.利用不动点理论研究了n维单重非线性循环的终止性问题,并建立了相应的符号判定算法.同时,对几类特殊循环的终止性进行了分析,得出了相应的结论.非规则流中高维数据流典型相关性分析并行计算方法
摘要：为了满足在计算资源受限的环境下高维数据流处理的实时性要求,提出一种方法——基于GPU（graphicprocessing unit）的非规则流中高维数据流的处理模型和具体的可行架构,并分析设计了相关的并行算法.该六层模型是将GPU处理数据的高宽带性能结合进滑动窗口中数据流的分析,进而在该框架下基于统一计算设备架构（compute unified device architecture,简称CUDA）,使用数据立方模型以及降维约简技术并行分析了多条高维数据流的典型相关性.理论分析和实验结果均表明,该并行处理方法能够在线精确地识别同步滑动窗口模式下高维数据流之间的相关性.相对于纯CPU方法,该方法具有显著的速度优势,很好地满足了高维数据流的实时性需求,可以作为通用的分析方法广泛应用于数据流挖掘领域.一类两阶段杂交流水作业的近似算法（英文）
摘要：讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务：第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.基于树核函数的中英文代词消解
摘要：基于树核函数,提出了从使用中心理论、集成竞争者信息和融入语义角色相关信息这3个方面对结构化句法树进行动态扩展来提升中英文代词消解的性能.首先探索了3种基本结构化句法树捕获方案,并使用SVMLight中提供的卷积树核函数直接进行基于结构化句法树的相似度计算,从而完成指代消解任务;其次,在分析3种结构化句法树捕获方案的基础上,从中心理论、竞争者信息和语义角色相关信息等几方面对捕获的结构化句法树进行了扩展;最后,通过ACE 2004 NWIRE英文语料和ACE 2005 NWIRE中文语料上的实验,说明了这些扩展能够提升代词消解的性能.话题跟踪中静态和动态话题模型的核捕捉衰减
摘要：话题跟踪是一项针对新闻话题进行相关信息识别、挖掘和自组织的研究课题,其关键问题之一是如何建立符合话题形态的统计模型.话题形态的研究涉及两个问题,其一是话题的结构特性,其二是话题变形.对比分析了现有词包式、层次树式和链式这3类主流话题模型的形态特征,尤其深入探讨了静态和动态话题模型拟合话题脉络的优势和劣势,并提出一种基于特征重叠比的核捕捉衰减评价策略,专门用于衡量静态和动态话题模型追踪话题发展趋势的能力.在此基础上,分别给出突发式增量式学习方法和时序事件链的更新算法,借以提高动态话题模型的核捕捉性能.实验基于国际标准评测语料TDT4,采用NIST（National Institute of Standards and Technology）提出的最小检测错误权衡系数评测法,并结合所提出的核捕捉衰减评价方法,对各类主要话题模型进行测试.实验结果显示,结构化的动态话题模型具有最佳的跟踪性能,且突发式增量式学习和时序事件链的更新算法分别给予动态话题模型0.4%和3.3%的性能改进.基于中心/修饰依存重排序模型的短语SMT
摘要：为了提高基于短语的机器翻译系统的重排序能力,提出了一个基于源语言端的中心-修饰依存结构的重排序模型,并将该重排序模型以软约束的方式加入到机器翻译系统中.该排序模型提出了一种在机器翻译中应用句法树资源的方法,将句法树结构,通过将句法树映射成中心-修饰词的依存关系集合.该重排序模型在基于短语系统的默认参数设置下,显著地提升了系统的翻译质量.在系统原有的词汇化的重排序模型基础上,该重排序模型在翻译模型中融入了句法信息.实验结果显示,该模型可以明显地改善机器翻译系统的局部调序.基于选择性集成的最大化软间隔算法
摘要：当前,boosting集成学习算法研究主要集中于最大化弱学习器凸组合的间隔或软间隔,该凸组合几乎使用了生成的所有弱学习器,然而这些弱学习器间存在大量的相关性和冗余,增加了训练和分类过程的时空复杂度.针对这一问题,在LPBoost基础上提出了一种选择性boosting集成学习算法,称为SelectedBoost.在每次迭代生成新的弱学习器以后,通过计算新生成的弱学习器与已有弱学习器的相关度和差异度,并结合当前集成的强学习器的准确率来判断是否选择该弱学习器.另外,当前的一系列boosting算法（如AdaBoost,LPBoost,ERLPBoost等）,本质上是基于已生成的1个或者多个弱学习器来更新样本权重,但与弱学习器相比,强学习器更能代表当前的决策面.因此,SelectedBoost通过在带约束的间隔最大化问题中引入更加严格的强学习器边界约束条件,使得该算法不仅参考弱学习器边界,同时还参考已生成的强学习器来更新样本权重,进而提高算法的收敛速度.最后,与其他有代表性的集成学习算法进行实验比较,结果表明,该方法在收敛率、分类准确性以及泛化能力等方面均具有比较明显的优势.云数据库研究
摘要：随着云计算的发展,云数据库的重要性和价值日益显现.介绍了云数据库的特性、影响、相关产品.详细讨论了云数据库领域的研究问题,包括数据模型、系统体系架构、事务一致性、编程模型、数据安全、性能优化和测试基准等.最后讨论了云数据库未来的研究方向.不一致数据库上带信任标记的查询结果
摘要：不一致数据无法正确反映现实世界,其上的查询结果内含错误或矛盾,而现有的很多不一致数据查询处理相关研究都存在信息丢失的问题.AQA（annotation based query answer）针对这一问题采用信任标签在属性级别上区分一致和不一致数据,避免了信息丢失.但AQA假设记录在依赖左边属性上的分量可信,且只针对函数依赖一种约束,具有应用局限性.在综合约束（函数依赖、包含依赖和域约束）范围内、不确定属性任意的情况下扩展了AQA,重新审视了AQA的数据模型及其上的查询代数,讨论了任意约束在查询结果上的蕴含约束计算问题.实验结果表明,扩展后的AQA非连接类查询的性能和普通的SQL基本相同,连接查询经优化后性能接近普通SQL查询,但AQA不丢失信息,与部分同类研究相比有很大优势.基于情节规则匹配的数据流预测
摘要：提出了一种数据流预测算法Predictor.该算法为每个待匹配的一般形式的情节规则分别使用了一个自动机,通过单遍扫描数据流来同时跟踪这些自动机的状态变迁,以搜索每个规则前件最近的最小且非重叠发生.这样不仅将无界的数据流映射到有限的状态空间,而且避免了对情节规则的过于匹配.另外,算法预测的结果是未来多个情节的发生区间和发生概率.理论分析和实验评估表明,Predictor具有较高的预测效率和预测精度.基于加权边界度的稀有类检测算法
摘要：提出了一种快速的稀有类检测算法——CATION（rare category detection algorithm based on weightedboundary degree）.通过使用加权边界度（weighted boundary degree,简称WBD）这一新的稀有类检测标准,该算法可利用反向k近邻的特性来寻找稀有类的边界点,并选取加权边界度最高的边界点询问其类别标签.实验结果表明,与现有方法相比,该算法避免了现有方法的局限性,大幅度地提高了发现数据集中各个类的效率,并有效地缩短了算法运行所需要的运行时间.无线网络中的干扰攻击
摘要：在无线网络中,媒介的广播、共享特性使其易于受到干扰性质的拒绝服务攻击,严重影响着网络的性能和安全.分析了当前存在的干扰攻击测度标准和攻击模型;从干扰攻击的检测、防御以及干扰源定位3个方面对当前具有代表性的研究工作进行了详细的分析和总结.最后给出未来可能的研究方向和研究重点.能量均衡的无线传感器网络非均匀分簇路由协议
摘要：提出了一种能量高效均衡、非均匀分簇和簇间多跳路由有机结合的无线传感器网络分布式分簇路由协议DEBUC（distributed energy-balanced unequal clustering routing protocol）.该协议采用基于时间的簇头竞争算法,广播时间取决于候选簇头的剩余能量和其邻居节点的剩余能量.同时,通过控制不同位置候选簇头的竞争范围,使得距离基站较近的簇的几何尺寸较小.这样,网络中不同位置节点之间的簇内和簇间通信能耗得以互相补偿.DEBUC采用簇间多跳路由,根据节点剩余能量、簇内通信代价和簇间通信代价,每个簇头在邻居簇头集合中运用贪婪算法选择其中继节点.仿真实验结果表明,DEBUC能够有效地节约单个节点能量、均衡网络能耗、延长网络生存周期.相继干扰消除的无线网络中的调度性能分析
摘要：研究了支持相继干扰消除（successive interference cancellation,简称SIC）的无线网络中链路调度算法的设计与分析.首先,为刻画SIC的顺序检测特性,提出M-level非累积干扰模型与有序累积干扰模型.然后,由于两种模型下的调度均为NP-hard问题,研究了近似调度的性能：（1）给出了一种工作于有序累积干扰模型的调度机制,其近似比为O（g）,其中,g为网络的链路多样性指数;（2）给出了一种工作于M-level非累积干扰模型的调度机制,其近似比为常数.最后,通过仿真实验考察了SIC对调度性能的影响.基于隐式分段自回归模型的图像插值算法
摘要：利用自然图像信号的分段统计稳态性可以有效地对图像信号进行建模.其分段统计稳态区域往往具有非规则的形态.采用规则窗口对图像统计稳态区域内的统计量进行估计存在较大的误差.提出一种基于概率描述的隐式分段自回归模型来刻画分段统计稳态区域形态,并基于该模型提出了一种改进的图像插值算法.实验结果表明,该方法可以较好地改善插值图像中在边缘处的模糊、振铃和噪声等瑕疵现象.无线移动网络跨可信域的直接匿名证明方案
摘要：基于信任委托的思想,提出一种移动环境下的跨可信域的直接匿名（direct anonymous attestation,简称DAA）证明方案,采用签名技术和直接匿名证明方法,实现对移动终端在多可信域之间漫游时的可信计算平台认证,并在认证过程中协商会话密钥,增强了远程证明体系的安全性.利用Canetti-Krawczyk（CK）模型对方案的认证协议的认证安全性和匿名安全性进行了形式化分析和证明.分析表明,该方案能够抵抗平台伪装攻击和重放攻击,其性能适用于无线网络环境.基于大偏差统计模型的Http-Flood DDoS检测机制及性能分析
摘要：针对Http洪泛Web DDoS（distributed denial of service）攻击,提出了一种检测机制.该机制首先采用型方法量化处理用户访问的网页序列,以得到用户访问不同网页的实际点击概率分布;然后,利用大偏差统计模型分析了用户访问行为的实际点击概率分布与网站先验概率分布的偏差;最后,依据大偏差概率检测恶意DDoS攻击.对该机制的性能进行仿真,结果表明,正常用户的大偏差概率大于恶意攻击者,并且大部分正常用户的大偏差概率大于10 36,而大部分恶意攻击者的大偏差概率则小于1040.由此,该机制能够有效地检测Http洪泛Web DDoS攻击,当检测门限设置为1060时,其有效检测率可达97.5%,而误检率仅为0.6%.另外,将该机制与基于网页转移概率的检测方法进行性能比较,结果表明,该检测机制的检测率优于基于网页专业概率的检测机制,并且在误检率小于5%的情况下,该机制的检测率比现有检测机制提高0.6%.