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

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

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

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

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

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

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

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

一种面向大规模空间文本数据的空间结构匹配算法

为了支持各类基于位置的服务,人们提出了各种查询和搜索空间文本数据的方法和技术.传统的空间关键字查询和近期提出的空间模式匹配不支持用户定义查询关键字对象以及对象之间细致的空间结构关系,使得查询结果集庞大但无效结果偏多,不能满足用户高效且精确的查询需求.本文因此提出了一种新的查询模式——空间结构匹配查询(Spatial Structure Matching,SSM),允许用户定义一组查询关键字对象并指定任意两个对象之间的距离和方向约束.为了解决SSM查询问题,本文首先提出了一种基于多路连接的基准方法,将SSM查询问题分解为单个对象的关键字匹配,两个对象的边匹配和多个对象的聚合匹配.为了提高SSM查询效率,本文提出了基于扫描线算法的边匹配计算,利用对象的地理位置信息来降低边匹配计算开销.本文利用同时满足查询关键字,距离和方向约束的空间对象构造对象连接图,从而将SSM查询问题转换为在对象连接图上搜索与SSM查询结构同构的子图匹配问题,并且利用经典的子图同构匹配算法求解获得最终的查询结果.在四个大规模空间文本数据集上的实验结果表明,本文所提算法的查询效率远高于对比算法,返回的查询结果集精简有效且...     

融合关联性分析的图数据处理加速方法的研究

针对目前视频服务场景下的电影资源中存在海量的关系型数据,现有的基于图相关的推荐算法需要将这些关系型数据映射成图结构后进行处理,由于图数据规模较大造成了传统的图数据处理方法中语义匹配算法的效率降低、通信开销增大的问题,本文融合关联性分析提出了一种基于语义匹配的图数据加速处理方案——一种在单一大图中查询图序列的子图匹配加速...     

基于自动机XML正则路径表达式查询研究

基于自动机正则路径表达式查询技术是半结构化数据模式下XML查询研究领域颇有价值的方法。许多研究方法对含有“//”操作符和“*”通配符复杂正则路径重写都会产生大量中间路径。设计了处理XML正则路径查询高效方法——CSAS,利用对象交换模型(OEM)作为XML数据模型,有限自动机作为查询模型,提出裁剪XMLSchema转化的自动机片断作为重写自动机来重写“//”和“*”符号的重写技术;利用剪枝技术、谓词处理后移策略实现查询优化。实验证明,CSAS方法是一种高效的XML正则路径表达式查询方法。     

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

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

低冗余计算的可达性查询保持图压缩策略

针对可达性查询保持图压缩（QPGC）算法存在冗余计算的问题,提出了一种高性能压缩策略。在求解顶点的祖先后代集阶段,针对普通图数据,提出一种基于拓扑排序的求解算法TSB,首先将图数据顶点拓扑排序,然后沿拓扑序列顺序（逆序）求解顶点的祖先（后代）集,避免了求解顺序不明确导致的冗余计算;针对最长路径较短的图数据,提出一种基于图聚合运算的求解算法AGGB,可在确定次数的聚合运算内完成顶点的祖先和后代集的求解。在求解可达性等价类阶段,提出一种分段统计剪枝算法PSP,先对祖先后代集分段统计,再比较统计值以实现粗匹配,剪除了部分不必要的精细匹配。实验结果表明,与QPGC算法相比：在祖先后代集求解阶段,TSB和AGGB在不同数据集上的性能平均提升94.22%和90.00%;在求解可达性等价类阶段,PSP算法在大部分数据集上性能提升超过70%;随着数据集的增大,TSB和AGGB配合PSP算法,性能提升了近28倍。理论分析和模拟实验表明,该策略与QPGC算法相比冗余计算更少、压缩速度更快。     

基于图匹配网络的可解释知识图谱复杂问答方法

知识图谱问答是人工智能领域的研究热点之一.在该任务中,自然语言问句结构与知识图谱结构之间的语义匹配是一个具有挑战的研究问题.现有工作主要利用深度学习技术对自然语言问句进行序列化编码,然后与知识图谱子图计算语义匹配,这样做法未充分利用复杂问句的结构信息,方法也缺乏可解释性.针对此问题,提出一种基于图匹配网络的知识图谱复杂问答方法TTQA.首先,通过语法分析方法,构建一个与知识图谱无关的未定查询图.然后,依据未定查询图和给定的知识图谱,构建一个与知识图谱相关的已定查询图,在其中,提出一种图匹配网络GMN,通过结合预训练语言模型和图神经网络技术,再利用注意力机制学习查询结构的上下文表示,从而得到更加丰富的结构匹配表示,用于已定查询图预测.在2个复杂问答数据集LC-QuAD 1.0和ComplexWebQuestions 1.1进行实验,结果表明：TTQA超过了现有方法.同时,通过消融实验验证了GMN的有效性.此外,TTQA生成的未定结构图和已定查询图增强了问答系统可解释性.     

Structure and attribute index for approximate graph matching in large graphs

The increasing popularity of graph data in various domains has lead to a renewed interest in developing efficient graph matching techniques, especially for processing large graphs. In this paper, we study the problem of approximate graph matching in a large attributed graph. Given a large attributed graph and a query graph, we compute a subgraph of the large graph that best matches the query graph. We propose a novel structure-aware and attribute-aware index to process approximate graph matching in a large attributed graph. We first construct an index on the similarity of the attributed graph, by partitioning the large search space into smaller subgraphs based on structure similarity and attribute similarity. Then, we construct a connectivity-based index to give a concise representation of inter-partition connections. We use the index to find a set of best matching paths. From these best matching paths, we compute the best matching answer graph using a greedy algorithm. Experimental results on real datasets demonstrate the efficiency of both index construction and query processing. We also show that our approach attains high-quality query answers.     

结构化加密图的最短路径查询

随着云计算的快速发展, 数据用户将大量图数据外包给云以节约存储和管理成本。然而, 外包数据的安全隐私问题是云计算面临的一大挑战。由于云是半诚实的, 为保护敏感信息的隐私安全, 数据拥有者希望在将图数据外包给云服务器之前对其加密, 同时保留对加密的图数据进行查询和处理的能力。最短路径查询查找图中给定两节点之间的最短路径, 是图应用中最基础的查询类型之一。目前已有许多研究者提出一系列高效的方案, 以支持加密图上近似或精确最短距离查询、约束最短距离查询和 top-k 最近关键字查询, 但支持最短路径查询的方案较少, 且已有方案的存储与时间开销较大。本文提出一种支持在加密图上进行两节点间最短路径查询的结构化加密图方案。在本方案中, 我们基于 2-Hop 标签技术构造支持有向图上最短路径查询的标签索引并加密, 然后将加密的标签外包给云服务器。 利用改进的保序编码算法编码距离值, 实现加法运算和值的比较, 提高最短路径查询的效率。在查询阶段, 通过递归式地计算两节点间最短路径上的第一条边和最后一条边, 最终输出完整的最短路径。安全性和性能分析证明本文方案是安全有效的, 能以较小的存储和较高的查询效率实现两节点间的最短路径查询并保护图数据的隐私。     

大型网络中近似子图匹配研究

为降低噪声对近似子图匹配准确率的影响,提出一种改进的近似子图匹配方法。在预处理阶段,利用k-近邻顶点集为数据图中的每个顶点建立标签-权重向量索引。在查询过程中,基于单个近邻标签的权重距离和所有近邻标签的整体匹配程度进行两级过滤,生成顶点候选集,采用生成树匹配和图匹配的方式确定查询图在大型网络中的位置。在真实数据集上的实验结果表明,该方法具有较高的执行效率和匹配准确率。     

基于资源描述框架图切分与顶点选择性的高效子图匹配方法

在SPARQL查询过程中，含有复杂结构的资源描述框架（RDF）图的查询效率低下。为此，通过分析几种RDF图的基本结构与RDF顶点的选择性，提出RDF三元组模式选择性（RTPS）——一种基于RDF顶点选择性的图结构切分规则，以提高面向RDF图的子图匹配效率。首先，根据谓词结构在数据图与查询图中的通性建立RDF相邻谓词路径（RAPP）索引，将数据图结构转化为传入-传出双向谓词路径结构以确定查询顶点的搜索空间，并加快顶点的过滤；接着，通过整数线性规划（ILP）问题计算建模将复杂RDF查询图结构分解为若干结构简单的查询子图，通过分析RDF顶点在查询图中的相邻子图结构与特征，确立查询顶点的选择性以确定最优切分方式；然后，通过RDF顶点选择性与相邻子图的结构特征来缩小查询顶点的搜索空间范围，并在数据图中找到符合条件的RDF顶点；最后，遍历数据图以找到与查询子图结构相匹配的子图结构，将得到的子图进行连接并将其作为查询结果输出。实验采用控制变量法，比较了RTPS、RDF子图匹配（RSM）、RDF-3X、GraSS与R3F的查询响应时间。实验结果充分表明，与其他4种方法相比，当查询图复杂度高于9时，RTPS的查询响应时间更短，具有更高的查询效率。     

基于信息熵的子图匹配算法

子图查询是指输入一个图数据库和查询子图,输出图数据库中包含查询子图的图集合,它广泛应用于社会网、生物网和信息网的查询应用中。目前的子图查询算法大多采用静态消耗测算模式,此类测算模式在图中点数和连接边数呈指数分布时,会在少数节点上花费较多时间遍历其邻节点,导致查询算法效率低下。根据信息熵在信息度量中的作用,将条件信息熵作为启发式匹配的依据,提出了基于信息熵的子图匹配算法。实验表明,基于信息熵的子图匹配算法具有更高的查询效率,且在指数分布的数据集上效果更明显。     

Graph Grammars for Querying Graph-like Data

Recently research has deeply investigated the problem of querying semi-structured data and data which can be represented by means of graphs (e.g. object-oriented data, XML data, etc.). Typically queries on graph-like data, called path queries, are expressed by means of regular expressions denoting paths in the graph. The result of a path query is the set of nodes reachable by means of a path expressed by a specified regular expression. In this paper we investigate the problem of extracting a subgraph satisfying a given property from a given graph representing some information. We propose a new form of queries, called graph queries, whose answers are (marked) graphs having a particular structure, extracted from the source graph. We show that a simple form of graph grammars can be profitably used to define graph queries. The result of a graph query, using a grammar G over a database D, is a marked subgraph of D ‘matching’ a graph derived from G. We consider different types of graph grammars which can be used to query graph-like data and consider their expressiveness and complexity.     

Answering pattern match queries in large graph databases via graph embedding

The growing popularity of graph databases has generated interesting data management problems, such as subgraph search, shortest path query, reachability verification, and pattern matching. Among these, a pattern match query is more flexible compared with a subgraph search and more informative compared with a shortest path or a reachability query. In this paper, we address distance-based pattern match queries over a large data graph G. Due to the huge search space, we adopt a filter-and-refine framework to answer a pattern match query over a large graph. We first find a set of candidate matches by a graph embedding technique and then evaluate these to find the exact matches. Extensive experiments confirm the superiority of our method.