2005, 16(2):165-173.
摘要:软件DSM(distributed shared memory)系统在机群上构造了共享存储编程环境,结合了共享存储的易编程性和机群的可扩展性,引起了广泛的研究.由于软件DSM系统是一个分布式系统,系统失败风险大,需要实现容错技术以促进其实用化.利用用户级检查点技术,在支持域存储一致模型的软件DSM系统JIAJIA的基础上,设计并实现了一个可恢复的高可移植的软件DSM系统JIACKPT(JIAjia with ChecKPoinTing).由于采用适合软件DSM系统的强全局一致状态以及多种优化措施,JIACKPT易于实现且获得很好的性能.在一个8节点的PC机群上的应用测试表明,即使每分钟做一次检查点,大部分应用的检查点开销也小于10%.此外,JIACKPT还具有高可移植性.这些都表明JIACKPT已经成为一个比较实用的系统.
2005, 16(2):174-183.
摘要:阐述了在程序设计语言语法分析器的构造中采用通用LR(generalized LR,简称GLR)分析算法的动机.提出了一个多层次的优化策略,加快了GLR分析器的分析速度.为基本的GLR算法增加了必要的运行时控制机制,以实现语法分析时调用文法规则附带的语义动作,化解输入串的二义性,同时避免GLR分析器可能存在的语义动作延迟问题.优化后的算法已在一个可视化语法分析器自动生成环境VPGE中实现.实验结果表明,在分析确定性的编程语言时,自动生成的GLR分析器的分析速度与自由软件基金会的Bison生成的LALR(1)分析器的分析速度有可比性.
2005, 16(2):184-193.
摘要:知识在多个参与者之间的产生、传播与应用称为知识流.在知识密集型组织中,对业务过程的控制和对知识资产的管理具有紧密的依赖关系.工作流管理是实现业务过程控制的重要技术.当前的工作流过程元模型不支持对知识管理机制的表示.为此,提出了一个扩展的工作流过程元模型,以支持业务过程控制与知识管理的集成.在此基础上,对知识流的建模与控制进行了深入的研究.提出了一种知识流建模方法,通过5类知识流单元对知识传递与重用、人员协作与交流进行表示.针对知识流中的动态因素,研究了基于资源约束、知识需求变化和时间约束的知识流控制方法,以实现自适应的知识流控制,并给出了有关算法.为工作流技术与知识管理技术的有效结合提供了一个有益的途径.
2005, 16(2):194-204.
摘要:由于指导语句动态嵌套与绑定规则的存在,OpenMP程序中线程的一些上下文只能在运行时刻才能完全确定.然而,通过编译时刻的静态分析可以部分确定指导语句的嵌套类型,这些信息可以用于指导后续的编译与优化.由于函数调用的存在,嵌套与绑定常常会跨越过程边界,除了通常的局部和全局分析之外,还需要过程间分析的支持.通过在通常的过程间分析的基础上附加信息,可以使得嵌套类型信息在过程调用图中进行传播.将这些全局信息与过程内的局部信息结合起来,就可以在编译时刻确定语句的嵌套类型.结果表明,编译时刻的嵌套类型分析可以有效地确定通常的科学与工程计算程序中指导语句的嵌套类型,基于嵌套类型的翻译与优化可以同时减少运行时开销和目标代码长度.
2005, 16(2):205-214.
摘要:海量关系中经常存在小值域属性,关系不仅在这些属性上的互不相同的值的数量很小,而且在这些属性的组合上的值域也很小.因此,海量关系在这些属性上有很多重复的组合值.一种提高数据库的存储和查询效率的重要方法就是消除这些重复取值.为此,提出了拆分压缩技术,它将海量关系拆分成两种较小的关系,其中一种关系的属性由小值域属性组组成,而另一种关系的属性是海量关系的其他属性.该方法的关键是小值域属性组的识别问题.在证明了这个问题的NP-完全性后,给出了两种在海量关系中识别小值域属性组合的算法,并在此基础上提出了海量关系拆分压缩技术,讨论了压缩关系的查询处理方法.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并可以提高数据库查询处理的整体性能.
2005, 16(2):215-222.
摘要:最大频繁项集的挖掘过程中,在最小支持度较小的情况下,超集检测是算法的主要耗时操作.提出了最大频繁项集挖掘算法FPMFI(frequent pattern tree for maximal frequent item set)使用基于投影进行超集检测的机制,有效地缩减了超集检测的时间.另外,算法FPMFI通过删除FP子树(conditional frequent pattern tree)的冗余信息,有效地压缩了FP子树的规模,减少了遍历的开销.分析表明,算法FPMFI具有优越性.实验比较说明,在最小支持度较小时,算法FPMFI的性能优于同类算法1倍以上.
2005, 16(2):223-232.
摘要:如何在XML数据流上高效地执行大量的XPath查询成为数据流应用中一个迫切需要解决的关键问题.目前提出的算法或者不能完全支持XPath的常规特性,或者在算法的执行效率和空间代价上不能满足数据流应用的要求.提出了基于树自动机的XEBT机来解决这个问题.与传统方法相比,XEBT机具备如下特征:首先,XEBT机基于表达能力丰富的树自动机,无须附加中间状态,或保存中间结果,就能处理支持{[]}操作符的XPath;其次,XEBT机支持多种优化策略,包括基于DTD的XPath查询自动机的构造;在空间代价有限增加的情况下采用局部确定化减少并发执行的状态;采用自上而下和自下而上相结合的查询处理策略.实验结果表明,提出的方法能够支持复杂的XPath查询,在执行效率和空间代价方面优于传统算法.
2005, 16(2):233-238.
摘要:提出一个结合长期学习的概率检索模型,即通过估算一个动态的用户模型来预测目标图像的概率分布.系统以反馈序列为用户模式,通过与反馈日志中用户模式的匹配,动态地调整对当前用户的预测.与PicHunter传统用户模型相比,此系统基于长期学习的方法,通过对用户反馈的观察,动态地调整当前的用户模型,从而更精确地推断当前用户的反馈行为.对1.1万幅图像数据库的实验表明,与已知方法相比,此方法对检索精度有明显的改善.
2005, 16(2):239-250.
摘要:由IETF最年轻的工作组之一的SIP(session initiation protocol)工作组发布的SIP相关标准已经成为通信和网络界的研究热点.目前SIP工作组发表的协议和草案超过30个,除了核心协议以外,其他协议涵盖QoS、安全、消息头和方法扩展、与PSTN等其他协议的互操作性、穿透防火墙和NAT、应用、多消息体、即时消息等诸多话题,其最终目标是为所有Internet成功的应用提供无所不在的接入,成为联系Internet和电信、多媒体的媒介.对SIP标准中的核心技术和研究进展进行了综述.着重介绍了以上SIP相关标准及应用中的核心技术和相关领域最新的研究动态,并指出了进一步的研究方向和应用前景.
2005, 16(2):251-259.
摘要:路由算法和动态自配置特性是实现大规模基于内容的发布订阅系统的两个关键问题.尽管已经有多种路由算法被提了出来,但是它们没有充分利用组播技术提高系统性能和节省网络带宽;此外,已有系统的网络都是静态的,不能够进行网络的自动配置.首先,提出了具有组播集群的层次性系统模型,设计了混合式路由算法,充分利用物理网络组播的特性,节省网络带宽.然后,提出了组播集群复制协议和基于内容的组播树协议CMTP,分别处理节点或者链路失效导致的网络分割以及路由的重建.实验结果表明,这些算法和协议的引入节省了网络带宽,显著提高了系统的性能,保证了系统的自配置特性.
2005, 16(2):260-275.
摘要:法律界研究计算机证据的有关法律特性及其认定,而计算机科学领域的研究人员则从技术的角度研究计算证据的技术特征及其获取技术.由于这一学科是建立在法学和计算机科学之上的交叉学科,必须从这两个学科及其派生学科上体现出的特殊性的角度对其进行研究.在这一领域把法律和技术分离的做法会导致法律认定上的错误和技术上的无序性.通过将法律和计算机技术相结合对计算机取证进行了研究.阐明了计算机取证的相关法律问题,重点研究了计算机取证的技术方法和工具,并给出了一个计算机取证实验的技术过程.提出了目前计算机取证相关法律法规和计算机取证技术的不足,指出了今后法律法规的进一步健全、计算机取证工作的规范化和计算机取证技术的发展趋势.
2005, 16(2):276-285.
摘要:在现有的单层马尔科夫链异常检测模型基础上,提出一种崭新的两层模型.将性质上有较大差异的两个过程,不同的请求和同一请求内的系统调用序列,分为两层,分别用不同的马尔可夫链来处理.两层结构可以更准确地刻画被保护服务进程的动态行为,因而能较大地提高异常的识别率,降低误警报率.而且异常检测出的异常将被限制在相应的异常真正发生的请求区内.检测模型适合于针对特权进程(特别是基于请求?反应型的特权进程)的异常入侵检测.
2005, 16(2):286-294.
摘要:传统的Poisson统计流量模型对于以突发性流量为基本特征的Internet网络不再适应,而采用更加接近Internet网络流量特征的自相似模型,会具有复杂的建模过程和繁杂的计算.为此,从数据缓冲区占用情况的实时状态出发,运用模糊理论对缓冲区占用率状态这一模糊性问题进行描述,建立起模糊拥塞控制模型,并实现了对拥塞的模糊控制.它对所有到达的数据流按照一定的优先级进行分类,并把全局性缓冲区和各队列的局部性缓冲区按照正常、拥塞避免和拥塞的规则划分为3个具有交叉过渡域的几个阶段,然后采用整体和局部相结合的拥塞控制方法,实现了队列调度过程中的模糊性处理.理论分析和NS实验仿真结果表明,该算法在保证各连接服务的公平性方面,特别是在保护和隔离非拥塞状态的连接上,取得了比传统方法更好的效果,从而更好地改进了路由器或者交换机的拥塞控制性能.
2005, 16(2):295-302.
摘要:检测时无须原始图像的盲数字水印是实用的数字产品版权保护系统和隐蔽通信系统的关键技术之一.理论研究证明,图像的正交投影序列与图像是一一对应的.利用此结论,设计并实现了一种具有良好性能的盲水印检测器.该水印检测器的相关值不是采用像素值信息,而是采用图像的正交投影序列来计算的.实验结果表明,该水印检测器不仅对旋转、平移攻击有很强的抵抗能力,而且对随机高斯噪声也具有良好的鲁棒性.其性能优于一般的直接利用像素值设计的水印检测器.
2005, 16(2):303-308.
摘要:基于笔式手势的自然交互是支持概念设计创新的有效方式.提出了一种笔式手势的层次概念模型,结合基于约束的自由勾画和上下文感知技术描述了手势设计方式,进一步讨论了手势内部的约束建立和求解算法;基于手势应用的范式,给出了概念设计中特征手势建模的应用实例,通过与传统建模和交互方式的对比,验证了特征手势建模的方便性.给出一个自然、高效的方法,以基于手势的方式来完成概念设计构思过程,采用笔式交互快速自然地记录下设计思路,所实现的系统方便了用户的创新设计,改善了人机交互模式.
2005, 16(2):309-315.
摘要:二维多边形渐变在二维角色动画、模式匹配、几何造型等领域有着重要的应用.已有的方法大多根据多边形的边长、角度、面积、骨架等几何属性来完成多边形之间的最佳对应和渐变,而忽略了多边形的内在视觉特征.提出了一种基于视觉特征对应的2-D多边形渐变方法,该方法把源多边形和目标多边形按照视觉特征进行同构特征分解,得到若干对对应的特征子多边形.在渐变过程中,每个源特征子多边形光滑地过渡到目标特征子多边形.通过引入特征分解点,用户可以灵活和直观地改变特征子多边形,按照预想的效果控制多边形的渐变.实验效果表明,基于特征分解的顶点对应和插值算法不仅可以得到光滑的多边形渐变序列,而且可以实现多边形的特征对应和特征保留.
2005, 16(2):316-323.
摘要:根据汽车内饰等行业需求,对皮制品加工的优化排样问题进行了研究.创新地采用离散化处理方式,同时引进边界约束,使排样过程与皮料和样片的几何信息无关,使用基于顺序的启发式底左布局将样片顺次布置到皮料上,样片的最优布置顺序和角度依靠随机优化算法来实现.设计了简洁、实用的操作算子,并提出了基于模拟退火技术的遗传算法(simulated annealing based genetic algorithm,简称SABGA),该算法在优化搜索中能自适应地控制变异率,使得优化高效地逼近全局最优解.实验及对比结果表明,提出的优化排样方式特别适用于二维不规则形体在多个二维不规则平面上的优化排样.
2005, 16(2):324-326.
摘要:重点项目是国家自然科学基金资助的一种项目类型,它以推动学科发展、促进国民经济与社会的可持续发展为目标,每年年初集中受理一次.介绍了2004年度国家自然科学基金委员会信息科学部计算机科学处重点项目受理及资助情况,给出了评审原则,分析了存在的问题,并针对问题提出了建议.