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

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

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

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

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

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

均值-标准差描述子与直线匹配

提出一种通过直线描述子来进行自动直线匹配的思想.直线描述子的建立分为以下3个主要步骤:首先为直线定义平行邻域并将该邻域分解为一系列平行线,其次通过选择图像特征建立直线描述矩阵,最后通过计算描述矩阵列向量的均值和标准差获得直线描述子.基于不同的图像特征(灰度、梯度和梯度幅值),提出3个具有平移、旋转和线性光照不变性的直线描述子.实验结果表明本文提出的直线描述子具有较好的匹配性能.     

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

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

分布式环境下大规模资源描述框架数据划分方法综述

随着知识图谱的日益发展和在各个垂直领域的广泛应用，对于资源描述框架（RDF）数据的高效处理需求日益成为现代大数据管理领域中的新课题。RDF是W3C提出的用于描述知识图谱实体以及实体间关系的数据模型。为了有效地应对大规模RDF数据的存储和查询，很多学者考虑在分布式环境中管理RDF数据。RDF数据的分布式存储所面临的关键问题是数据的划分，而划分的结果很大程度上决定了SPARQL的查询性能。从数据划分的角度，主要围绕两类：基于图结构的RDF数据划分方法和基于语义的RDF数据划分方法展开深入阐述。前者包括多粒度层次划分、模板划分和聚类划分，适用于通用领域查询的语义范畴较为宽泛的场景；后者包括哈希划分、垂直划分和模式划分，更加适用于垂直领域查询的语义范畴相对固定的环境。此外，针对几种典型的划分方法进行对比与分析，为未来RDF数据划分方法的研究提供参考。最后，对未来RDF数据划分方法的发展方向进行了归纳总结。     

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

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

分布式环境下大规模资源描述框架数据划分方法综述

随着知识图谱的日益发展和在各个垂直领域的广泛应用,对于资源描述框架（RDF）数据的高效处理需求日益成为现代大数据管理领域中的新课题。RDF是W3C提出的用于描述知识图谱实体以及实体间关系的数据模型。为了有效地应对大规模RDF数据的存储和查询,很多学者考虑在分布式环境中管理RDF数据。RDF数据的分布式存储所面临的关键问题是数据的划分,而划分的结果很大程度上决定了SPARQL的查询性能。从数据划分的角度,主要围绕两类：基于图结构的RDF数据划分方法和基于语义的RDF数据划分方法展开深入阐述。前者包括多粒度层次划分、模板划分和聚类划分,适用于通用领域查询的语义范畴较为宽泛的场景;后者包括哈希划分、垂直划分和模式划分,更加适用于垂直领域查询的语义范畴相对固定的环境。此外,针对几种典型的划分方法进行对比与分析,为未来RDF数据划分方法的研究提供参考。最后,对未来RDF数据划分方法的发展方向进行了归纳总结。     

A subgraph matching algorithm based on subgraph index for knowledge graph

The problem of subgraph matching is one fundamental issue in graph search, which is NP-Complete problem. Recently, subgraph matching has become a popular research topic in the field of knowledge graph analysis, which has a wide range of applications including question answering and semantic search. In this paper, we study the problem of subgraph matching on knowledge graph. Specifically, given a query graph q and a data graph G, the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G. Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph. To accelerate subgraph matching on knowledge graph, we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph, called as F G q_T-Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph ( F G q_T), which reduces redundant calculations in advance. Another design is a multi-label weight matrix, which evaluates a near-optimal matching tree for minimizing the intermediate candidates. With the aid of these two key designs, all subgraph isomorphic mappings are quickly conducted only by traversing F G q_T. Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.     

一种基于子图近似同构的e-Learning学习资源本体匹配方法

针对e-Learning学习资源本体异构问题, 提出一种基于子图近似同构的本体匹配方法。该方法对现有本体匹配方法进行扩展, 综合编辑距离、层次关系等特征, 计算本体的结构级相似性, 以点、边有序交替匹配来判断实体的有向图近似同构问题, 实现本体匹配判定。演示算法处理过程, 给出算法时间复杂度理论分析, 说明其有效性。     

基于邻域安全压缩的动态图增量子图匹配算法

针对目前最先进的增量子图匹配算法Symbi中的索引结构DCS中存在的信息冗余问题,提出了一种新的索引结构CDCS（compressed dynamic candidate space）,并提出了CDCS的更新算法INCCDCS来动态维护CDCS索引结构和匹配结果,最后提出了动态图的增量子图匹配算法CSymbi。该方法通过引入邻域信息约束,在构建和更新辅助结构的过程中过滤候选集,提高算法的求解效率。最后,在Netflow和LSBench数据集上进行验证,相较于现有方法,候选节点数量最高可以删减56%,候选边数量最高可以删减62%,有效缩减了计算空间并提高了算法的求解效率。     

基于k-频繁子图聚类的二分图匿名方法

针对以二分图形式发布的社会网络隐私泄露问题,提出了一种面向敏感边识别攻击的社会网络二分图匿名方法。在已有k-安全分组的理论基础上,结合二分图的稀疏性和敏感边识别攻击形式,分别提出了正单向、逆单向以及完全（c1,c2）-安全性原则,并在此基础上,形式化地定义了一类抗敏感边识别攻击的社会网络二分图安全匿名问题;同时,还提出了一种基于k-频繁子图聚类的二分图划分算法和一种基于二分图（c1,c2）-安全性的匿名算法来保证发布二分图的安全性。实验结果表明,该算法在与已有方法相当时间开销的前提下,能产生更小的信息损失度,有效地抵制了敏感边识别攻击,实现了二分图的安全发布。     

基于非对称属性描述的网格资源匹配算法

针对网格资源匹配过程逐渐复杂化,以语义相似度查找机制为基础,提出了一种基于非对称资源属性描述的网格资源匹配算法BARM。BARM利用两次匹配对匹配过程加以边界约束,通过调整权重和阈值控制匹配结果的查准率和查全率,从而满足用户个性化的需求。     

Efficient and scalable labeled subgraph matching using SGMatch

Graphs are natural candidates for modeling application domains, such as social networks, pattern recognition, citation networks, or protein–protein interactions. One of the most challenging tasks in managing graphs is subgraph matching over data graphs, which attempts to find one-to-one correspondences, called solutions, among the query and data nodes. To compute solutions, most contemporary techniques use backtracking and recursion. An open research question is whether graphs can be matched based on parts and local solutions can be combined to reach a global matching. In this paper, we present an approach based on graph decomposition called SGMatch to match graphs. We represent graphs in smaller units called graphlets and develop a matching technique to leverage this representation. Pruning strategies use a new notion of edge covering called minimum hub cover and metadata, such as statistics and inverted indices, to reduce the number of matching candidates. Our evaluation of SGMatch versus contemporary algorithms, i.e., VF2, GraphQL, QuickSI, GADDI, or SPath, shows that SGMatch substantially improves the performance of current state-of-the-art techniques for larger query graphs with different structures, i.e., cliques, paths or subgraphs.     

基于描述方法的SAR图像分割*

针对减少SAR图像分割中自由参数的问题,提出了基于最小描述长度的SAR图像分割方法。该方法经对数变换将SAR图像乘性噪声转换为加性噪声,对其建立描述模型,在描述长度最短意义上计算出重建图像,在假设SAR图像各区域实际地物后向散射特性对应的像素值恒定的前提下,该重建图像即为SAR图像的分割结果。该方法在分割的同时很好地抑制了SAR图像的相干斑噪声,保留了原始SAR图像的区域边界,并且不需要参数调节,整个分割过程自动完成,是一种非监督SAR图像分割方法。给出了该方法的具体实现步骤,实验结果验证了该方法的有效性。     

基于分水岭算法和图论的图像分割

提出一种新的基于分水岭算法和图论的图像分割方法FWTN(First Watershed Then Normalized cut),以克服传统的分水岭算法造成的图像过度分割。FWTN方法在分水岭算法之后,用Normalized Cut方法在区域之间进行分割,产生最终所分割的图像。FWTN成功地解决了过分割问题,同时还对Normalized Cut方法中的NP-hard问题有所改进。实验结果表明该算法是一种切实可行的图像分割方法。     

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

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