面向模式图变化的增量图模式匹配

在大数据时代,数据图的规模急剧增长,增量图模式匹配算法能够在数据图或模式图发生变化时避免重新在整个数据图上进行匹配、减少响应时间,因此成为了研究的热点.针对实际应用中数据图不变而模式图发生变化的情况,提出了一种面向模式图变化的增量图模式匹配算法PGC_IncGPM,在模式图匹配的过程中记录适当的中间结果作为索引,用于后续的模式匹配.提出了增强的图模式匹配算法GPMS,用于首次整个数据图上的模式匹配.该算法一方面能够建立后续增量匹配所需的索引,另一方面减少了整个数据图匹配的执行时间.设计实现了面向模式图增边和减边的两个核心子算法,通过子算法的组合,能够支持在模式图发生各种变化时进行增量图模式匹配.在真实数据集和合成数据集上进行实验,结果表明:与重新在整个数据图上进行匹配的ReComputing算法相比,当模式图中变化的边的数目不超过不变的边的数目时,PGC_IncGPM算法能够有效减少图模式匹配的执行时间;随着数据图规模的增大,PGC_IncGPM算法相对于ReComputing算法的执行时间的减少程度更加明显,对于大规模数据图具有更好的适用性.     

高效的图模型点模式匹配算法

点模式匹配的概率图模型具有很好的匹配精度,但是计算复杂度较高,当隔离子中包含异常点（outlier）时匹配精度会受到较大的影响。为了提高匹配的速度和精度,提出了一种由粗到精的图模型点模式匹配算法。利用包含特征点的窗口,用标准化互相关方法对特征点进行粗匹配,以减少异常点的数量,提高后续匹配方法的速度和精度。提出了一种新的点模式匹配的概率图模型,这种图模型能综合利用特征点的位置信息和包含特征点的邻域的灰度信息。利用提出的概率图匹配方法对粗匹配所得到的点对进行分段匹配,得到精确的匹配结果。对光学图像和遥感图像的匹配实验显示该方法能显著减少点模式匹配时间,提高匹配的精度。     

基于强社交图的多约束信任图模式增量匹配算法

针对现有的图匹配方法没有考虑到社交背景下的多种约束以及在多约束图匹配中图结构的变化,提出一种多约束图模式匹配方法.为了提高多约束图模式匹配的效率,提出强社交图的概念及一种强社交图的索引结构来索引图的可达性、图模式和上下文背景信息,提出维护强社交图索引的算法INC-SSG和多约束图匹配的增量算法SSG-IncMGPM,当面对强社交图结构的变化时能快速有效地识别多约束图模式匹配结果.通过对五个真实社交图的实证研究,验证了该方法在效率和有效性方面的优越性.     

图编辑距离概述

图编辑距离是图模式匹配技术中常用的方法之一。基于图编辑距离的匹配方法能够处理多种类型的图数据,因而受到了学术界的广泛关注。首先介绍了图编辑距离的相关概念;然后简述了基于启发式搜索技术的精确图编辑距离算法,重点分析了基于二分图匹配的近似图编辑距离算法;最后对现存的一些图编辑问题进行了总结,并对未来的发展趋势进行了展望。     

基于改进加权图转换的图像匹配算法

对提出的基于马氏距离的点匹配方法进行了理论分析与实验验证,针对马氏距离及加权图转换匹配方法的不足,将马氏距离融入到加权图转换匹配算法中,提出了一种新的稳健的图像匹配策略——基于马氏距离加权图转换的图像匹配算法。该算法利用图中的点及其K-近邻点的马氏距离中值和角度距离建立权重矩阵,根据不断更新得到的权值更新图,逐个剔除出格点,获得更加精确的匹配结果。仿真数据和真实图像实验对比结果表明该方法的可行性和鲁棒性。     

一种有效的贪婪模式匹配算法

模式匹配问题是意图获得两个模式中所包含个体对象之间的语义匹配和映射,其结果表示源模式的个体对象与目标模式的个体对象之间存在特定的语义关联.它在数据库应用领域起到关键性的作用,例如数据集成、电子商务、数据仓库、XML消息交换等,特别地,它已成为元数据管理的基本问题.然而,模式匹配很大程度上依赖人工的操作,是一个费时费力的过程.模式匹配问题可以归约为一个组合优化问题:多标记图匹配问题.首先,将模式表示为多标记图,将模式匹配转换为多标记图匹配问题.其次,提出多标记图的相似性度量方法,进而提出基于多标记图相似性的模式匹配目标优化函数.最后,在这个目标函数基础上设计实现了一个贪婪匹配算法,其最显著的特点是综合多种可用的标记信息,灵活准确地获得最优的匹配结果.     

一种高效的RDF图模式匹配算法

随着越来越多的信息被表示为RDF格式,如何高效地对RDF信息进行分发和过滤成为一个重要的问题·在语义Web环境下的信息分发系统中,输入的RDF信息需要和大量的用户订阅条件进行匹配,而用户的订阅条件可以被表示为RDF图模式·根据RDF图的特点,并对其增加了一些约束,设计了一种新的RDF图模式匹配算法·实验结果表明,该算法的匹配效率远远高于传统的图模式匹配算法·     

使用社区结构信息的子图匹配算法优化方法*

子图匹配是图数据查询处理技术中的一个重要研究问题。针对现有子图匹配算法运行效率不高且缺乏通用优化方法的现状,提出一种基于社区结构的子图匹配算法优化方法(community structure based subgraph matching optimization method,CSO)。首先,提出两种优化策略,即解析模式图信息以减少子图匹配过程的计算量,以及利用社区结构信息在子图匹配过程中进行剪枝;然后,结合上述两种优化策略提出基于社区结构的子图匹配算法优化方法,并进行了理论分析。真实数据集和合成数据集上的大量实验结果表明,CSO方法能有效减少子图匹配算法的时间开销。同时,不同规模数据集上的实验结果验证了CSO方法良好的可扩展性。     

基于图连通支配集的子图匹配优化算法

在子图匹配过程中,随着图规模不断增长,匹配时间呈现指数爆炸的趋势.对此,提出一种基于图连通支配集的子图匹配优化算法VF-SMDS.根据贪心算法构建查询图的最小连通支配子图;通过代价模型计算最小连通支配子图节点的匹配代价,构建最优k查询节点匹配序列;通过支配节点的结构特征缩小查询节点搜索空间范围,在数据图中遍历到满足要求的节点,得到最终答案集.实验将VF-SMDS与GADDI、SPath、VF2++、VF3和SubISO方法进行对比.实验结果表明,在处理较大规模子图匹配问题时,VF-SMDS查询效率更高.     

演变图上的连接子图演变模式挖掘

探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连 接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动 态规划算法.模拟数据集上的实验结果表明,该算法具有较低的误差率和较高的效率.真实数据集上的实验结果表 明,挖掘结果在真实应用中具有实际意义.     

基于变迁图编辑距离的流程相似性算法

为了提高从企业模型库中查询检索模型的效率,提出一种基于变迁图编辑距离的流程相似性算法。首先,给出了变迁图的概念及其生成方法;其次,提出边的长度概念,且删除和插入边的代价由该边的长度决定,基于此定义出图编辑操作及其代价,并用节点匹配算法计算最小图编辑距离;然后,给出两个过程模型的相似性概念和计算方法;最后,通过实验验证了算法的正确性且满足七条相似性性质,并验证了变迁图编辑距离满足四条距离性质。     

网络攻击图逆向深度优先生成算法

大规模网络节点数量多,连接关系复杂,现有攻击图生成方法存在节点爆炸问题,针对大规模网络的这种特点,提出了一种逆向深度优先攻击图生成算法。首先对攻击图的相关概念进行了简要介绍,并分析了逆向生成算法流程。然后,鉴于生成攻击图过程中要对网络可达性进行测试,因此,同时提出了基于区间树的规则匹配算法,最后,对攻击图生成算法进行了实际环境测试,并对测试结果进行了验证分析。实验结果表明,该攻击图生成算法能以O（lgn）的时间复杂度高效检测网络可达性,优化网络攻击图生成结果。     

图的几何关系直方图及在匹配中的应用

针对图结构在一些非刚性变换下谱特征不稳定等问题,提出一种基于几何关系直方图的图结构信息的描述方法,并在此基础上实现图的顶点匹配。首先通过夹角和距离等一些几何量来描述图的顶点与其他各边的位置关系,然后结合直方图给出一种图顶点的特征描述,最后采用改进的匈牙利算法实现图的匹配。不同于传统的描述方法,该方法是利用图的顶点与边的几何关系的统计特征来描述图的结构信息。其结构简单,信息描述充分。实验结果表明,方法对于一些扰动前后的图的匹配具有较高的匹配准确度。     

基于边映射表连接的匹配算法

针对面向语义网络图匹配的特殊性, 在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法, 利用语义网络图的有向性, 将图匹配问题转换为对搜索路径的规划, 并采用深度优先算法形成搜索步, 同时对目标图的所有边建立索引, 加快以边匹配为中心形成边映射表的过程, 最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明, 该算法具有较高的执行效率。     

面向图数据的结构化正则路径查询方法

正则路径查询是一种应用正则表达式在图数据上进行查询的技术,通常利用有限状态自动机实现查询匹配。现有正则路径查询方法的匹配结果为顶点对的序列,未能充分保留图的结构,为了解决这一问题,提出了一种面向图数据的结构化正则路径查询方法,通过在不同的序列间加以结构化约束,使得查询结果由路径转变为子图。为了实现这一目的,首先定义了一种结构化的正则路径查询语言,并设计了结构化的查询解析以及基于此结构的匹配算法。实验在模拟数据集和真实数据集上进行了测试与分析,验证了网络规模对查询速度的影响,并设置了对照实验。实验结果表明,提出方法能够在保证满足正则表达式约束的前提下实现结构化查询。     

大规模图挖掘算法并行化研究

目前大规模图挖掘算法的思路是基于MapReduce将矩阵与向量相乘的过程并行化,但却没有针对MapReduce特点对图数据进行划分,会产生大量中间结果,算法代价较高.针对这些问题,提出了GIM-V LI算法.该算法采用数据划分思想,将图矩阵横向划分,结合MapReduce特点以行为单位替代点或块的数据组织方式,并设计出＜key,value＞结构,使一个单位数据仅产生一个中间结果,从而大大减少了中间结果,提高了算法的性能.通过大量实验分析验证了该改进算法的正确性与有效性.     

Adding regular expressions to graph reachability and pattern queries

It is increasingly common to find graphs in which edges are of different types, indicating a variety of relationships. For such graphs we propose a class of reachability queries and a class of graph patterns, in which an edge is specified with a regular expression of a certain form, expressing the connectivity of a data graph via edges of various types. In addition, we define graph pattern matching based on a revised notion of graph simulation. On graphs in emerging applications such as social networks, we show that these queries are capable of finding more sensible information than their traditional counterparts. Better still, their increased expressive power does not come with extra complexity. Indeed, (1) we investigate their containment and minimization problems, and show that these fundamental problems are in quadratic time for reachability queries and are in cubic time for pattern queries. (2) We develop an algorithm for answering reachability queries, in quadratic time as for their traditional counterpart. (3) We provide two cubic-time algorithms for evaluating graph pattern queries, as opposed to the NP-completeness of graph pattern matching via subgraph isomorphism. (4) The effectiveness and efficiency of these algorithms are experimentally verified using real-life data and synthetic data.     

一种改进的基于图割的立体匹配算法

为了提高立体匹配算法的精确度,提出了一种结合图割与Mean Shift图像分割的立体匹配算法。首先用Mean Shift算法对参考图像进行图像分割,得到分割后的标记图,然后将分割信息结合到图割算法的能量函数中,最后用改进的能量函数和图割算法得出致密的视差图。实验结果表明,提出的算法具有更高的精确度和更好的边缘特征。     

一种面向图数据的AWG-LDP局部差分隐私保护算法研究

针对传统的图数据隐私保护方法只关注保护属性或结构两者之一易导致节点或边隐私信息泄露的问题,提出了一种对属性加权图的局部差分隐私的保护算法（AWG-LDP）。首先,该算法利用GN算法将图数据划分成社区子图;其次,分别计算每个社区子图的局部敏感度,对于划分后的每一个子图,通过结合结构相似性和属性相似性并添加拉普拉斯噪声进行边扰动,实现局部差分隐私;最后,利用属性泛化的方式将待发布的节点进行泛化,防止节点敏感信息被攻击。利用真实的图数据集进行了不同参数配置以及不同算法的对比实验,实验结果表明该算法提升了隐私保护效果,同时,降低了信息损失,提高了数据的可用性。