Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2005年 第42卷 第1期    出版日期:2005-01-15
   下一期
工作流过程建模中的形式化验证技术
周建涛, 史美林, 叶新铭,
2005, 42(1):  1-9. 
摘要 ( 612 )   HTML ( 2)   PDF (510KB) ( 779 )  
相关文章 | 计量指标
工作流过程建模是一个复杂且易错的过程.若过程定义在投入运行之后被发现有错,则修复错误的代价相当高,这个问题引起了研究界和工业界的高度重视.因此,在建模阶段进行有效的过程验证是十分必要的.综述了工作流过程验证技术的发展现状,包括强调验证的重要性,叙述了需要验证的问题和复杂度;介绍了对验证方法的要求;讨论了过程合理性验证和化简验证技术等;并通过对研究现状的分析和对比,提出了仍然没有解决的问题和将来的工作.
论文
VAR-Tree——一种新的高维数据索引结构
董道国 梁刘红 薛向阳
2005, 42(1):  10-17. 
摘要 ( 680 )   HTML ( 1)   PDF (432KB) ( 723 )  
相关文章 | 计量指标
在多媒体信息检索和数据挖掘等应用领域,实现高维矢量的K近邻搜索是非常具有挑战性的研究课题,为此人们提出了很多种索引结构.然而,现有研究成果表明,随着矢量维数的增加,基于树状索引结构的查询性能急剧下降,例如在R-Tree,X-Tree和SS-Tree中都会出现“维数灾难”.为此,又引入近似压缩的思想,即通过压缩数据来减少查询过程中的磁盘读写代价,例如VA-File等,不过,VA-File没有对近似矢量数据做任何的排序或层次处理.提出了一种新的索引结构VAR-Tree,它将VA-File与R-Tree有机结合起来,用R-Tree管理和组织VA-File中的近似数据,并用已提出的R-Tree类相似查询算法实现基于VAR-Tree的查询.实验结果表明,VAR-Tree较好地提高了检索性能.
一种面向混合实时事务调度的并发控制协议
王 强 王宏安 金 宏 付 勇 戴国忠
2005, 42(1):  18-29. 
摘要 ( 401 )   HTML ( 0)   PDF (654KB) ( 451 )  
相关文章 | 计量指标
首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能.进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI.该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率.仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能.
一种基于DTD的XML索引方法
路 燕, 张 亮, 段起阳, 施伯乐,
2005, 42(1):  30-37. 
摘要 ( 451 )   HTML ( 0)   PDF (429KB) ( 508 )  
相关文章 | 计量指标
路径查询是XML查询的一个主要特征,现已提出了多种XML索引方法. DTD的结构信息对于XML索引的建立及查询效率的提高很重要,但现有的大部分索引方法没有利用DTD这一有效资源.提出一种利用DTD的XML索引方法——DBXI(DTD-based XML indexing),该方法采用了新的编码方法,可使路径查询具备如下特征:对于由N个元素/属性组成的具有1个谓词约束的路径表达式,DBXI处理每个XML文档仅需0次或1次元素/属性结点集的结构连接操作;对于在XML文档中不存在匹配结构的路径查询,DBXI能够在比现有的XML索引方法较短的时间内给出无查询结果的判断.实验表明,与Lore,SphinX和XISS等索引方法相比,DBXI能够缩短路径查询的响应时间.
LDPChecker——一个实时和混成系统模型检验工具
裴 玉 李宣东 郑国梁
2005, 42(1):  38-46. 
摘要 ( 563 )   HTML ( 0)   PDF (504KB) ( 534 )  
相关文章 | 计量指标
混成系统是一类复杂系统,线性混成系统作为其重要子类,在形式方法中,人们通常使用线性混成自动机来对它建模.虽然线性混成自动机的模型检验问题总的来说还是不可判定的,但对于其中的正环闭合自动机,其对于线性时段性质的满足性能够通过线性规划方法加以检验.为了实现自动检验正环闭合自动机对线性时段性质的满足性,设计并实现了工具LDPChecker.工具LDPChecker能够识别正环闭合自动机并对其进行相应的检验,其主要特色在于它能够对实时和混成系统检验包含可达性在内的许多实时性质,并且能够自动给出诊断信息.
文本分类中结合评估函数的TEF-WA权值调整技术
唐焕玲, 孙建涛, 陆玉昌,
2005, 42(1):  47-53. 
摘要 ( 554 )   HTML ( 0)   PDF (397KB) ( 592 )  
相关文章 | 计量指标
文本自动分类面临的难题之一是如何从高维的特征空间中选取对文本分类有效的特征,以适应文本分类算法并提高分类精度.针对这一问题,在分析比较特征选择和权值调整对文本分类精度和效率的影响后,提出了一种结合评估函数的TEF-WA权重调整技术,设计了一种新的权重函数,将特征评估函数蕴含到权值函数,按照特征对文本分类的辨别能力调整其在分类器中的贡献.实验结果证明了TEF-WA权值调整技术在提高分类精度和降低算法的时间复杂度方面都是有效的.
论文
BDI模型信念特性研究
刘 勇, 蒲树祯, 程代杰, 曹泽翰,
2005, 42(1):  54-59. 
摘要 ( 787 )   HTML ( 0)   PDF (325KB) ( 476 )  
相关文章 | 计量指标
计算的典型模型是BDI(belief, desire, intention),信念是Agent计算的重要属性.把信念拓展为知识性信念和可实现信念. Agent的知识性信念是指Agent当前具有或掌握的知识,具有知识的进化和继承特性. Agent的可实现信念是指当前不成立而在将来会成立的事情,是Agent被意识到的个性倾向和目标.用非标准世界的模态逻辑为形式化工具描述两种信念,将可能世界的可达关系作为认识的不同阶段和达到可实现信念的不同阶段,避免了“逻辑全知问题”和逻辑蕴涵的副作用问题.可实现信念满足KD公理,知识性信念满足KDT4公理.两种信念适合描述Agent的意识状态和意识模型.
SAT问题中局部搜索法的改进
杨晋吉, 苏开乐,
2005, 42(1):  60-65. 
摘要 ( 584 )   HTML ( 0)   PDF (337KB) ( 401 )  
相关文章 | 计量指标
局部搜索方法在求解SAT问题的高效率使其成为一研究热点.提出用初始概率的方法对局部搜索算法中变量的初始随机指派进行适当的约束.使在局部搜索的开始阶段,可满足的子句数大大增加,减少了翻转的次数,加快了求解的速度.用该方法对目前的一些重要的SAT问题的局部搜索算法(如WSAT,TSAT,NSAT,SDF等)进行改进,通过对不同规模的随机3-SAT问题的实例和一些不同规模的结构性SAT问题的实例,以及利用相变现象构造的难解SAT实例测试表明,改进后的这些局部搜索算法的求解效率有了很大的提高.该方法对其他局部搜索法的改进具有参考价值.
基于最小不确定性神经网络的茶味觉信号识别
王 岩 周春光 黄艳新 丰小月
2005, 42(1):  66-71. 
摘要 ( 419 )   HTML ( 0)   PDF (390KB) ( 398 )  
相关文章 | 计量指标
提出了一种基于最小不确定性神经网络方法的味觉信号识别模型,使用贝叶斯概率理论和粒子群优化算法(PSO),快速而有效地确定网络结构参数,实现了对10种茶味觉信号的识别,实验结果表明了将该模型引入到茶味觉信号识别的可行性和有效性.
基于分段时间弯曲距离的时间序列挖掘
肖 辉 胡运发
2005, 42(1):  72-78. 
摘要 ( 685 )   HTML ( 0)   PDF (472KB) ( 1045 )  
相关文章 | 计量指标
在时间序列库中的数据挖掘是个重要的课题,为了在挖掘的过程中比较序列的相似性,大量的研究都采用了欧氏距离度量或者其变形,但是欧氏距离及其变形对序列在时间轴上的偏移非常敏感.因此,采用了更鲁棒的动态时间弯曲距离,允许序列在时间轴上的弯曲,并且提出了一种新的序列分段方法,在此基础上定义了特征点分段时间弯曲距离.与经典时间弯曲距离相比,大大提高了效率,而且保证了近似的准确性.
一种改进的自适应文本信息过滤模型
马 亮 陈群秀 蔡莲红
2005, 42(1):  79-84. 
摘要 ( 378 )   HTML ( 0)   PDF (342KB) ( 567 )  
相关文章 | 计量指标
自适应信息过滤技术能够帮助用户从Web等信息海洋中获得感兴趣的内容或过滤无关垃圾信息.针对现有自适应过滤系统的不足,提出了一种改进的自适应文本信息过滤模型.模型中提供了两种相关性检索机制,在此基础上改进了反馈算法,并采用了增量训练的思想,对过滤中的自适应学习机制也提出了新的算法.基于本模型的系统在相关领域的国际评测中取得良好成绩.试验数据说明各项改进是有效的,新模型具有更高的性能.
一种实用高效的文本分类算法
王建会, 王洪伟, 申 展, 胡运发,
2005, 42(1):  85-93. 
摘要 ( 544 )   HTML ( 3)   PDF (516KB) ( 795 )  
相关文章 | 计量指标
在模式识别研究领域已有的分类算法中,大多数都是基于向量空间模型的算法,其中使用范围最广的是kNN算法.但是,其中的大多数算法都因为计算复杂度太高而不适用于大规模的场合.而且,当训练样本集增大时都需要重新生成分类器,可扩展性差.为此,提出了互依赖和等效半径的概念,并将两者相结合,提出新的分类算法——基于互依赖和等效半径、易更新的分类算法SECTILE. SECTILE计算复杂度较低,而且扩展性能较好,适用于大规模场合.将SECTILE算法应用于中文文本分类,并与kNN算法和类中心向量法进行比较,结果表明,在提高分类精度的同时,SECTILE还可以大幅度提高分类速度,有利于对大规模信息样本进行实时在线的自动分类.
使用最大熵模型进行中文文本分类
李荣陆 王建会 陈晓云 陶晓鹏 胡运发
2005, 42(1):  94-101. 
摘要 ( 3403 )   HTML ( 25)   PDF (409KB) ( 4097 )  
相关文章 | 计量指标
随着WWW的迅猛发展,文本分类成为处理和组织大量文档数据的关键技术.由于最大熵模型可以综合观察到各种相关或不相关的概率知识,对许多问题的处理都可以达到较好的结果.但是,将最大熵模型应用在文本分类中的研究却非常少,而使用最大熵模型进行中文文本分类的研究尚未见到.使用最大熵模型进行了中文文本分类.通过实验比较和分析了不同的中文文本特征生成方法、不同的特征数目,以及在使用平滑技术的情况下,基于最大熵模型的分类器的分类性能.并且将其和Bayes,KNN,SVM三种典型的文本分类器进行了比较,结果显示它的分类性能胜于Bayes方法,与KNN和SVM方法相当,表明这是一种非常有前途的文本分类方法.
论文
应用于计算机网络协议一致性测试的传输机制
张玉军 李忠诚 郑红霞 田 野 孙静波
2005, 42(1):  102-108. 
摘要 ( 482 )   HTML ( 0)   PDF (327KB) ( 449 )  
相关文章 | 计量指标
测试传输在很大程度上影响测试系统实现和测试集设计.良好的传输方法能够对测试集设计者屏蔽被测协议实现的相关信息,同时简化测试配置.根据测试集设计和测试传输分离的思想,采用通信实体和网络接口相结合的机制实现测试传输,网络接口用于定义逻辑测试接口的类型和相应的参数,相当于一台逻辑测试器;通信实体用于向逻辑测试器屏蔽下层服务提供者的类型,完成测试数据的发送/接收工作.该传输机制在IPv6协议一致性测试系统中获得了成功.
基于Small-World网络的非结构化DHT算法
周 晋 李衍达
2005, 42(1):  109-117. 
摘要 ( 466 )   HTML ( 0)   PDF (528KB) ( 533 )  
相关文章 | 计量指标
目前,非结构化的P2P路由算法面临着搜索效率低下的严峻问题,这严重影响了非结构算法的应用领域.提出一种基于关键字聚类的分布式哈希表算法,主要思路是将环状关键字空间分成上下两层,下层(AUT层)负责关键字管理,上层(HUB层)负责节点路由.每个节点用一个随机数值作为它的聚类中心,从过往的路由消息中本地节点将抽取文件关键字和节点聚类中心,以聚类原则将这些数据记录到本地路由表中.除了改进非结构化算法的数据组织无序性,另一个目标是提高搜索效率.于是,上述算法的增强算法利用了small-world理论,在HUB层中加入远距离节点的聚类中心,将确定性聚类转化为概率性聚类,故能保证路由长度为O(log\+2N).
同构计算环境中一种快速有效的静态任务调度算法
李庆华, 韩建军, Abbas A. Essa,
2005, 42(1):  118-125. 
摘要 ( 404 )   HTML ( 0)   PDF (421KB) ( 482 )  
相关文章 | 计量指标
快速有效的调度任务是多处理器计算环境中的一个关键问题. 目前任务调度算法中刻画任务依赖关系最流行的模型是DAG. 在以前的文献中, 提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境). 延伸了TTIG模型, 并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2). GBHA以组的形式尽量消除图中回路,因而能获得任务图的全局信息,具有更好的调度性能. 在模拟实验中,将此算法与MATE和其他同构环境中基于DAG的有效调度算法,在不同测试条件下进行了比较,结果显示GBHA在性能上明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势.
分布式数据库服务器系统及其自适应配置管理策略
田俊峰, 刘玉玲, 杜瑞忠,
2005, 42(1):  126-133. 
摘要 ( 395 )   HTML ( 0)   PDF (468KB) ( 515 )  
相关文章 | 计量指标
服务器冗余技术在解决传统分布式环境的可用性和性能瓶颈问题的同时,给系统的管理带来了新的挑战.介绍了一种分布式数据库服务器DDSS的构成原理及工作模型.为了解决当前冗余服务系统的配置管理中存在的冗余资源动态可扩展性不强的问题,针对服务器DDSS(模型把系统中的每种服务抽象成为一个对象类,并提出同一个服务对象类的多个实例互为冗余服务),对冗余资源的配置管理问题进行讨论,并提出基于移动代理技术的自适应配置管理ACM(adaptive configuration management)策略,在保证系统可用性的前提下提高系统的性能,减少资源浪费.在ACM中,通过定义奖惩函数(对于静态配置)和用户请求到达率(对于动态配置)来作为配置依据,对冗余实例进行动态增加或删除.最后,对算法的性能进行了分析、测试,并与传统算法进行了比较.
基于遗传算法的B样条曲线和Bézier曲线的最小二乘拟合
周明华, 汪国昭,
2005, 42(1):  134-143. 
摘要 ( 691 )   HTML ( 1)   PDF (590KB) ( 684 )  
相关文章 | 计量指标
考虑用B样条曲线拟合平面有序数据使得最小二乘拟合误差最小.一般有两种考虑,一种是保持B样条基函数的节点不变,选择参数使得拟合较优.参数的选择方法包括均匀取值、累加弦长法、centripetal model、Gauss-Newton迭代法等.另一种则是先确定好参数值(一般用累加弦长法),然后再用某一算法计算出节点,使得拟合较优.同时把两者统一考虑,用遗传算法同时求出参数、节点使得拟合在最小二乘误差意义下最优.与Gauss-Newton迭代法、Piegl算法相比,本方法具有较好的鲁棒性(拟合曲线与初始值无关)、较高的精度及控制顶点少等优点.实验结果说明采用遗传算法得到的曲线逼近效果更好.用遗传算法对Bézier曲线拟合平面有序数据也进行了研究.
建筑工程图识别与理解——模型与算法
路 通 席晓鹏 芮 明 蔡士杰 窦万春
2005, 42(1):  144-152. 
摘要 ( 571 )   HTML ( 1)   PDF (519KB) ( 1077 )  
相关文章 | 计量指标
建筑工程图采用二维示意式表达方式,识别和三维精确还原相对困难.提出了一种基于轴网、结构语义驱动的层次式自生长识别模型(SINEHIR模型),在融合结构语义的基础上从先导建筑构件开始,在削减后的识别空间中结合当前识别层次的特点,分别采用基于特征的建筑符号识别方法、基于符号的轴网识别方法、基于轮廓的结点构件识别方法、基于关联语义的段构件识别方法、基于几何的组合构件识别方法和基于继承的信息传递方法,在模型约束下完成后继识别,以较小的计算量有效排除绘图噪音、提高识别率.
SOC可测试性设计与测试技术
胡 瑜, 韩银和, 李晓维,
2005, 42(1):  153-162. 
摘要 ( 656 )   HTML ( 4)   PDF (488KB) ( 702 )  
相关文章 | 计量指标
超深亚微米工艺和基于芯核的设计给芯片系统(system-on-a-chip,SOC)测试带来了新的问题.对SOC可测试性设计与测试技术的国际研究现状及进展进行了广泛而深入的综述.从芯核级综述了数字逻辑、模拟电路、存储器、处理器4类芯核的可测试性设计与测试技术,从系统级综述了测试激励、测试响应和测试访问机制等SOC测试资源的设计以及压缩/解压缩与测试调度等测试资源划分、优化技术,并介绍了2个标准化组织开展的SOC测试标准工作.最后,展望了SOC测试未来的发展方向.
无线传感器网络研究进展
崔 莉, 鞠海玲, 苗 勇, 李天璞, 刘 巍, 赵泽,
2005, 42(1):  163-174. 
摘要 ( 1032 )   HTML ( 31)   PDF (543KB) ( 2219 )  
相关文章 | 计量指标
无线传感器网络因其巨大的应用前景而受到学术界和工业界越来越广泛的重视.介绍了无线传感器网络的基本概念以及具有应用代表性的研究项目,总结提出了网络协议体系结构框架并简要介绍了各主要研究方向的最新进展,本文还针对最受关注的数据链路层协议、网络层路由协议、协议栈优化、能耗管理以及网络仿真技术等几个研究热点做了比较详细的研究进展综述.