摘要:在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有(θ)(t).

摘要:高层体系结构HLA(high level architecture)是美国国防部提出的建模和仿真的标准,时间管理服务是其重要的组成部分,而GALT(greatest available logical time)的计算是RTI(runtime infrastructure)时间管理服务实现的核心技术.GALT算法容易导致死锁,继而导致整个仿真无法推进.在Frederick Kuhl算法的基础上探讨了死锁产生时系统所特有的一些规律,得出了一些重要结论:如果系统处于死锁状态,则所有盟员的GALT和输出时间一定分别相等,并且GALT一定等于输出时间;所有Lookahead大于0的盟员一定处于NMR/NMRA推进状态而不会处于其他推进状态(TAR/TARA/FQR).最后提出了基于"身高测量法"的无死锁的GALT算法,"身高测量法"为RTI中时间管理模块的实现提供了可靠保证.

摘要:语音识别领域已经取得了稳步发展并出现了众多实用系统,但众所周知,今天的识别技术还远没有达到要求,而"鲁棒性"问题是系统性能提高的一个主要障碍.集中讨论了一种对抗语音识别系统脆弱性的通行方法--信道正规化技术,提出了一种新的正规化策略--多层信道正规化MLCN(multi-layer channel normalization)新的算法应用递归补偿算法,在频谱域和倒谱域两层上进行正规化,降低噪音和去除信道畸变,从而为后续识别过程提供更鲁棒的特征参数.在此基础上,探讨了一种新的语音识别特征参数的提取-频域动态倒谱系数,由于MLCN的引入,频域的动态信息被恰当地集成到最终的特征向量中.在gallina系统中的实验证明了这种新方法的有效性.

摘要:引进了一种在缺省理论中提取优先序的方法.与已有方法相比,此方法不仅具有合理性且具有低难度.进而定义了缺省逻辑的优先稳定语义.这种方法在不增加复杂性的情况下,增强了谨慎稳定缺省推理的能力.

摘要:提出了一种识别多载体数据流中包含的特定信息的新方法.该方法按照特征词及其拼音匹配规则,基于统计自然语言理论,通过自动的归纳学习,将从语料库中获得的词性间的转移值作为系统知识,利用有效的知识逼近策略判断真实数据流中的特征词与其上下文的关系,并得到特征词在真实文本中的评测值,以此来考查真实数据流中出现的全部特征词与在语料中所学到的特征词上下文搭配规则上的相似程度.如果整个数据流的评测值超过阈值,该数据流将被屏蔽.实验结果表明,根据该方法开发的识别及监控多载体数据注中不良信息的实验系统取得很好的效果.

摘要:特征选择在模式识别和数据挖掘等领域都有十分广泛的应用.然而,当涉及空间数据时,由于传统特征选择方法没有很好地考虑数据的空间特性,所以会导致特征选择结果性能下降.从空间数据本身的特性出发,提出一种特征选择方法MEFS(maximum entropy feature selection).MEFS在基于最大熵原理的基础上,运用互信息和Z-测试技术,采用两步方法进行空间特征选择.第1步,空间谓词选择;第2步,选择与每个空间谓词对应的相关属性集.最后,分别对MEFS方法和RELIEF方法以及基于MEFS的分类方法与决策树算法ID3分别进行了实验比较.实验结果表明,MEFS方法不仅可以节约特征提取和分类时间,而且也极大地提高了分类质量.

摘要:多小波是对小波理论的一个新发展,它可以同时满足正交性、对称性、短支撑等良好特性要求,而标量小波不能同时达到这些要求.提出了一种新的基于多小波、多分辨率分析抑制超声斑纹噪声的理论和方法,通过评价两种多小波的分解与重构,得到了两种可以分别适用于这两类多小波的最佳预处理方法,给出了多小波变换的解析表达式.在二维图像阵列的应用方面,通过采用局部方差作为阈值,对超声斑纹图像进行阈值化去噪处理的实验结果表明,多小波变换在有效抑制斑纹噪声的同时,相对于其他方法还能更好地保留原图像的边界等重要特征信息.

摘要:离散分层马尔可夫随机场(MRF)模型由于层间具有了因果性,因而其非迭代的推导算法比非因果的马尔可夫随机场模型的迭代算法复杂度低得多,结果更精确.针对图像分割问题中观测数据有限的情况,提出了一种新的基于离散分层MRF的半树模型,推导出了它的最大后验边缘概率(MPM)算法.半树模型不仅继承了一般分层模型快速、误分类少的优点,还避免了计算中遇到的数值下溢问题,减轻了分层模型带来的块现象,尤其适合大幅面图像的处理.

摘要:函数依赖是数据语义的重要组成部分,这一概念被引入到XML的领域中.基于DTD,XML的树模型和路径表达式,对节点的值相等和路径节点集作了定义.在此基础上,研究了XML中函数依赖、逻辑蕴涵和路径闭包的概念,证明了函数依赖在给定DTD上的可满足性.提出了一个XML上函数依赖的正确和完备的推理规则集,并给出了一个用于计算路径闭包的算法.

摘要:数据中的异常点常常反映了企业经营中潜伏的问题或暗藏的商机,数据分析人员经常需要从大量的数据中找出这些异常点.最近提出的一种从数据中自动发现异常点的方法,将人们从繁重的体力劳动中解放出来.然而,该方法在计算效率和伸缩性方面还存在很多不足.针对这些不足,对该方法进行了优化和改进,提出了一种基于约束的多维数据异常点挖掘方法.通过在数据挖掘过程中引入约束条件,首先将数据立方体限制到一个小的多维空间,然后再从中找出异常点.实验结果表明该方法非常有效.

摘要:试图从另一个角度来考察主题提取算法HITS,即提出一种基于相似度的链接分析模型来观察主题提取的过程.通过给出一种一般化的相似度定义,提出了一种仅使用链接分析来改善主题提取的质量的主题提取算法.同时,还将主题发现的功能也结合到了算法的框架中.通过该功能,用户可以搜索到次流行的主题.实验结果显示了这一新算法的两个优点:不必使用内容分析即能改善主题提取的质量以及能够进一步发现在查询结果中显现出来的不同主题.

摘要:挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,之前的很多研究都是采用Apriori类的候选项目集生成-检验方法.然而,候选项目集产生的代价是很高的,尤其是在存在大量强模式和/或长模式的时候.提出了一种快速的基于频繁模式树(FP-tree)的最大频繁项目集挖掘DMFIA(discover maximum frequent itemsets algorithm)及其更新算法UMFIA(update maximum frequent itemsets algorithm).算法UMFIA将充分利用以前的挖掘结果来减少在更新的数据库中发现新的最大频繁项目集的费用.

摘要:信息检索长期存在着用词歧义性问题,在Web搜索上的表现更加突出.提出了一种基于用户查询日志的查询扩展统计模型,将用户查询中使用的词或短语与文档中出现的相应词或短语以条件概率的形式连接,利用贝叶斯公式挑选出文档中与该查询关联最紧密的词加入原查询,以达到扩展优化的目的.实验结果表明,该方法更适宜改进Web上的信息检索,相对传统的查询扩展算法可以大幅度提高查询精度.

摘要:移动目标数据库(moving object database)有别于一般数据库技术的重要特征之一就是不仅可以对移动目标在数据库记录的时刻进行位置查询,而且可以对不同记录时刻之间以及未来时刻的位置进行查询,其研究的首要问题是建立移动目标运动及位置更新模型.目前有大量依靠其他辅助设备(如GSM网络)定位的盲终端设备(如移动电话,PDA等),存在着MOD管理的潜在需求,需要对它们建立合适的运动及位置更新模型,来为移动用户提供基于位置的服务.针对这类无自定位能力的移动目标,利用它们通常运动在城市的道路网络上这一特点,提出了基于道路网络的移动目标历史和未来速度计算模型,在此基础上提出了基于道路网络的非等时位置更新模型.与传统的速度计算模型相比,基于道路网络的移动目标历史和未来速度计算模型在考虑移动目标定位误差时可以降低移动目标位置预测的误差;与等时位置更新模型相比,基于道路网络的非等时位置更新模型在平均预测误差相近的情况下,可以减少移动目标和定位设施之间的通信量.

摘要:移动IPv6协议给出了支持主机移动的远程签署和家乡签署两种组播方法,它们具有互补的优缺点.提出的移动组播算法综合了这两种基本方法,同时采用区域的层次型结构的路由思想,减少因主机移动而重构组播树的频率,并对模拟结果进行了分析和比较.

摘要:路径表达式作为XML数据查询语言的核心部分,关于它的计算方法的研究成果已有很多,然而针对路径表达式本身进行优化的研究却相对较少.提出了两种针对路径表达式的优化策略:路径缩短策略和补路径策略,从而提高了XML路径查询效率.路径缩短策略根据XML文档模式信息,将路径表达式查询长度缩短,从而简化查询本身以降低需要的查询代价;而补路径策略则试图使用代价更小的等价路径表达式来替换原始查询.经过对实验数据的分析,这两种优化策略对于绝大多数路径表达式查询可以应用,并可大幅度地改进路径表达式的查询性能.

摘要:推荐系统是电子商务系统中最重要的技术之一.随着电子商务系统用户数目和商品数目的日益增加,在整个商品空间上用户评分数据极端稀疏,传统的相似性度量方法均存在各自的弊端,导致推荐系统的推荐质量急剧下降.针对用户评分数据极端稀疏情况下传统相似性度量方法的不足,提出了一种基于项目评分预测的协同过滤推荐算法,根据项目之间的相似性初步预测用户对未评分项目的评分,在此基础上,采用一种新颖的相似性度量方法计算目标用户的最近邻居.实验结果表明,该算法可以有效地解决用户评分数据极端稀疏情况下传统相似性度量方法存在的问题,显著地提高推荐系统的推荐质量.

摘要:为了充分利用高性能网络,研究人员开发了多种用户级通信协议.这些用户级通信协议可以获得底层硬件提供的高带宽、低延迟.然而由于它们提供完全不同的应用程序接口,用户级通信协议往往只能支持科学计算,而不能支持传统的基于Socket接口、采用核心级通信协议的网络应用程序.通过增加一个IP协议支持模块,BCL-3用户级通信协议在支持科学计算的同时,可以有效地支持现有的基于TCP/IP协议的网络应用程序.而且在分析TCP/IP协议软件开销的基础上,IP协议支持模块有针对性地采用了一些优化技术,使运行在BCL-3上的TCP/IP协议可以取得很高的网络性能.改进的BCL-3已经运行在曙光3000L超级服务器上.在曙光3000L上,运行于BCL-3之上的TCP/IP协议取得了最大带宽938Mbps,最小单向延迟48.1μs的性能.

摘要:计算机取证研究的是如何为调查计算机犯罪提供彻底、有效和安全的技术.其关键是确保证据的真实性、可靠性、完整性和符合法律规定.介绍了计算机取证的过程以及取证软件的原理和实现,并且给出完整的取证实例.从理论和实现两个方面讨论了现有取证技术的局限性和面临的挑战,并展望其未来的发展方向.由于计算机犯罪手段的变化和其他技术的引入,现有的取证工作将向着深入和综合的方向发展.

摘要:在数字产品中嵌入数字水印,是对其进行版权保护的一种有力手段.近年来提出了不少数字水印方案,但是它们中大部分都是对称的,即用于水印嵌入和水印检测的密钥是相同的.而许多实际的应用都要求非对称的数字水印方案,即水印检测时所知道的秘密不足以修改、伪造或移去水印.对基于比特承诺和零知识证明的水印验证协议进行了研究.所有权证明者采用基于扩频的对称水印技术,在宿主信号中嵌入水印;水印检测的密钥采用比特承诺的形式提交给验证者,通过证明者和验证者之间的交互协议,验证者可以提取到所嵌入的水印,但无法修改、伪造或移去水印.分别提出了验证一个和多个水印比特的协议,可应用于验证嵌入在图像、音频和视频数据中的扩频水印.

摘要:先前众多的DWT(discrete wavelet transform)域水印算法几乎都是私有水印或易脆水印,而针对版权保护的鲁棒的、公开的小波域水印算法却极少.在充分考虑人类视觉系统掩蔽特性的基础上,首先给出基于图像分块的临界噪声阈值矩阵JND(just noticed difference),进而提出了一种基于DWT的鲁棒公开水印技术.算法首先把原图像各8(8块按Hilbert扫描顺序排列,然后在原图像分块的Hilbert序列中选取两相邻块分别进行一层DWT,再结合各分块JND阈值,通过不同强度地调整两相邻块各对应细节子带均值之间的大小关系以自适应地嵌入水印.嵌入水印具有很好的透明性,水印嵌入强度是与原图像特征相自适应的.同时,水印的提取无须求助于原图像.此外,实验结果也证明,该算法对常见图像处理操作、有损压缩和裁剪、挤压、像素移位等几何变换有较高的鲁棒性,特别是信号增强操作处理几乎不影响水印的正确提取,所以该算法是有效和实用的.