基于概念R-MUPS的本体调试方法

通过定义不可满足概念间的覆盖关系,发现MUPS和MIPS之间的内在关联,从而引出不可满足概念的R-MUPS;给出并证明不一致本体术语集中至少存在一个不可满足概念的R-MUPS就是该术语集的MIPS;利用这一结论,提出基于有序标签演算的R-MUPS算法,采用深度优先遍历原则合并分支计算R-MUPS,同时缓存覆盖概念集合,加快MIPS的求解,实现本体调试.通过概念扩展树与概念R-MUPS算法的等价性,证明算法的正确性并分析其复杂度.最后,利用自动生成本体、现实本体及其扩建本体的数据进行全面测试.实验结果表明:基于R-MUPS的MIPS求解方法能够高效、准确地完成本体调试任务.     

求解极小SMT不可满足子式的宽度优先搜索算法

极小不可满足子式能够为可满足性模理论(SMT)公式的不可满足的原因提供精确的解释,帮助自动化工具迅速定位错误.针对极小SMT不可满足子式的求解问题,提出了SMT公式搜索树及其3类结点的概念,并给出了不可满足子式、极小不可满足子式与3类结点之间的映射关系.基于这种映射关系,采用宽度优先的搜索策略提出了宽度优先搜索的极小SMT不可满足子式求解算法.基于业界公认的SMT Competition 2007测试集进行实验的结果表明,该算法能够有效地求解极小不可满足子式.     

Pellet本体概念分类算法优化

针对Pellet1.4(简称Pellet)推理机的本体概念分类算法效率较低,为了通过减少调用ABOX推理概念间包含关系来提高分类性能,提出了一种全局标记方法.方法首先对所有节点嵌入一个二维散列mark,用于节点存储与其他节点的包含关系标记.然后在推理过程中通过ABOX的推理结果.动态修改相关节点中mark的标记信息.最后充分利用以前的推理结果所修改的标记信息来减少ABOX一致性检测次数.通过使用全局标记方法的算法替代Pellet推理机中原有概念分类算法对实际本体分类进行仿真,实验结果表明该方法可以有效地减少调用ABOX执行一致性检测次数,提高本体概念分类性能.     

针对MUS求解问题的加强剪枝策略

极小不可满足子集(minimal unsatisfiable subsets, MUS)的求解是布尔可满足性问题中的一个重要子问题. 对于一个给定的不可满足问题, 其MUS的求解能够反映出问题中导致其不可满足的关键原因. 然而, MUS的求解是一项极其耗时的任务, 不同的剪枝过程将直接影响到搜索空间的大小、算法的迭代次数, 从而影响算法的求解效率. 提出一种针对MUS求解的加强剪枝策略ABC (accelerating by critical MSS), 依据MSS、MCS、MUS这3者之间的对偶性和碰集关系特点, 提出cMSS和subMUS概念, 并总结出4条性质, 即每个MUS必是subMUS的超集, 进而在避免对MCS的碰集进行求解的情况下有效利用MUS和MCS互为碰集的特征, 有效避免求解碰集时的时间开销. 当subMUS不可满足时, 则subMUS是唯一的MUS, 算法将提前结束执行; 当subMUS可满足时, 则剪枝掉此节点, 进而有效避免对求解空间中的冗余空间进行搜索. 同时, 通过理论证明ABC策略的有效性, 并将其应用于目前最高效的单一化模型算法MARCO和双模型算法MARCO-MAM, 在标准测试用例下的实验结果表明, 该策略可以有效地对搜索空间进行进一步剪枝, 从而提高MUS的枚举效率.     

基于悖论证明与局部搜索的不可满足子式求解算法

随着软硬件设计规模日益增加,功能越来越复杂,功能验证与调试在整个设计周期中占有的比重越来越大,迫切需要高效的方法诊断与定位设计中的错误,而求解不可满足子式可以显著提高自动化工具定位错误的效率.近年来,求解不可满足子式的算法多是基于DPLL(Davis-Putnam-Logemann-Loveland)回溯搜索过程的完全算法,很少有研究涉及到不完全方法.文中针对求解不可满足子式的不完全方法,提出了悖论证明与悖论解析树的概念,并提出一种启发式局部搜索算法,从布尔公式的悖论证明中求解不可满足子式.算法首先采用融合了布尔推理技术、动态剪枝方法及蕴含消除方法的局部搜索过程,逐步构建悖论证明所对应的悖论解析树;然后调用递归函数搜索悖论解析树,最终得到不可满足子式.基于实际测试集与随机测试集进行了实验对比,结果表明文中提出的算法优于同类算法,而且动态剪枝与蕴含消除技术能够有效地减少存储空间及运行时间.     

基于否证蕴含的极小一阶不可满足子式求解算法

解释公式不可满足的原因在软件分析与验证等众多领域都具有非常重要的理论与应用价值,而极小不可满足子公式能够为公式不可满足的原因提供精炼的解释,帮助应用领域的自动化工具迅速定位错误,准确地诊断问题失败的本质缘由.文中针对极小一阶不可满足子式的求解问题,引入了否证蕴含图及其正向与逆向可达结点的概念,并证明了不可满足子式与否证蕴含图之间的关系.基于二者的关系,提出了基于冲突分析与否证蕴含的极小一阶不可满足子式求解算法,并融合了蕴含图剪枝技术,以提高算法效率.通过实验与当前最优的深度优先搜索算法进行了比较,结果表明:文中的算法显著优于深度优先搜索算法,并且随着公式复杂度的增加,性能优势更加明显.     

半扩展规则下分解的定理证明方法

基于扩展规则的定理证明方法在一定意义上是与归结原理对偶的方法,通过子句集能否推导出所有极大项来判定可满足性.IER(improved extension rule)算法是不完备的算法,在判定子句集子空间不可满足时,并不能判定子句集的满足性,算法还需重新调用ER(extension rule)算法,降低了算法的求解效率.通过对子句集的极大项空间的研究,给出了子句集的极大项空间分解后子空间的求解方法.通过对扩展规则的研究,给出了极大项部分空间可满足性判定方法PSER(partial semi-extension rule).在IER算法判定子空间不可满足时,可以调用PSER算法判定子空间对应的补空间的可满足性,从而得到子句集的可满足性,避免了不能判定极大项子空间可满足性时需重新调用ER算法的缺点,使得IER算法更完备.在此基础上,还提出DPSER(degree partial semi-extension rule)定理证明方法.实验结果表明:所提出的DPSER和IPSER的执行效率较基于归结的有向归结算法DR、IER及NER算法有明显的提高.     

基于本体分割的语义图概要方法

语义图概要的目的是提取语义图的关键信息,形成原数据集的概要模型以解决大规模语义图的理解、查询、应用难题。为提升现有语义图概要方法效率,提出一种基于本体分割的概要方法。通过本体分割算法对语义图进行分割生成扩展子图。采用形式概念分析对每个扩展子图生成元素的偏序格（又称特征集格）。在此基础上,由所有子图的特征集格形成了原语义图的概要。在关联开放数据集和Berlin SPARQL Benchmark数据集上的实验结果表明,该方法具有较好的可扩展性,有效提高了概要方法的效率。     

一种基于任务分解的多知识库协同求解专家系统

针对特定领域的知识特点、知识表示方法及采用的推理模型,提出一种基于产生式规则的多知识库专家系统.该系统改进传统专家系统的框架设计,根据求解问题的类别划分将知识库分解成相应的子知识库,再将子知识库的知识规则按知识表示的深度加以分解,建立反映专家经验知识的浅层知识库和原理性知识的深层知识库.系统采用主推理机和从推理机二级推理方式,不同的子知识库采用相应的从推理机.从而任务单一,搜索范围减小,能快速形成待检目标集.主从推理机制与正反向推理结合,提高系统的推理效率.运用该系统模型建造的农业领域专家系统实例,运行效率得到改善,速度显著提高.     

求解连通图关节点的一种新的思考方法

引入图以及图的深度优先搜索数据结构定义,在图的深度优先搜索定义的基础上,讨论了从深度优先搜索定义出发,查找连通图的全部关节点的算法.     

Search-based metamodel matching with structural and syntactic measures

The use of different domain-specific modeling languages and diverse versions of the same modeling language often entails the need to translate models between the different languages and language versions. The first step in establishing a transformation between two languages is to find their corresponding concepts, i.e., finding correspondences between their metamodel elements. Although, metamodels use heterogeneous terminologies and structures, they often still describe similar language concepts. In this paper, we propose to combine structural metrics (e.g., number of properties per concept) and syntactic metrics to generate correspondences between metamodels. Because metamodel matching requires to cope with a huge search space of possible element combinations, we adapted a local and a global metaheuristic search algorithm to find the best set of correspondences between metamodels. The efficiency and effectiveness of our proposal is evaluated on different matching scenarios based on existing benchmarks. In addition, we compared our technique to state-of-the-art ontology matching and model matching approaches.     

Efficient data mining for calling path patterns in GSM networks

In this paper, we explore a new data mining capability that involves mining calling path patterns in global system for mobile communication (GSM) networks. Our proposed method consists of two phases. First, we devise a data structure to convert the original calling paths in the log file into a frequent calling path graph. Second, we design an algorithm to mine the calling path patterns from the frequent calling path graph obtained. By using the frequent calling path graph to mine the calling path patterns, our proposed algorithm does not generate unnecessary candidate patterns and requires less database scans. If the corresponding calling path graph of the GSM network can be fitted in the main memory, our proposed algorithm scans the database only once. Otherwise, the cellular structure of the GSM network is divided into several partitions so that the corresponding calling path sub-graph of each partition can be fitted in the main memory. The number of database scans for this case is equal to the number of partitioned sub-graphs. Therefore, our proposed algorithm is more efficient than the PrefixSpan and a priori-like approaches. The experimental results show that our proposed algorithm outperforms the a priori-like and PrefixSpan approaches by several orders of magnitude.     

投入驱动的存储与计算一体化的事务处理效率优化方法

事务处理技术是报告信息一致性和可靠性的关键技术,决定了Web服务是否可以应用于电子商务。类型化的数据、信息和知识等资源繁杂冗余,导致资源存储和处理效率低下,长事务的处理过程往往会持续较长时间,使得锁定资源的策略不能一直适用,为了协调事务型资源存储和计算代价,提出了一种投入驱动的事务处理方法。从资源建模、资源处理、处理优化和资源管理等角度进行研究,基于对现有知识图谱概念的拓展提出了一种三层可自动抽象调整的解决架构。这个架构包括：数据图谱、信息图谱和知识图谱等三个层面,关键在于对搜索目标资源对象类型转移代价和在资源存储空间上的存储代价的计算,并根据用户投入协同调整搜索目标资源对象的搜索机制和存储方案,从而降低资源搜索的时间复杂度和资源存储的空间复杂度,优化事务处理的时空效率。     

基于最大Code码的极大完全子图算法

本文通过引入极大code码，提出了一种寻找图的极大完全子图的算法FMCSG，该算法用邻接矩阵表示图。在寻找极大完全子图时根据得到的code码及时剪掉非极大code码的子矩阵，从而减少对矩阵的遍历次数，提高了算法的效率。     

基于可满足性模理论的多处理机通信延迟优化任务调度方法

在一组相同处理器上调度带有通信延迟的任务图以实现其最短的执行时间,这在并行计算的调度理论和实践中具有重要的意义。针对具有通信延迟的任务图调度问题,提出一种基于可满足性模理论（SMT）的改进SMT方法。首先,将处理器映射约束和任务执行顺序等约束条件进行编码,将任务图调度问题转化为SMT问题;然后,调用SMT求解器对可行解空间进行搜索,以确定问题最优解。在约束编码阶段,使用整型变量表示任务和处理器的映射关系,从而降低处理器约束编码的复杂程度;在求解器调用阶段,通过添加独立任务的约束条件减小求解器的搜索空间,进一步提升最优解的查找效率。实验结果表明,与原始SMT方法相比,改进SMT方法在20 s和1 min超时实验中的平均求解时间分别减少了65.9%与53.8%,并且在处理器数量较多时取得了更大的效率优势。改进的SMT方法可以有效求解带通信延迟的任务图调度问题,尤其适用于处理器数量较多的调度场景。     

基于软件知识图谱的代码语义标签自动生成方法

开源及企业软件项目和各类软件开发网站上的代码片段是重要的软件开发资源.然而,很多开发者代码搜索需求反映的代码的高层意图和主题难以通过基于代码文本的信息检索技术来实现精准的代码搜索.因此,反映代码整体意图和主题的语义标签对于改进代码搜索、辅助代码理解都具有十分重要的作用.现有的标签生成技术主要面向文本内容或依赖于历史数据,无法满足大范围代码语义标注和辅助搜索、理解的需要.针对这一问题,提出了一种基于知识图谱的代码语义标签自动生成方法KGCodeTagger.该方法通过基于API文档和软件开发问答文本的概念和关系抽取构造软件知识图谱,作为代码语义标签生成的基础.针对给定的代码,该方法识别并抽取出通用API调用或概念提及,并链接到软件知识图谱中的相关概念上.在此基础上,该方法进一步识别与所链接的概念相关的其他概念作为候选,然后按照多样性和代表性排序,产生最终的代码语义标签.通过实验对KGCodeTagger软件知识图谱构建的各个步骤进行了评估,并通过与几个已有的基准方法的比较,对所生成的代码语义标签质量进行了评估.实验结果表明,KGCodeTagger的软件知识图谱构建步骤是合理有效的,该方法所生成的代码语义标签是高质量、有意义的,能够帮助开发人员快速理解代码的意图.     

基于模糊概念图的文档聚类及其在Web中的应用

随着World Wide Web上数据量的日益庞大,现有的搜索引擎已经不能满足用户日益增长的需求.利用数据挖掘技术,提高搜索效率,实现了查询的用户化.首先提出了模糊概念图的模型来描述词语间的关系,然后在聚类过程中引入概念知识,提出了基于模糊概念图的文档聚类算法,通过分析用户的浏览行为发现兴趣模式.在上述技术的基础上,给出了一种用户化的智能搜索系统的实现策略,通过分析概念间的关系和用户的兴趣模式,评价超链/文档和查询的相关程度,从而帮助用户得到更准确的信息.     

Multimedia ontology matching by using visual and textual modalities

Ontologies have been intensively applied for improving multimedia search and retrieval by providing explicit meaning to visual content. Several multimedia ontologies have been recently proposed as knowledge models suitable for narrowing the well known semantic gap and for enabling the semantic interpretation of images. Since these ontologies have been created in different application contexts, establishing links between them, a task known as ontology matching, promises to fully unlock their potential in support of multimedia search and retrieval. This paper proposes and compares empirically two extensional ontology matching techniques applied to an important semantic image retrieval issue: automatically associating common-sense knowledge to multimedia concepts. First, we extend a previously introduced textual concept matching approach to use both textual and visual representation of images. In addition, a novel matching technique based on a multi-modal graph is proposed. We argue that the textual and visual modalities have to be seen as complementary rather than as exclusive sources of extensional information in order to improve the efficiency of the application of an ontology matching approach in the multimedia domain. An experimental evaluation is included in the paper.     

图数据库中的相似性搜索算法研究与应用*

图数据库的相似性搜索是一个非常重要的研究内容,图的相似性匹配属于图同构的判定问题,是NP完全问题,传统的高开销搜索的方法已经不能满足复杂图查询的需要;另外,由于图数据库的复杂性和特殊性,已有的优化算法不能直接使用。为了提高图数据库的搜索效率,提出了一种基于索引的相似性搜索算法,通过数据库中的频繁结构建立特征索引,算法可高效准确地滤除大量的非相似图集合,避免了图之间精确匹配即图同构的计算,最后将本算法应用于化学数据库,实验结果证明了该方法的有效性和可行性。     

基于限界传递相似度图的FCA概念相似度计算方法

使用相似度图计算FCA概念相似度需要构造相似关系的传递闭包,对于复杂问题会导致相似度图规模过大,从而影响相似度评价的效率.为了降低相似度图规模,提出一种基于限界传递相似度图的FCA概念相似度计算方法.该方法首先通过限定传递相似关系的长度来避免构造相似关系的传递闭包,得到的限界传递相似度图中忽略了长度超过界限且对区分FCA概念无用的传递相似关系,能够有效压缩相似度图的规模;然后给出了动态传递相似度计算方法和由限界传递相似度图构建二部图的方法.实验结果表明,使用限界传递相似度图能够在不损失计算结果准确度的情况下有效提高FCA概念相似度计算的效率.