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

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

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

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

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

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

基于RDF图结构切分的高效子图匹配方法

针对在SPARQL查询处理中,随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题,通过分析几种资源描述框架（RDF）图的基本结构,提出了一种基于查询图结构切分的子图匹配方法——RSM。首先,将查询图切分为若干结构简单的查询子图,并通过相邻谓词结构索引来定义查询图节点的搜索空间;然后,通过相邻子图结构来缩小搜索空间范围,在数据图中根据搜索空间中的搜索范围找到符合的子图结构;最后,将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较,对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明,与其他3种方法相比,在处理结构复杂的查询图时,RSM的查询响应时间更短,具有更高的查询效率。     

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

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

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

在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的查询响应时间更短，具有更高的查询效率。     

基于OAN的知识图谱查询研究

知识图谱查询是目前知识图谱研究中最广泛的应用,能够有效提高搜索引擎查询效率。然而,现有的知识图谱的查询研究多是基于节点标签的子图匹配。由于节点标签不能体现节点间的语义信息,导致查询结果的语义相关性不高。针对此问题,本文提出了一种基于本体和邻居信息的查询算法OAN(Ontology and Neighborhood)。首先,结合本体相似度和邻居相似度来确定查询节点的候选集,以此提高候选节点的语义相似度;其次,通过边检测算法移除那些不满足条件的查询节点候选集,以此减少查询规模;然后,在目标图上查找满足边标签同构的查询子图,并计算节点的标签相似度和结构相似度总和,给每个结果集打分后排序,获得最终排序后的结果集;最后,通过在真实数据集上与已有查询算法进行对比实验,实验结果表明:本文所提出的方法无论是在精确度上,还是在查询效率方面都有所提高。     

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

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

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

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

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

Fast processing of graph queries on a large database of small and medium-sized data graphs

We propose a new way of indexing a large database of small and medium-sized graphs and processing exact subgraph matching (or subgraph isomorphism) and approximate (full) graph matching queries. Rather than decomposing a graph into smaller units (e.g., paths, trees, graphs) for indexing purposes, we represent each graph in the database by its graph signature, which is essentially a multiset. We construct a disk-based index on all the signatures via bulk loading. During query processing, a query graph is also mapped into its signature, and this signature is searched using the index by performing multiset operations. To improve the precision of exact subgraph matching, we develop a new scheme using the concept of line graphs. Through extensive evaluation on real and synthetic graph datasets, we demonstrate that our approach provides a scalable and efficient disk-based solution for a large database of small and medium-sized graphs.     

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

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

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.     

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

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

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

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

Subgraph similarity maximal all-matching over a large uncertain graph

Recently, uncertain graph data management and mining techniques have attracted significant interests and research efforts due to potential applications such as protein interaction networks and social networks. Specifically, as a fundamental problem, subgraph similarity all-matching is widely applied in exploratory data analysis. The purpose of subgraph similarity all-matching is to find all the similarity occurrences of the query graph in a large data graph. Numerous algorithms and pruning methods have been developed for the subgraph matching problem over a certain graph. However, insufficient efforts are devoted to subgraph similarity all-matching over an uncertain data graph, which is quite challenging due to high computation costs. In this paper, we define the problem of subgraph similarity maximal all-matching over a large uncertain data graph and propose a framework to solve this problem. To further improve the efficiency, several speed-up techniques are proposed such as the partial graph evaluation, the vertex pruning, the calculation model transformation, the incremental evaluation method and the probability upper bound filtering. Finally, comprehensive experiments are conducted on real graph data to test the performance of our framework and optimization methods. The results verify that our solutions can outperform the basic approach by orders of magnitudes in efficiency.     

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.