层次序列索引的大规模动态标签图子图查询

标签图常用于智能交通网、生物信息网等新兴领域的建模。子图查询作为图数据分析的关键问题，引起了研究者的广泛关注。对现有子图查询算法的研究发现，随着图数据规模增大且频繁更新，传统子图查询算法普遍存在查询效率低，存储开销大，忽略顶点标签信息等问题。为此，提出了一种支持大规模动态标签图子图查询的层次序列索引（Dynamic Hierarchical Sequence，DHS），该索引提取数据图中带有顶点编号的层次拓扑序列关系以实现子图查询；针对图的动态变化，提出了更新点拓扑扩展式索引维护策略，仅从局部变化顶点及边开始进行增量式更新，大大降低了重建索引造成的巨大开销；提出了基于DHS索引的子图查询方法，仅需将查询图与数据图的层次序列进行匹配即可获得候选集，并在其上利用关系匹配策略获得最终查询结果。实验证明提出的方法在保证高效查询的同时降低了索引的创建及维护时间，提高了子图查询效率。     

基于索引的子图查询技术研究进展

图作为表示实体间的数据结构，在社区发现、生物化学分析、社会安全分析等数据关联性要求较高的领域有着广泛的应用。对于大规模数据下进行实时的图查询问题，通过构建合适的索引可以有效降低查询响应时间，提高查询精确度。首先介绍基于索引的子图查询算法的基本结构；然后按索引的构建方式将主流算法分为基于枚举的方法和基于频繁模式挖掘的方法两大类，分别从索引特征、索引结构、应用数据集等方面进行介绍和分析；最后对基于索引的子图查询算法面临的主要问题进行总结和分析，阐述了最新的分布式系统下图查询技术，并对未来趋势进行展望。     

不确定图数据库中高效查询处理

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.     

动态图模式匹配技术综述

随着大数据时代的到来,多源异构数据的快速增长已经成为了一个开放性问题,这些数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中,例如网络安全分析和社交网络舆情分析,描述实体对象之间关系的图数据的结构和内容往往不是固定不变的,图数据的结构以及节点和边的属性会随着时间的推移发生更新变化.因此,如何在动态更新的图数据中进行高效的查询、匹配是目前研究的热点问题,也涌现了许多优秀的研究工作.本文从关键技术、代表性算法和性能评价方面对动态图匹配技术的研究进展进行了综述.最后对动态图匹配技术的典型应用、面临的挑战问题和未来发展趋势进行了总结和展望.     

基于包含度的子图匹配方法

子图匹配是图论中最基本的操作.研究子图匹配的一个变种,即：在一个节点拥有若干元素的大图数据库中,找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图,称作基于包含度的子图匹配（subgraph matching with inclusion degree,简称SMID）.该查询能够应用于多种场景,包括论文检索、社区发现、企业招聘等.为高效实现SMID,设计了同时包含节点元素和图结构信息的数据签名与查询签名,在离线处理阶段,利用数据签名为数据图建立动态签名树（DS-Tree）,以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题,设计了一种DS-Tree压缩方法,在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率,还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明,所提出的方法在效率和扩展性方面优于现有其他方法.     

支持动态图数据的子图查询方法

近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加困难。针对上述问题,提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引,在序列中加入标号以便数据更新后对索引进行维护,再根据序列间的匹配关系过滤出候选集合,最后采用图同构算法验证候选集中的图,最终得到结果集合。该方法的索引构造简单且体积小,并且在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。     

图近似查询算法研究

从数据管理中的近似查询方向,对图数据的近似查询算法进行了研究.依据近似查询的类别,分别介绍了近似查询中的经典算法,并对这些算法进行了详细的分析和讨论,从索引单元以及索引机制比较了各种算法适用的范围以及应用领域.重点阐述和比较了各算法的特点及查询性能,分析了各个算法存在的优势和不足.对近似查询中现有算法的不足及未来的研究方向进行了讨论.     

大规模图数据可达性索引技术:现状与展望

随着社交网络、生物信息网、本体等新兴领域的飞速发展,在现实应用中涌现出大量的图数据.可达性查询是有向图上一类最基本的查询.当图的规模非常小时,利用深度优先遍历(depth-first search,DFS)或可达性传递闭包可以很容易处理可达性查询.但是,随着图的规模越变越大,由于DFS方法的查询效率太低而可达性传递闭包方法占用的存储空间太大,这2种方法不再适用.因此,许多可达性索引方法相继被提出.这些方法已经被广泛应用于多个计算机科学领域,如软件工程、编程语言、分布式计算、社交网络分析、生物网络分析、XML和RDF数据库、路由规划等领域.此外,可达性索引还可用于加速其他图算法,如最短路径查询和子图模式匹配.首先介绍了可达性索引的应用背景.接着,依据支持的数据规模、数据类型以及查询类别,将现有可达性索引工作进行了分类,并对代表性工作进行分类比较;最后,讨论了现有的大规模图数据可达性索引方法存在的问题,并指出了未来的研究方向.     

基于双索引的近似子图匹配

越来越多的大型复杂网络使得图结构的研究变得日益重要,其中近似子图查询备受关注。为了提高查询效率,利用顶点的邻接关系特征为每个顶点建立索引,减少了匹配顶点的数量;并基于结构和标签对大型数据图进行划分,缩小了匹配时的搜索空间。利用离线时建立的双索引,查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点,然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明,与单纯的划分方法或近邻关系索引相比较,双索引机制对于查询的效率和准确率方面均有明显改善。     

大规模标签图中的动态Top-K兴趣子图查询

针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K。该方法建立了包括节点拓扑结构特性（NTF）索引和边特性（EF）索引的图拓扑结构特性（GTSF）索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确。大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询。     

计算机视觉中图匹配研究进展: 从二图匹配迈向多图匹配

图匹配试图求解二图或多图之间节点的对应关系.在图像图形领域,图匹配是一个历久弥新的基础性问题.从优化的角度来看,图匹配问题是一个组合优化问题,且在一般情形下具有非确定性多项式复杂程度(non-deter-ministic polynomial, NP)难度的性质.在过去数十年间,出现了大量求解二图匹配的近似算法,并在各个领域得到了较为广泛的应用.然而,受限于优化问题本身的理论困难和实际应用中数据质量的种种限制,各二图匹配算法在匹配精度上的性能日益趋近饱和.相比之下,由于引入了更多信息且往往更符合实际问题的设定,多图的协同匹配则逐渐成为了一个新兴且重要的研究方向.本文首先介绍了经典的二图匹配方法,随后着重介绍近年来多图匹配方法的最新进展和相关工作.最后,本文讨论了图匹配未来的发展.     

基于谱图理论的特征匹配方法研究和改进

图像匹配问题是计算机视觉领域的一个基本问题,广泛地应用于很多领域,如:模式识别,自动导航,医学诊断,计算机视觉,图像三维重构等领域。将所研究的问题转化为数学问题,再利用数学工具解决这一问题,成为当今研究的一种重要手段。在这里,将图像匹配中的图像转化为数学-图论中的图,利用谱图理论解决图像匹配问题,从而形成了一类比较流行而新颖的方法,针对这一方法进行了较为系统的探究并做出了改进。     

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

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

点圈并图的匹配等价图数

若两个图G和H的匹配多项式相等,称图G和H匹配等价用(δG)表示图G的所有不同构的匹配等价图的个数。文[5]在{m1,m2}∩{6,9,15}=Ф的条件下计算了δ(sK1∪t1Cm1∪t2Cm2),在该文中计算了δ(sK1∪t1C3∪t2C6)、δ(sK1∪t1C6∪t2C9)是文[5]的完善和补充。     

Matching preclusion and conditional matching preclusion for pancake and burnt pancake graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion destroys all perfect matchings in the graph. The optimal matching preclusion sets are often precisely those which are induced by a single vertex of minimum degree. To look for obstruction sets beyond these, the conditional matching preclusion number was introduced, which is defined similarly with the additional restriction that the resulting graph has no isolated vertices. In this paper we find the matching preclusion and conditional matching preclusion numbers and classify all optimal sets for the pancake graphs and burnt pancake graphs.     

一种基于RDF图的本体匹配方法

本体匹配是建立两个本体之间映射关系的过程,一个高效、严格的相似度计算方法是本体匹配的前提条件,为此提出了一种基于RDF图匹配的方法。该方法用RDF图表示本体,使本体间的匹配问题转化为RDF图的匹配问题,并利用匹配树表示匹配的状态,通过匹配树计算出两个本体中各实体之间的相似度,进而得到两个本体之间的映射关系。实验结果表明,该方法在查全率和查准率方面都有很好的表现。     

Stereo vision correspondence using a multichannel graph matching technique

A multichannel feature-based stereo vision technique is described in this paper where curve segments are used as the feature primitives in the matching process. Curve segments are extracted by tracking the zero-crossings of the left and right images. The generalized Hough transform of each curve and the curve length are used as a local feature vector in representing the distinctive characteristics of the curve segment. The feature vector of each curve segment in the left image is used as a constraint to find an instance of the same curve segment in the right image. The epipolar constraint on the centroids of the curve segment is used to limit the searching space in the right image.

A relational graph is formed from the left image by treating the centroids of the curve segments as the nodes of the graph. The local features of the curve segments are used to represent the local properties of the nodes, and the relationship between the nodes represents the structural properties of the objects in the scene. A similar graph is also formed from the right image curve segments. A graph isomorphism is then formed between the two graphs by using the epipolar constraint on the centroids, the local properties of the nodes, node assignment and the structural relationship (compatibility) between the nodes.     

基于深度优先搜索的一般图匹配算法

对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在“花”。遇到这种情况,要对它进行缩减“花”处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O（n^3）,但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现“花”的情况,算法相对简单;同时,算法时间效率为O（n＊degree（n））,degree（n）为顶顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。     

基于骨架层次分解的目标的图表示

基于骨架的目标表示技术是模式识别和计算机视觉的重要研究内容,近年来人们提出了许多骨架化算法,但是有关利用骨架信息表示并识别目标的研究还非常有限。Ablameyko等1996年提出了通过分解由距离标号的骨架为有意义的结构基元从而获得目标的层次结构图的方法。该图可以准确地刻画基元之间的拓扑关系,但是它对于骨架中的噪声比较敏感。主要表现为噪声基元破坏其它基元的完整性和图的稳定性。该文采用将分支编组为分支链以及构造多尺度结构图的改进策略来克服这些缺点,最终获得了目标的节点数更小、节点显著度更高、节点间连接关系更稳定的多尺度图,从而显著地提高后续利用不精确图匹配技术进行目标识别的效率。这项技术已经被应用于一个基于形状特征的图像数据库检索系统中。