多核CPU-GPU协同的并行深度优先算法

针对多核CPU和GPU环境下图的深度优先搜索问题,提出多核CPU中实现并行DFS的新算法,通过有效利用内存带宽来提高性能,且当图增大时优势越明显.在此基础上提出一种混合方法,为DFS每一分支动态地选择最佳的实现:顺序执行;两种不同算法的多核执行;GPU执行.混合算法为每种大小的图提供相对更好的性能,且能避免高直径图上的最坏情况.通过比较多CPU和GPU系统,分析底层架构对DFS性能的影响.实验结果表明,一个高端single-socket GPU系统的DFS执行性能相当于一个高端4-socket CPU系统.     

基于gSpan的数据筛选算法研究与应用*

针对图结构数据库中如何实现图结构的快速有效检索问题,提出了一种新的数据筛选算法。它在gSpan算法原理的基础上引入了新的剪枝规则,修改了DFS编码的形式。其次利用改进后的gSpan挖掘出频繁图结构的DFS编码,以此建立索引并对图结构分类。最后将新算法应用于化学数据库,实验结果证明了该算法的正确性和高效性。     

基于图形几何特征相似度的点阵比较

在工程实践中，需要从具有多个相似点阵的已知点阵（Spot Array）集[S]中匹配出一个与未知点阵[P]最相似的点阵[P*]，然后对两个点阵做样本点匹配。完成这个任务的关键挑战在于如何匹配出与未知点阵[P]最相似的已知点阵[P*]。这个问题比较新颖，目前少有理论研究，文中探索出一种基于图形的几何特征分析的描述算法，算法首先将每个点阵构建成一个唯一的简单图（Simple Graph）轮廓图形，同时为每个图形构建一个链式结构，然后利用轮廓图形的几何特征计算未知点阵与各已知点阵的相似程度，匹配出相似度最高的一个，最后利用链式结构完成两个点阵间的样本点匹配。该算法不受点阵的坐标系旋转和尺度缩放的影响。通过实验表明，该算法能够快速、准确地完成点阵相似度比较和样本点匹配任务。     

构造标定自动机实现数字图像的Freeman链编码标定

图像的Freeman链编码是对图像边界的描述，这种链编码给我们图形一些基本特征，正在被广泛地应用到图像处理和图像识别中。本文给出了二值图像区域的标定方法。对于八近邻的图像，分别建立了一组最小的完备图。利用图像标定的基本图，为二值图像边界的识别构造了一个自动机，自动机的输出就是Freeman链编码，为二值图像区域的标定提供了一个有效算法。     

全景视频最小变形双极方形映射研究

球面全景视频映射为矩形视频后才能使用现有编码标准进行编码.针对映射过程中存在内容变形和数据冗余的问题,提出一种最小变形双极方形映射(Minimize Deformation Bipolar Square Projection,MDBSP)算法.算法分三步:将球面按纬度展开成一个等面积的、边界与纬度呈余弦关系的平面图形;用两个三角形和一个矩形组成的多边形近似该平面图形,并使变形度最小;将多边形内像素重排列成一个矩形.实验结果表明,MDBSP算法能有效解决内容变形和数据冗余的问题,压缩效率比经纬图映射提高17.48％.     

异构图形数据的近似语义匹配技术研究

以流程工厂协同设计应用为背景,提出基于允许误差的最大语义图匹配（MSMGE）算法的异构图形数据近似语义匹配模型。利用类无向图来描述2D和3D异构图形数据的工程属性和拓扑关系,消除了图形信息的异构性,并建立各种类实体的属性标签词典来消除2D和3D属性信息的异构性,用语义表达式来表示类无向图顶点和边的语义关系,将异构图形匹配转化为近似语义图匹配。通过基于工程语义对类无向图进行语义分割和基于最大公共序列算法的语义表达式比较、语义规整和语义裁剪等方法,降低了匹配搜索空间,提高了近似语义图匹配效率,实现了近似语义图匹配判断。该研究已经在流程工厂设计软件中得到较好地应用。     

帧内微块复制的屏幕图像编码算法

针对现有的帧内块复制（IBC）算法不能很好地适应屏幕图像具有各种不同大小和形状样图的问题，为了进一步提高屏幕图像的编码效率，提出了一种帧内微块复制（IMBC）算法。该算法首先将当前编码单元（CU）划分成L个微块。然后以每个微块作为最小的匹配和复制单元，采用匹配微块组选择算法，在参考像素集合R中找到与当前微块最匹配的“参考微块”。用L个位移矢量（DV）来表示“参考微块”所在位置与当前CU所在位置的位移关系。最后，对L个位移矢量应用预测算法以消除位移矢量之间的相关性后进行熵编码。对于屏幕图像标准测试数据集合中的视频序列，IMBC算法与IBC算法相比，在编码复杂度增加较低的前提下，在全帧内（AI）、随机接入（RA）、低延迟（LB）三种编码配置中，有损BD-rate降低率分别达3.4%、2.9%、2.6%，无损Bit-rate降低率分别达9.5%、5.2%、5.1%，能有效提高屏幕图像的编码效率。     

基于图像块动态调整的码字内再匹配矢量量化

提出一种基于图像块动态调整的码字内再匹配矢量量化方法。该方法在编码前，首先分析待编码子图像与其八邻域子图像的相似性，通过给定的阈值判断是否相似，如果相似，则用同一个码字编码；否则就单独编码。在编码时，由于匹配码字只是和子图像整体上失真度最小，所以进一步把子图像和匹配码字划分为小块，然后子图像中的每一小块在匹配码字中再匹配。实验结果表明，相对于普通矢量量化，该方法不但可以提高编码速度，而且图像质量也有明显改善。     

手绘草图识别方法研究

提出了一种手绘草图图形识别的解决方法。该方法将不同复杂层次的草图结构抽象为空间关系图，并在图匹配计算过程中引入约束部分枚举方法，智能地预测匹配的有效状态，缩小了空间关系图匹配过程中状态搜索空间。实验表明该方法取得了较好的效果。     

基于IFS理论的快速图象编码和解码算法

分形图象编码法具有高压缩比、高图象品质等显著优点，但其编码时间太长。文中提出的快速编码算法，用偏差图导出距离度量，用二叉树和链表结构进行搜索匹配，可使编码速度提高几十倍乃至百倍。同时，用偏差图进行解码迭代，可使解码过程加速，而还原图象质量不变。     

图同构的矩阵初等变换判定及算法设计

判断图同构的一种有用的方法是对图的邻接矩阵进行初等变换,变成另一个图的邻接矩阵。不幸的是,当初等变换后两个矩阵不能相等时,并不能说明两个图不同构,因为可能存在另一种变换途径,使得两个矩阵相等。另一方面,这种穷尽变换途径的方法有n!种可能(n为图的顶点个数);当n太大时,尝试每一种可能来说明两个图是否同构是不可行的,是一个NP难问题。文章提出了一个简单有效的判断图同构的方法。首先,利用邻接矩阵生成行码距异或矩阵和行码距同或矩阵;其次,寻找邻接矩阵、行码距异或矩阵、行码距同或矩阵间保持行元素一样的行-行置换;如果这种置换存在,则图同构,否则不同构。最后,根据行-行置换确定出同构函数,它给出了两个图的顶点间具有保持相邻关系的一一对应。     

一种多到一子图同构检测方法

提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS 编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.     

图同构的一个充分必要条件

图同构的判定性问题是图论理论中的一个难问题,至今没有得到彻底解决。Ulam曾经提出过一个判定图同构的猜想,也称为图的重构猜想。提出了一个新的判定图同构的充分必要条件,即在子图同构的前提下,根据新增顶点及相应关联边的关系,判断母图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用数学归纳法证明了这个充分必要条件的成立。     

求解图同构的判定算法

图同构的判定性问题是图论理论中的一个难题,至今没有得到彻底解决。受Ulam猜想的启发,提出了一个新的判定图同构的充分必要条件:在子图同构的前提下,根据新增顶点及相应关联边的关系,利用子图同构函数,判断父图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用反证法证明了这个充分必要条件的成立。设计并实现了图同构的一个判定算法,通过实例验证了算法的正确性和有效性。     

Graph isomorphism and identification matrices: parallel algorithms

In this paper, we explore some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a famous open problem. We show that, given two graphs in the form of a certain identification matrix, isomorphism can be tested efficiently in parallel if at least one matrix satisfies the circular 1s property, and more efficiently in parallel if at least one matrix satisfies the consecutive 1s property. Graphs which have identification matrices satisfying the consecutive 1s property include, among others, proper interval graphs and doubly convex bipartite graphs. The result presented here substantially broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms     

Isomorphism identification for epicyclic gear mechanism based on mapping property and ant algorithm

To achieve computer-aided design for mechanism, one method that can be applied is graph theory. During the process of kinematic structure enumeration using graph theory, isomorphism identification of graphs is an important and complicated problem. The problem is known to be NP-complete problem. It is very important to improve the isomorphism identification efficiency and reliability. The objective of this research work is to use ant algorithm to improve the isomorphism identification efficiency and reliability for epicyclic gear mechanism. Based on mapping property between graphs, the isomorphism identification problem can be changed into a matrix operation problem. Two graphs must be isomorphism if the two matrixes of the two graphs can be exactly by exchanging their certain rows and columns, whereas show the two graphs must be non-isomorphic. A mixed model was developed for isomorphism identification by integrating the ant algorithm and mapping property between graphs. The gratifying results can be achieved while parameters are selected in appropriate situation by using the model. Finally, a computer program has been developed in Visual C++. Some examples confirm the validity of the model. The work will be a reliable isomorphism identification algorithm for intelligent CAD of epicyclic gear mechanism.     

并行图论算法研究进展

在这篇综述文章中，我们将重点介绍并行图论处近年来的发展概况及主要成果，并给出一些可能的发展方向。具体内容包括：基于共享存储模型上的图搜索技术、连发支及最小生成树算法、增值并行图论算法、最短路径算法、极大独立集算法、极大匹配与最大匹配算法，图着色算法、求欧拉回路及哈密尔顿回路算法，图同构算法、图Ｋ连通算法以及最大流最小割算法等。     

CoSy C语言编译器安全性研究

为验证CoSy编译器的安全性,并确定不安全因素大致出现的位置,提出一种通过控制流图的同构对比判定CoSy编译器是否安全的方法。该方法生成源程序的控制流图以及CoSy中级中间表示的控制流图后,生成由CoSy编译器产生的目标汇编码的控制流图,根据控制流图同构算法,判断控制流图是否同构,由此确定CoSy编译器的不安全因素发生在编译器的前端还是后端。实验结果表明,该方法能有效验证编译器的安全性。     

不确定图间α-β子图同构匹配算法

子图查询返回图数据集合中所有包含查询图的数据图。在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义。不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量。文章详细阐述了α-β子图同构匹配的语义特点,分析了其和期望子图同构的联系和差别,设计实现α-β子图同构匹配判定算法。     

NODAR: mining globally distributed substructures from a single labeled graph

Data mining in structured and semi-structured data focuses on frequent data values. However, in graph data mining, the focus is on common specific topologies. Graph mining, although its ubiquity, is a difficult task since it requires subgraph isomorphism which is known to be NP-complete. In order to effectively prune the search space and thereby save computational time, a graph mining algorithm requires that the support measure of a pattern to be no greater than that of its subpatterns. This property of the support measure is referred to in the literature as the down-closure, anti-monotonicity or admissibility. Unfortunately, when mining a single labeled graph, simply counting the occurrences of a graph pattern may not have the down-closure property. For this, most existing approaches mine frequent substructures in a set of labeled graphs (called also the transactional setting) and few efforts have been devoted to mining frequent globally distributed substructures in a single labeled graph. In this paper, we propose a graph mining algorithm, called NODAR(Non-Overlapping embeDding based grAph mineR), for computing common and globally distributed substructures in a single labeled graph. NODAR adopts the Depth-First Search (DFS) strategy and is based on the SMNOES (Size of Maximum Non Overlapping Embedding Set) as support measure. The core idea of NODAR is to automatically extract frequent subpatterns; and thus without frequency computation thanks to the down-closure property of SMNOES. By adopting this strategy in the computation of frequent substructures, NODAR reduces the number of subgraph isomorphism tests needed to compute pattern frequencies. Experimental results on monograph and transactional graph databases; and comparison with well-known probabilistic and exact algorithms; prove the efficacy of NODAR.