Extracting multiple layers from data having graph structures

Much data such as geometric image data and drawings have graph structures. Such data are called graph structured data. In order to manage efficiently such graph structured data, we need to analyze and abstract graph structures of such data. The purpose of this paper is to find knowledge representations which indicate plural abstractions of graph structured data. Firstly, we introduce a term graph as a graph pattern having structural variables, and a substitution over term graphs which is graph rewriting system. Next, for a graph G, we define a multiple layer (g, (θ1,…,θk)) of G as a pair of a term graph g and a list of k substitutions θ1,…,θk such that G can be obtained from g by applying substitutions θ1…,θk to g. In the same way, for a set S of graphs, we also define a multiple layer for S as a pair (D,Θ) of a set D of term graphs and a list Θ of substitutions. Secondly, for a graph G and a set S of graphs, we present effective algorithms for extracting minimal multiple layers of G and S which give us stratifying abstractions of G and S, respectively. Finally, we report experimental results obtained by applying our algorithms to both artificial data and drawings of power plants which are real world data.     

Extracting multiple layers from data having graph structures

Much data such as geometric image data and drawings have graph structures.Such data are called graph structured data. In order to manage efficiently such graph structured data, we need to analyze and abstract graph structures of such data. The purpose of this paper is to find knowledge representations which indicate plural abstractions of graph structured data. Firstly, we introduce a term graph as a graph pattern having structural variables, and a substitution over term graphs which is graph we also define a multiple layer for S as a pair (D,O) of a set D of term graphs and a list of substitutions. Secondly, for a graph G and a set S of graphs, we present effective algorithms for extracting minimal multiple layers of G and S which give us stratifying abstractions of G and S, respectively. Finally, we report experimental results obtained by applying our algorithms to both artificial data and drawings of power plants which are real world data.     

Algorithm of graph isomorphism with threedimensional DNA graph structures

ResearchonDNAcomputingwasinitializedin1994 ,whenAdleman[1] proposedamethodofsolvingasmallinstanceoftheHamiltonianPathproblembyalaboratoryexperimentinvolvingDNAmolecules .Later,Lipton[2 ] demonstratedhowalargeclassofNP completeproblemscouldbesolvedbyencodingtheprobleminDNAmolecules .Inparticular ,LiptonshowedonefamousNP problem ,theso called“satisfiability”problem (SAT)andsubsequentlytheotherNP problemscouldbeencodedandsolvedusingmolecules .TheadvantagesofDNAcomputingareitsmassivepa…     

A Graph Drawing Algorithm for Visualizing Multivariate Categorical Data

In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify patterns, trends and relationship within the data. A mathematical model for the graph layout problem is deduced and a spectral graph drawing algorithm for visualizing multivariate categorical data is proposed. The experiments show that the drawings by the algorithm well capture the structures of multivariate categorical data and the computing speed is fast.     

模式识别中的图结构描述方法综述

从概率图、组合图、代数图和几何图等模型角度综述模式识别中图结构的描述.分别讲述每一类图模型的图结构构建形式和计算方式,回顾其起源,归纳其历史发展过程,分析其研究现状.其中,着重论述各类图模型描述的不同特点和潜在关系,剖析未来发展方向.引用基于图模型的模式识别发展史上具有代表性的论著,介绍引领方向的研究学者,旨在帮助读者理清图模型的发展脉络,把握其前沿动态.     

基于内存计算的大规模图数据管理研究

图是一种重要的数据模型,能够描述结构化的信息,在诸如交通网络、社交网络、Web页面链接关系等领域应用广泛,因而获得了广泛的研究.海量的图数据管理对传统的图分析处理技术提出了挑战,分布式集群计算为大规模图数据分析提供了基础平台.随着计算机硬件性价比的大幅提升以及高性能应用需求,基于内存计算的海量数据处理技术获得了业界青睐.图数据高效存储和计算与内存计算密切相关,在此背景下,文章综述了大规模图数据处理相关技术进展,研究了典型的基于内存计算的大规模图数据管理系统,最后总结了基于内存计算的图数据管理的关键点.     

基于GIS的图形数据格式一体化转换技术

开发了基于GIS的地形符号设计和绘制软件,使地形图符号具有图形和属性两个特征,经过适当的整理加工,实现图形数据一体化转换,建立GIS数据库,提出了在GIS的各种软件中有效集成应用CAD等模型各种数据的解决方案,并且着重在点状符号、线状符号和面状符号的符号显示,以及地理要素与符号库的连接及匹配的问题做了重点阐述.     

基于半完全图在数据融合中的元搜索研究

基于对Web图的特性和性质的介绍,探讨了一个Web演化生成的模型;论述了结舍Web图论以及社会网络分析等思想,在研究Web上的搜索引擎中的应用,从社会选择理论提出了基于半完全图的融合模型,并结合堆排序给出了一个高效的元搜索融合算法,并且和其他融合算法做了一定比较,发现半完全图融合这一方法的性能最好。     

A graph based sliding window multi join over data stream

Join operation is a critical problem when dealing with sliding window over data streams. There have been many optimization strategies for sliding window join in the literature, but a simple heuristic is always used for selecting the join sequence of many sliding windows, which is ineffectively. The graphbased approach is proposed to process the problem. The sliding window join model is introduced primarily. In this model vertex represent join operator and edge indicated the join relationship among sliding windows. Vertex weight and edge weight represent the cost of join and the reciprocity of join operators respectively. Then good query plan with minimal cost can be found in the model. Thus a complete join algorithm combining setting up model, finding optimal query plan and executing query plan is shown. Experiments show that the graphbased approach is feasible and can work better in above environment     

Constructing three-dimension space graph for outlier detection algorithms in data mining

Outlier detection has very important applied value in data mining literature. Different outlier detection algorithms based on distinct theories have different definitions and mining processes. The three-dimensional space graph for constructing applied algorithms and an improved GridOf algorithm were proposed in terms of analyzing the existing outlier detection algorithms from criterion and theory.     

一种基于频繁模式有向无环图的数据流频繁模式挖掘算法

频繁模式挖掘中基于FP-growth的算法需要扫描两次事务数据库,预先给定支持度,且不支持时间敏感型数据。本文提出了一种基于频繁模式有向无环图的数据流频繁模式挖掘算法,它根据事务到来的时间给每个事务一个序号,每个事务中的数据项在存储前按数据项的顺序进行调整,频繁模式有向无环图的构建遵循这个顺序并用序号来记录事务与数据项的包含关系,模式增长过程只需要增加有向边上的序号。通过逆向遍历带有相同序号的有向边,产生条件模式基,根据动态定义的阈值抽取条件模式基信息,一次扫描数据库得到频繁模式。实验结果表明,本文算法的执行效率优于FP-growth算法,且存储节点的数目明显减少。     

多元数据的复系数星座图及其优化方法

星座图是多元数据可视化的一种常用方法,具有直观、形象的特点,可以通过调整权系数来对数据进行交互式挖掘.但是传统的星座图缺乏自动调整权系数的较好方法,因而限制了其在可视化数据分析和模式识别的进一步应用.本文将传统的实系数星座图推广为复系数星座图,并且提出了基于复线性判别分析算法对星座图权系数进行自动优化的方法.对4个数据集的实验结果表明,复系数星座图可以较好地表达高维数据的结构关系,并且可以和有关机器算法结合对数据进行可视化分析.     

基于有向图的管线网GIS一体化数据模型

针对城市管线网GIS领域特色，引入图论代数相关理论、改进GIS现有网络结构模型组织与表达，提出城市管线网GIS一体化空间数据模型，并实现该模型支持下的强大的地理计算和空间分析功能，最后在“数字城市”管线网GIS共享集成平台和专业管线GIS系统中实现了模型的功能应用。     

基于带权有向图的网格工作流数据传输策略

针对网格中数据传输忽略网络状况的问题，提出了一种基于带权有向图的网格工作流数据传输策略．该策略针对不同数据处理率的网格工作流作业，首先根据网格内各结点之间的带宽，然后选择合适的数据传输方式，计算出两点之间的权重从而生成一个带权有向图．最后从图中选出最佳的传输路径进行数据传输，从而提高了工作流的执行性能．实验证明了在网络结构及传输速度一定时，该策略的数据传输性能优于传统的利用GridFTP直接传送的数据传输方法。     

基于D-S证据理论的多源遥感图像目标数据联合关联算法

以遥感图像目标识别结果为主,结合卡尔曼滤波器获得的目标运动状态估计结果,提出一种基于D-S证据理论的目标数据联合关联算法.蒙特卡罗模拟实验结果表明,该方法稳定性较强,适合于对海上船舶等遥感图像目标的持续跟踪.     

基于多数据源的分类规则融合方法

探讨基于粗糙集的分类规则挖掘技术,提出一种融合不同数据源中的分类规则的方法.该方法能保证规则的完整性,即获得适用于全局的所有分类规则,并通过实验进行验证,结果表明该融合方法与直接在全局数据中挖掘分类规则的方法相比,具有运算量小、效率高的优势.针对大规模数据在分类求解中出现的过融合问题,应用剪枝策略进行实验,实验结果表明该剪枝策略正确可行,可以提高分类效果.     

数据结构在液压集成块孔道校验中的运用

基于集成块上空间孔系是否发生干涉的几何条件，文中介绍了一种运用数据结构校验空间孔系的算法，此算法有助于减轻设计人员的劳动强度。     

A graph theory model using human nature structure

A graph theory model of the human nature structure ( GMH ) for machine vision and image/graphics processing is described in this paper.Independent from the motion and deformation of con-tours, the human nature structure (HNS) embodies the most basic movement characteristics of the body.The human body can be divided into basic units like head, torso, and limbs.Using these basic units, a graph theory model for the HNS can be constructed.GMH provides a basic model for human posture processing, and the outline in the perspective projection plane is the body contour of an image.In addition, the GMH can be applied to articulated motion and deformable objects, e.g., in the design and analysis of body posture, by modifying mapping parameters of the GMH.     

具有动态拓扑有领航者的多智能体群集运动控制

对具有二次积分的动态多移动智能体在动态拓扑下跟随领航者取得群集运动编队进行了研究.引入了光滑的邻接矩阵以及光滑的势场函数,提出了多移动智能体群集运动的光滑控制器设计方法,运用现有群集运动理论和经典的李雅普诺夫稳定性理论,证明了多移动智能体系统群集运动的稳定性.分析表明:智能体网络在切换的情况下,该方案设计得到的控制输出仍然是光滑的,最终智能体群在领航者的带领下取得群集运动.计算机仿真实例验证了所得结论.     

一种具有缺失数据的贝叶斯网络结构学习方法

在数据缺失的情况下,文章建立的贝叶斯网络结构学习方法BC-ISOR基于界定折叠方法进行变量集联合概率的估计,基于依赖分析的基本思想进行贝叶斯网络的结构学习。该方法的概率估计与数据的缺失率无关,并有效降低了条件独立性检验的次数和阶数,因而具有良好的学习效率并能避免陷入局部最优;针对Asia网络的实验结果表明,该方法比经典方法SEM具有更好地时效性和精确性。