摘要:提出了基于Haar小波技术和偶合特征的多数据流压缩方法.主要研究成果包括:(1) 证明了Haar小波变换服从能量守恒规律,并用于压缩数据流;(2) 揭示了数据流的偶合度与变化趋势的相关性、偶合度的平移不变性及等价规律,采用特征流序列的小波系数和流能量近似表示流的趋势,达到压缩的目的;(3) 提出了多尺度能量分解模型,提高了表示精度;(4) 设计了多尺度能量分解压缩算法以及多尺度重构算法;(5) 在真实数据集上的实验表明,新方法的压缩比是传统小波方法的2～4倍.

摘要:针对生物序列分析中的多序列比对问题,当输入数据量比较大时,人们提出了很多启发式的算法来改善计算速度和比对结果.提出了用于进行全局DNA多序列比对的一种方法:MWPAlign(maximum weighted path alignment).该算法把序列信息用de Bruijn图的形式表示,并将输入序列的信息记录在图的边上,这样,就将求调和序列的问题转化为求图的最大权值路径问题,使多序列比对问题的时间复杂度降低到几乎线性.实验结果显示:MWPAlign是可行的多序列比对算法,尤其对于变异率低于5.2%的大量序列数据,相对于CLUSTALW(cluster alignments weight),T-Coffee和HMMT(hidden Markov model training)有较好的比对结果和运算性能.

摘要:目前,一些主流的判别学习算法只能优化光滑可导的损失函数,但在自然语言处理(natural language processing,简称NLP)中,很多应用的直接评价标准(如字符转换错误数(character error rate,简称CER))都是不可导的阶梯形函数.为解决此问题,研究了一种新提出的判别学习算法--最小化样本风险(minimum sample risk,简称MSR)算法.与其他判别训练算法不同,MSR算法直接使用阶梯形函数作为其损失函数.首先,对MSR算法的时空复杂性作了分析和提高;同时,提出了改进的算法MSR-II,使得特征之间相关性的计算更加稳定.此外,还通过大量领域适应性建模实验来考察MSR-II的鲁棒性.日文汉字输入实验的评测结果表明:(1) MSR/MSR-II显著优于传统三元模型,使错误率下降了20.9%;(2) MSR/MSR-II与另两类主流判别学习算法Boosting和Perceptron表现相当;(3) MSR-II不仅在时空复杂度上优于MSR,特征选择的稳定性也更高;(4) 领域适应性建模的结果证明了MSR-II的良好鲁棒性.总之,MSR/MSR-II是一种非常有效的算法.由于其使用的是阶梯形的损失函数,因此可以广泛应用于自然语言处理的各个领域,如拼写校正和机器翻译.

摘要:作为迭代算法,Mean Shift的收敛性研究是应用的基础,而Comaniciu和李乡儒分别证明了Mean Shift的收敛性,但证明过程存在错误.首先指出了Comaniciu和李乡儒的证明过程存在错误;然后,从数学上重新证明了Mean Shift算法的局部收敛性,并指出其收敛到局部极大值的条件;最后,从几何上举反例分析了Mean Shift的收敛性,并进行了深入比较和讨论.这为Mean Shift算法的深入研究及应用奠定了基础.

摘要:提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果.

摘要:在系统级综合中,资源的分配通常由设计者指定,或在设计空间搜索的最外层循环中进行枚举探索.提出了一种结合资源分配的启发式调度算法.它根据当前系统划分的结果,在调度过程中寻找合适的所需资源实例的数目,从而确定系统的资源分配以及调度指派方案.应用该调度算法可使设计空间搜索过程简化为划分、调度和评估三个步骤,省去了最外层的资源分配枚举循环,提高了搜索效率.实验结果验证了该算法的可行性和有效性.

摘要:并行交换是新兴的交换技术,基于该技术能够利用小型交换模块来构建大容量的交换系统,例如太比特或更高容量的交换机.把带输入队列的并行交换称为带缓存并行交换(buffered parallel switch,简称BPS),重点研究其中并行且独立工作的交换模块之间的负载平衡问题.从不同角度出发,提出两种负载平衡的定义.基于两种定义,分别分析了BPS负载平衡的条件并提出分布式调度算法族.最后,提出一种简单而有效的调度算法,该算法能在无加速比BPS中同时满足两种定义,仿真实验结果表明了该算法的有效性和良好性能.另外,就算法的工程实现进行了讨论.

摘要:提出目录路径属性与目录对象分离的元数据管理方法,扩展了现有的对象存储结构.该方法能够有效避免因为目录属性修改而导致的大量元数据更新与迁移;通过减少前缀目录的重迭缓存提高了元数据服务器Cache的利用率和命中率;通过减少遍历目录路径的开销和充分开发目录的存储局部性,减少了磁盘I/O次数;通过元数据服务器的动态负载均衡避免单个服务器过载.实验结果表明,该方法在提高系统性能、均衡元数据分布以及减少元数据迁移等方面具有明显的优势.

摘要:现实世界存在着大量的时态数据,时态数据挖掘(temporal data mining,简称TDM)是近年来学术界关注的一个重要研究课题.相似性发现技术关注数据的发展变化,试图从时态数据中发现事物动态演化的相似性规律.分析和比较了近年来TDM研究中涉及的主要相似性发现技术.首先区分定义了3类时态数据:时间序列、事件序列和交易序列;然后分类并讨论了各种与序列相关的主要方法和技术,涉及相似性度量、序列抽象表示和搜索,以及各类挖掘任务及其算法操作;最后展望进一步研究的方向.

摘要:研究Peer数据管理系统(peer data management system,简称PDMS)中的视图维护策略.首先提出一种混合的P2P架构,在该架构中,Peer优先选择基本的P2P架构而不是超级Peer架构.如果一个视图沿着PDMS的一条语义链路传播,那么它通过重构能够从许多数据源检索到数据,因此扩展了视图的定义,提出peer视图、局部视图和全局视图;并且从一条语义链路的任意节点出发,同一查询都能够得到相同的结果.在PDMS中,连接操作限制在各个局部PDMS中,这样,全局物化视图的维护就转化为对各相关局部物化视图的维护.在PDMS中,一个视图可能涉及到多个表的连接,根据该应用的需要扩展了Mork的规则系统.根据扩展了的规则系统进行更新数据传播,同时依据该规则系统提出一种算法来维护PDMS中的视图.最后进行实验验证.实验结果表明,该视图维护策略比Mork的视图维护策略的性能要好.

摘要:针对基于TPR树(time-parameterized R-tree)索引的大量并发CKNN(continuous k-nearest neighbor)查询处理,提出了一种可伸缩的增量连续k近邻查询处理(scalable processing of incremental continuous k-nearest neighbor queries,简称SI-CNN)框架,通过引入搜索区域进行预裁剪以减少查询更新所需要的TPR树节点访问代价,并引入了增量结果表以保存候选对象,批量地更新查询结果集,具有良好的可伸缩性.基于SI-CNN框架提出了一种增量更新的SI-CNN查询处理算法,能够基于上次查询结果增量的更新查询,支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作.实验结果与分析表明,基于SI-CNN框架的SI-CNN算法可以很好地支持大量并发的CKNN查询处理,具有良好的实用价值.

摘要:提出了一种基于概率模型的预测性时空区域查询处理方法.该方法采用Filter-Refinement方式来处理查询.首先,从数据库中选择所有可能满足查询的候选移动对象;然后,根据概率模型中定义的方法来计算候选移动对象满足查询的概率;最后,根据查询中指定的最小概率阈值过滤候选移动对象并返回查询结果.该概率模型将移动对象未来可能出现的位置定义为一个随机变量,并给出了计算移动对象在两种不同的运动模式下满足查询的概率值的方法.还提出了一种通过对大量历史轨迹抽样来获得概率密度函数(probability density function,简称PDF)的轨迹分析算法,并设计了概率密度函数索引STP-Index(spatio-temporal PDF-index).该索引能够有效地提高轨迹分析算法和概率计算的效率.实验结果表明,该查询处理方法能够有效地支持预测性时空区域查询的处理,提高查询结果的正确性,特别适合于具有较小的空间区域和长时间范围的预测性时空区域查询.

摘要:在数据流环境下,聚类算法不仅需要有较高的聚类质量,同时需要有实时处理速度.因而,提出了一类基于图形处理器(graphics processing unit,简称GPU)的快速聚类方法,包括基于K-means的基本聚类方法、基于GPU的数据流聚类以及数据流簇进化分析方法.这些方法的共同特点是充分利用了GPU强大的处理能力和流水线特性.与以往具有独立框架的数据流聚类算法不同,这些基于GPU的聚类算法具有同一框架和多种聚类分析功能,为数据流聚类分析提供了统一的平台.从分析可知,数据流聚类分析的核心操作实际上就是距离计算和比较.基于这一认识,利用GPU的子素向量处理功能进行距离计算.性能验证实验是在配有Pentium IV 3.4G CPU和NVIDIA GeForce 6800 GT显卡的PC上进行的.综合分析和实验结果表明,基于GPU的数据流聚类算法比传统的CPU算法平均快7倍,从而为高速数据流应用提供了良好的支持.

摘要:物化视图的刷新是Web仓储进行系统维护的一项主要任务,而基础数据变化频率则是刷新方案中的重要因素.在已有文献中,研究者已经给出一些关于基础数据变化规律的算法和估测器.虽然这些估测器取得了不错的效果,然而他们却忽略了这些估测器都有一定的适用范围,超出这个范围则效果急剧下降.在此,基于泊松过程进行分析,对估测器的适用范围进行了讨论,根据估测结果的偏离值和有效性对估测公式进行参数调整,同时根据估测值的大小不断调整数据源的访问频率和次数,从而使数据源访问模式和估测器互相适应,使估测器在最佳估测范围内获得估测值.实验结果表明,与已有文献中的方法相比,新提出的自适应估测算法能够取得更好的效果.

摘要:依据数据属性间的相似信息,提出了一种分类方法.该方法将属性矢量化,属性作为m维空间的基本矢量,数据记录作为属性矢量的和.利用属性间先验的概念相似信息,给出了求取任意属性矢量对的相似距离算法,并将数据间相关度计算转换为属性矢量及其相互投影的公式,从而得到任意两条数据的相关度;利用相关度,提出了一种分类算法.用详实的实验证明了该算法的有效性.

摘要:根据用户查询的分布情况,基于缓存以及在硬盘上对XML(extensible markup language)数据进行物化是提高XML数据存储与查询系统性能的主要方法之一.提出了一种XML查询集合的描述方法,即查询模式图,并以此为基础提出了一种能够充分考虑查询优化策略的物化方案生成方法.实验结果表明,该方法可以快速地生成物化方案,能够满足缓冲区管理等应用领域的需要.

摘要:大多数的空间聚类算法主要针对欧几何空间中的数据对象.然而在大多真实的应用中,空间对象的访问主要受限于空间网络(如道路网络),因此,对道路网络中的对象进行聚类分析更具有现实意义.道路网络中对象之间的距离度量需要通过基于网络的最短路径距离来重新定义,其计算代价高,这使得已有的基于欧几何距离的聚类算法不能直接运用到这种环境中.因此,通过开发道路网络的特征提出了两种新的聚类算法.算法使用网络中的边和结点信息来缩减搜索空间,避免了一些不必要的距离计算.实验结果表明,算法对于真实道路网络中的对象聚类是高效的.

摘要:多级调度应该保证事务历史可串行化,满足多级安全特性,不会引入隐通道,并保证高级别事务不会因为无限等待而"饿死".与其他多级数据管理系统调度机制相比,多级多版本时戳调度机制满足上述要求,但该机制存在两个问题,一是事务可能读旧版本,二是要求调度器是可信进程.提出一种多级多版本全局时戳调度机制(MLS_MVGTO),以及依据事务快照生成其全局时戳的基本步骤.给出了预知只读事务信息时的两种改进方法.MLS_MVGTO机制生成的事务历史可串行化,不引入隐通道等,并且该方法避免引入一个全局可信的调度器,并通过对只读事务的深入分析,允许事务读新版本.

摘要:针对现有软件水印算法中存在的一些不足,将反逆向工程技术和混沌系统与Easter Egg软件水印的思想相结合,提出了一个基于混沌的软件水印算法框架.该框架通过引入混沌系统,把水印信息散列编码到整个代码当中,以保护全部代码;通过引入反逆向工程技术来抵抗逆向工程攻击,算法框架与软硬件平台无关.在i386体系结构Windows平台下实现了该算法框架,并以该实现为例分析了水印的鲁棒性,讨论了水印的嵌入对程序性能的影响.分析表明,该算法可以有效地抵抗各种语义保持变换攻击,对逆向工程攻击具有较好的抵抗性,鲁棒性较高.

摘要:将目前主要用于小规模数据库查询的语义缓存技术拓展到海量数据库的聚集查询中,以面向聚集查询的语义缓存形式模型为基础,构造了语义缓存StarCache.详细讨论了StarCache中的聚集查询处理、语义缓存替换管理和一致性维护等技术.StarCache已经集成在自主研发的并行数据库中间件StarTP中,并在一项大型国家工程中得到实际应用.

摘要:在讨论计算机时钟分析模型的基础上,分析和总结已有的时间同步机制的特点,提出了一种低能耗单向广播校正同步机制,同时进行时钟偏移补偿和漂移补偿,并基于传统的锁相环(phase locked loop,简称PLL)原理设计了同步算法.为了避免实现过程中额外的硬件开销,开发了一种简洁的数字锁相环.最后,在Mica2实验平台上对所设计的同步机制与算法进行了验证,并与已有的典型算法进行了性能比较.

摘要:利用分布式哈希表,有结构的对等(peer-to-peer,简称P2P)网络具备了较短的路由长度和较好的扩展性.然而,由此产生了覆盖网络和物理网络之间的不匹配问题,它严重阻碍了在大规模环境下建立有效的对等网络.提出一种通用的、协议无关的方法来解决该问题.该方法基于节点交换机制,通过发现并实施有利于覆盖网络和物理网络匹配的节点交换来降低网络时延、提高性能.实验表明,该方法在明显降低了覆盖网络的平均时延的同时,也保证了额外开销可控.此外,若与其他协议相关的方法相结合,系统性能还可以得到进一步提高.

摘要:介绍了一种基于P2P(peer-to-peer)网络的大规模视频直播系统Gridmedia.该系统采用Gossip协议构建无结构的应用层覆盖网络,每个节点可以独立地选择自己的伙伴节点.在覆盖网络上,每个节点通过一种推拉结合的流传输策略从邻居节点获取数据.与DONet中的纯拉策略相比,推拉结合策略大幅度减小了终端用户观看视频的延迟,并有效降低了直播系统的控制开销.PlanetLab上的大量实验充分表明了该策略的有效性.Gridmedia的原型系统通过300Kbps的视频码流对2005年春节联欢晚会进行了全球互联网直播.晚会期间,全球范围内有超过500 000人次通过系统观看了直播,最高在线人数达到了15 239人,充分验证了系统的性能.

摘要:现有的无结构Peer-to-Peer(P2P)系统缺乏对拓扑公平性的考虑,并且不能对某些节点的恶意行为进行有效的抑制.其主要原因在于构造的拓扑对节点可信度的不敏感性,忽略了节点在不同领域中可信度的区别.据此,首先给出了基于领域的P2P信任模型的定义,然后在此基础上提出了一种针对无结构化P2P网络的自适应拓扑进化协议.该协议可以针对具体的领域进行拓扑进化,使得领域内的高可信节点占据相应领域拓扑的有利位置,低可信节点处于不利位置,从而体现拓扑的公平性.该协议同时能够对节点的恶意行为进行有效的抑制,并具有激励性质,鼓励节点提供更好的服务,以获得更高的回报率.分析和仿真结果表明,该协议较之现有协议,在拓扑的有效性和安全性等方面有较大的提高.

摘要:目前已有一些全球化的网络蠕虫监测方法,但这些方法并不能很好地适用于局域网.为此,提出一种使用本地网协同检测蠕虫的方法CWDMLN(coordinated worm detection method based on local nets).CWDMLN注重分析扫描蠕虫在本地网的行为,针对不同的行为特性使用不同的处理方法,如蜜罐诱捕.通过协同这些方法给出预警信息,以揭示蠕虫在本地网络中的活动情况.预警信息的级别反映报警信息可信度的高低.实验结果表明,该方法可以准确、快速地检测出入侵本地网络的扫描蠕虫,其抽取出的蠕虫行为模式可以为协同防御提供未知蠕虫特征.通过规模扩展,能够实施全球网络的蠕虫监控.

摘要:密钥加密协议的目的是利用安全性低的口令协商安全性高的密钥,进而利用密钥对以后的通信进行加密或身份认证,从而实现安全通信.现有的密钥加密协议大多缺乏安全证明,或者仅在Random Oracle模型下证明了协议的安全性.与Random Oracle模型下的协议相比,标准模型下可证安全的EKE(encrypted key exchange)协议虽然不需要Random Oracle假设,但它们都对参与方的计算能力要求较高,协议规则也更为复杂.从David P. Jablon在"Extended Password Key Exchange Protocols Immune to Dictionary Attacks"一文中提出的协议出发,通过引入服务端的公钥,并利用ElGamal加密和伪随机函数集,将一个Random Oracle模型下可证安全的EKE协议改进为一个标准模型下可证安全的EKE协议,并证明了改进后的协议仍然是安全的.与原始协议相比,改进后的协议只需要DDH(decisional Diffie-Hellman)假设,而不需要理想加密和Random Oracle假设;与其他标准模型下可证安全的协议相比,改进后的协议不需要CCA2(chosen ciphertext attack-2)安全的加密方案,从而不仅可以减少指数计算的次数,而且具有协议规则简单的优点.相对于KOY协议,改进后的协议将指数运算次数降低了73%;相对于Jiang Shao-Quan等人在"Password Based Key Exchange with Mutual Authentication"一文中提出的协议,改进后的协议将指数运算次数降低了55%.

摘要:在三角形域上构造对边界曲线和跨界导数插值的三角曲面是计算机辅助几何设计和计算机图形学等领域中的基本问题.此类问题称为三角形域上的超限插值问题.对现有三角形域上的超限插值方法进行了综述,并对现有三角形域上的超限插值方法以具体实例进行了比较.最后讨论了现有三角形域上的超限插值方法中有待进一步解决的问题.

摘要:实现了一个从带噪声的密集三角形拟合出带尖锐特征的细分曲面拟合系统.该系统包括了一种改进的基于图像双边滤波器的网格噪声去除方法,模型的尖锐特征提取以及保持尖锐特征的网格简化和拓扑优化.为了处理局部细节特征和模型数据量问题,提出了自适应细分方法,并将根据给定精度估计最少细分深度引入到细分曲面拟合系统中,使得拟合得到的细分曲面模型具有良好的细节特征和数据量小等特点.大量3D模型实验结果和实际工程应用结果表明了该细分曲面拟合系统的有效性.

摘要:从最小平方估计的观点揭示了最小平方估计与Laplacian光顺算法之间的关联,并进一步提出了M-估计器在网格光顺中的应用,最后延伸M-估计器至二次加权的M-估计器,在抑制噪声的同时有效地保持了表面特征.在本质上,二次加权的M-估计器就是双向滤波器.

摘要:超光谱图像作为一种三维图像,其海量的数据导致在有限带宽信道上传输和存储非常困难,必须对它进行有效的压缩编码.提出了一种基于非对称三维小波变换(3D wavelet transform,简称3DWT)和三维集合块分裂的超光谱遥感图像压缩方法.因为大多数超光谱图像在各个方向上具有非对称的统计特性,所以利用非对称三维小波变换去除图像的谱间和空间冗余.与传统的对称三维小波变换相比,非对称的三维小波变换能够更有效地去除相邻谱段间的冗余.提出了一种改进的3DSPECK(3D set partitioning embedded block)算法--非对称三维集合分裂块算法(asymmetric transform 3DSPECK,简称AT-3DSPECK),并被用于编码变换后的系数.根据变换系数的能量分布特点,三维零块分裂和三维octave子带分裂方法被有效地结合在所提出的AT-3DSPECK算法中.为了优化率失真和加速编码速度,也给出了一种零块优化排序的快速算法.实验测试表明:AT-3DSPECK算法的平均PSNR(peak signal to noise ratio)分别比AT-3DSPIHT(asymmetric transform 3D set partitioning in hierarchical trees)和3DSPECK算法高0.4dB和1.4dB.此外,AT-3DSPECK还具有比零树算法更快的编码速度.

摘要:提出了一种基于小波变换与纹理移植相结合的人脸衰老化合成(绘制)方法.首先,将衰老模板进行二维离散小波变换(2D discrete wavelet transform,简称2D DWT),提取出承载衰老皮肤纹理特征的高频子图与高通滤波后的低频子图;然后,将其与目标人脸图像的对应分量进行置换与融合,利用小波重构来完成衰老纹理向目标人脸的移植;同时,提取出年轻人群到年老人群在脸形上的平均变化,将其作用在目标人脸上以增强衰老化合成的效果.结合色彩渲染技术,设计实现了真实感人脸衰老化绘制的完整技术框架.实验部分分别将该方法应用于东西方人脸以及艺术图片,绘制结果显示出了具有真实感和感染力的效果.与基于PCA(principal components analysis),3D渐变模型、比例图等方法相比,该方法较好地解决了在人脸衰老化绘制中真实感与易操作性之间难以折衷的问题.