摘要:排序是计算机事务处理的重要操作之一.前人已经就内部排序、外部排序和并行排序提出各种方法.从一种全新的视角研究了排序算法,提出一种在单机上实现的并行排序算法THSORT(Tsinghua SORT).它用多个进程分别控制不同的硬件部件,使输入、排序和输出能够同时进行,从而大大提高了硬件部件的并行性和运行效率.在带有双磁盘阵列的硬件平台上进行的测试表明,THSORT的性能达到了NTSORT(new technology SORT)的1倍左右,并成为2002年PennySort(Daytona类)世界排序纪录的保持者.

摘要:在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图G_F是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图G_G,用来表征广义自由区之间的邻接情况,其顶数和边数均为Θ(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用"不改向"启发式策略的A^*算法在广义连接图G_G中寻找两点间的最短路径,算法的时间复杂度由基于G_F的现有算法的O(tlogt)降低到Θ(t).

摘要:减少通信开销对于并行化编译器生成高效的分布代码是非常重要的.首先提出了一个冗余并行执行模型(RPEM)作为通信优化算法生成的目标程序的执行模型,之后给出了区域图的概念和区域最大化算法,在最大化区域图的基础上进行数据流分析可以增大数据流分析粒度,提高分析的效率,同时也有助于通信的提前与合并.最后提出了一种基于区域图数据流分析的通信优化算法.该算法能够进行跨循环、跨过程的数据流分析,提高分析的精度,改善通信优化效果.实验结果表明,该算法对于通信量较大的程序能够有效地减少通信的次数和通信量,具有良好的可扩展性.

摘要:讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时,若目标序列符号顺序固定,且有部分符号方向给定,则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP-难解问题.同时,还给出了该问题的多项式时间近似算法.

摘要:作为一种有效的解决手段,相关反馈(relevance feedback)技术在基于内容图像检索(content based image retrieval)的研究中得到了深入的发展.尽管有效,已有的反馈算法却始终没有解决特征空间的有指导降维和特征中的噪声去除这两个问题.提出了一种新的方法,通过对用户在检索过程中提供的正反馈样本在各特征空间中的分布特性,利用主成分分析(principal component analysis)来消除特征中的噪声,实现了对特征空间进行有效的降维.试验结果显示,该方法在不牺牲检索精度的前提下提高了检索速度,降低了存储复杂度.

摘要:研究了基于覆盖的构造型神经网络(cover based constructive neural networks,简称CBCNN)中的双交叉覆盖增量学习算法(BiCovering algorithm,简称BiCA).根据CBCNN的基本思想,该算法进一步通过构造多个正反覆盖簇,使得网络在首次构造完成后还可以不断地修改与优化神经网络的参数与结构,增加或删除网络中的节点,进行增量学习.通过分析认为,BiCA学习算法不但保留了CBCNN网络的优点与特点,而且实现了增量学习并提高了CBCNN网络的泛化能力.仿真实验结果显示,该增量学习算法在神经网络初始分类能力较差的情况下具有快速学习能力,并且对样本的学习顺序不敏感.

摘要:介绍了一个基于样本学习的人脸线条画生成系统.该系统可以根据用户给定的正面人脸照片自动生成相应的人脸线条画.在系统中有两个关键技术,即非参数化采样方法和灵活的线条画模板.对于给定图像上的任意像素点及其邻域,通过在样本空间搜索并匹配所有的相似邻域,计算该像素点在相应的线条画上出现的条件概率;然后根据艺术家的风格和得到的条件概率绘制"期望的线条画";最后使用模板匹配得到最后的线条画.此方法可以生成高质量的正面人脸线条画.

摘要:提出了一种基于非监督学习的人体运动分析方法.该方法通过使用MDL准则约束下的HMM模型对连续运动序列进行分割和聚类,并实现对运动序列的自动分割和标记.该方法由两步组成,首先通过聚类将连续运动离散化,并按照最小描述长度准则在离散域得到初始解.在此基础上,返回到连续域训练MDL准则约束下的HMM模型.使用HMM模型可以进一步利用原始序列中的动态信息获得更精确的最终结果.通过对实际人体运动序列进行的实验验证了方法的有效性.

摘要:语音与唇动面部表情的同步是人脸动画的难点之一.综合利用聚类和机器学习的方法学习语音信号和唇动面部表情之间的同步关系,并应用于基于MEPG-4标准的语音驱动人脸动画系统中.在大规模音视频同步数据库的基础上,利用无监督聚类发现了能有效表征人脸运动的基本模式,采用神经网络学习训练,实现了从含韵律的语音特征到人脸运动基本模式的直接映射,不仅回避了语音识别鲁棒性不高的缺陷,同时学习的结果还可以直接驱动人脸网格.最后给出对语音驱动人脸动画系统定量和定性的两种分析评价方法.实验结果表明,基于机器学习的语音驱动人脸动画不仅能有效地解决语音视频同步的难题,增强动画的真实感和逼真性,同时基于MPEG-4的学习结果独立于人脸模型,还可用来驱动各种不同的人脸模型,包括真实视频、2D卡通人物以及3维虚拟人脸.

摘要:联机分析处理OLAP(online analytical processing)查询作为一种复杂查询,当使用SQL(structured query language)语句来表述时,通常都包含多表连接和分组聚集操作,因此提高多表连接和分组聚集计算的性能就成为ROLAP(relational OLAP)查询处理的关键问题.提出一种基于分组序号的聚集算法MuGA(group number based aggregation with multi-table join),该方法充分考虑数据仓库星型模式的特点,将聚集操作和新的多表连接算法MJoin(multi-table join)相结合,使用分组序号进行分组聚集计算,代替通常的排序或者哈希计算,从而有效地减少CPU运算以及磁盘存取的开销.算法的实验数据表明,提出的MuGA算法与传统的关系数据库聚集查询处理方法以及改进后的基于排序的聚集算法相比,性能都有显著提高.

摘要:多重复制定义(MRD)虽然是数据库复制发展的一个新趋势,但是它会引起传播开销的增大.提出了关于MRD的3个优化传播算法:D-M,ILS和LIS算法.其中D-M算法通过拆分复制对象和合并传播对象获得最小的单次传播开销.在此基础上,ILS算法在链式结构下使总传播开销最小.而LIS算法在更普遍条件下通过分解传播任务得到优化的总传播开销.理论和实验分别验证了它们的正确性和有效性.

摘要:在分布式Peer-to-Peer (P2P)系统中,每个节点都具有相同的能力,负有相同的责任.它们将自己的资源提供给系统,同时可以共享系统中的信息和服务.但是,大多数P2P系统都具有局限性,比如说Napster,Gnutella,它们提供资源共享的粒度很粗糙,进一步地,它们忽略了文件在内容粒度上的共享.并且,大多数系统中节点的Peer是静态指定的,系统中不支持只具有临时IP的节点加入.提出了一个BestPeer的P2P系统,它具有以下几个特性:首先,它将移动Agent技术与P2P技术相结合,从而可以在数据提供者本地进行数据处理.其次,这个系统具有自配置的特性.一个节点可以动态地决定与哪个节点直接相连(决定哪个节点成为该节点的Peer),从而使网络结构的配置达到最优.另外,BestPeer系统提出了一个位置独立的全局名查找服务器(LIGLO).这个服务器可以惟一地识别具有动态IP地址的节点,从而使节点能够在它的Peer的IP地址发生改变后仍然能够找到它.BestPeer系统建立后,提出了一套评估系统的方法.采用32台Pentium II PC机进行实验,每台机器上都运行基于Java的存储管理程序.实验结果表明,BestPeer系统具有比传统的无自调整能力的P2P系统更好的性能.更进一步的实验还显示了BestPeer系统优于Gnutella 协议下的系统.

摘要:好的数据库逻辑设计目标是消除数据冗余以及插入、删除和更新异常.对于时态数据库,可以通过具有多时间粒度的时态函数依赖(TFDs)约束对时态数模式进行规范化.但是由于时间维的引入和多时间粒度的使用而给数据库设计带来巨大的复杂性.一般来说,系统所能处理的和相当多的应用所涉及到的时态类型集满足全序关系,并且具有全序时态类型集的TFD集的推导规则与传统函数依赖(FDs)的Armstrong公理有着紧密的联系.通过分析TFDs与FDs之间存在的联系,利用传统FD集的相应算法,提出了成员籍、有限属性闭包等TFD集的一些重要算法.这些算法是时态数据库进一步规范化的基础.

摘要:目前,网络在提高链路速率的同时出现了大量的新协议及新服务,而传统的网络设备一般采用专用硬件芯片或者基于纯粹的软件方案,很难兼顾性能与灵活性两方面的要求.为此,一种并行可编程的网络处理器被引入到路由器(交换机)的处理层面.它基于ASIP技术对网络程序处理进行了优化,同时还兼有硬件和软件两种方案的特点.网络处理器的出现将经典的"存储-转发"结构变为"存储-处理-转发",这为复杂的QoS控制和负载处理提供了可能.从网络处理器本身及其应用两个角度出发,介绍了相关的研究工作,分析了系统特点和面临的挑战,并展望其未来的发展方向.

摘要:随着软件产业的迅速发展,软件产品的版权保护已成为一个十分重要的问题.详细介绍了软件水印这种新兴软件版权保护技术,深入分析了软件水印的现状、分类、攻击方法以及已有的各种算法,并分别讨论了这些算法的利弊,最后提出软件水印的下一步发展方向.

摘要:通信子系统对并行系统的计算效率有重要影响,大规模应用对并行平台的通信性能和可用性提出了挑战性的要求.多通道通信技术通过并行采用多路网络链路互连来提高并行系统通信性能和可用性.首先分析了多进程复用网络对通信性能的影响,然后以Myrinet/GM网络平台为基础,提出了基于网络接口层的通信链路动态选择与分配策略,设计和实现了支持多路Myrinet网络并行通信的协议层MNC.MNC支持通信进程平等,充分地利用多路Myrinet网络链路资源.在使用2路Myrinet互连的PC机群平台上,MNC进程间通信带宽相对于单链路提高了约34%,有效地提高了应用层通信性能.

摘要:Virtual interface architecture(VIA)建立了一种低延迟、高带宽的通信模型,定义了集群系统中用户层高性能通信规范的标准.通过分析VIA的进展、原理及当前的实现,在Myrinet上设计并实现了一个符合VIA规范的高性能用户层通信软件MyVIA.首先定义了MyVIA的设计原理和框架;然后针对MyVIA实现的不同层次,通过与BerkeleyVIA的比较,提出了UTLB、连续物理内存和可变长NIC内存管理、基于资源和DMA chain的流水线处理、物理描述子环和物理描述子动态缓存等多项优化技术.通过性能的分析比较表明,MyVIA发送4KB数据包时的带宽可达到250MB/s,最小单边延迟为8.46(s.与目前其他VIA实现相比,MyVIA的性能有了较为显著的提高.

摘要:随着Internet的发展,应用的数据存储量与其增长速度都相当高,同时数据具有结构化特点,当前的(分布式)文件系统与数据库系统都无法较好地满足这一类需求.提出了一种网络附属对象存储设备模型,利用自身处理器的能力,提供结构化数据的存储/检索接口,消除了传统存储系统的服务器瓶颈问题.同时提出了基于该对象设备的集群存储体系--OStorage.它利用集群网络方式,实现了数据/元数据统一存储与查询式数据访问机制.其在系统的可扩展性、可用性与对结构化数据的支持上,均较符合当前存储应用的特点.实现了该体系的原型系统.测试结果表明,其吞吐率随规模的扩大呈线性增长.

摘要:把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|²).

摘要:提出一种面向区分服务网络确保转发的覆盖式拥塞管理方案,基本思想是利用控制分组在网络的入口和出口节点之间传递网络服务质量的状态信息,入口节点利用加性增加和显性降低的算法调节聚集通信量的发送速率.实验结果表明,与标准的区分服务网络相比,该方案能在聚集之间公平地分配带宽并能显著地降低分组丢失率.