共查询到19条相似文献,搜索用时 46 毫秒
1.
针对在SPARQL查询处理中,随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题,通过分析几种资源描述框架(RDF)图的基本结构,提出了一种基于查询图结构切分的子图匹配方法——RSM。首先,将查询图切分为若干结构简单的查询子图,并通过相邻谓词结构索引来定义查询图节点的搜索空间;然后,通过相邻子图结构来缩小搜索空间范围,在数据图中根据搜索空间中的搜索范围找到符合的子图结构;最后,将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较,对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明,与其他3种方法相比,在处理结构复杂的查询图时,RSM的查询响应时间更短,具有更高的查询效率。 相似文献
3.
子图匹配是图论中最基本的操作.研究子图匹配的一个变种,即:在一个节点拥有若干元素的大图数据库中,找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图,称作基于包含度的子图匹配(subgraph matching with inclusion degree,简称SMID).该查询能够应用于多种场景,包括论文检索、社区发现、企业招聘等.为高效实现SMID,设计了同时包含节点元素和图结构信息的数据签名与查询签名,在离线处理阶段,利用数据签名为数据图建立动态签名树(DS-Tree),以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题,设计了一种DS-Tree压缩方法,在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率,还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明,所提出的方法在效率和扩展性方面优于现有其他方法. 相似文献
4.
5.
均值-标准差描述子与直线匹配 总被引:3,自引:0,他引:3
提出一种通过直线描述子来进行自动直线匹配的思想.直线描述子的建立分为以下3个主要步骤:首先为直线定义平行邻域并将该邻域分解为一系列平行线,其次通过选择图像特征建立直线描述矩阵,最后通过计算描述矩阵列向量的均值和标准差获得直线描述子.基于不同的图像特征(灰度、梯度和梯度幅值),提出3个具有平移、旋转和线性光照不变性的直线描述子.实验结果表明本文提出的直线描述子具有较好的匹配性能. 相似文献
6.
7.
随着知识图谱的日益发展和在各个垂直领域的广泛应用,对于资源描述框架(RDF)数据的高效处理需求日益成为现代大数据管理领域中的新课题。RDF是W3C提出的用于描述知识图谱实体以及实体间关系的数据模型。为了有效地应对大规模RDF数据的存储和查询,很多学者考虑在分布式环境中管理RDF数据。RDF数据的分布式存储所面临的关键问题是数据的划分,而划分的结果很大程度上决定了SPARQL的查询性能。从数据划分的角度,主要围绕两类:基于图结构的RDF数据划分方法和基于语义的RDF数据划分方法展开深入阐述。前者包括多粒度层次划分、模板划分和聚类划分,适用于通用领域查询的语义范畴较为宽泛的场景;后者包括哈希划分、垂直划分和模式划分,更加适用于垂直领域查询的语义范畴相对固定的环境。此外,针对几种典型的划分方法进行对比与分析,为未来RDF数据划分方法的研究提供参考。最后,对未来RDF数据划分方法的发展方向进行了归纳总结。 相似文献
8.
子图匹配是图数据查询处理技术中的一个重要研究问题。针对现有子图匹配算法运行效率不高且缺乏通用优化方法的现状,提出一种基于社区结构的子图匹配算法优化方法(community structure based subgraph matching optimization method,CSO)。首先,提出两种优化策略,即解析模式图信息以减少子图匹配过程的计算量,以及利用社区结构信息在子图匹配过程中进行剪枝;然后,结合上述两种优化策略提出基于社区结构的子图匹配算法优化方法,并进行了理论分析。真实数据集和合成数据集上的大量实验结果表明,CSO方法能有效减少子图匹配算法的时间开销。同时,不同规模数据集上的实验结果验证了CSO方法良好的可扩展性。 相似文献
9.
随着知识图谱的日益发展和在各个垂直领域的广泛应用,对于资源描述框架(RDF)数据的高效处理需求日益成为现代大数据管理领域中的新课题。RDF是W3C提出的用于描述知识图谱实体以及实体间关系的数据模型。为了有效地应对大规模RDF数据的存储和查询,很多学者考虑在分布式环境中管理RDF数据。RDF数据的分布式存储所面临的关键问题是数据的划分,而划分的结果很大程度上决定了SPARQL的查询性能。从数据划分的角度,主要围绕两类:基于图结构的RDF数据划分方法和基于语义的RDF数据划分方法展开深入阐述。前者包括多粒度层次划分、模板划分和聚类划分,适用于通用领域查询的语义范畴较为宽泛的场景;后者包括哈希划分、垂直划分和模式划分,更加适用于垂直领域查询的语义范畴相对固定的环境。此外,针对几种典型的划分方法进行对比与分析,为未来RDF数据划分方法的研究提供参考。最后,对未来RDF数据划分方法的发展方向进行了归纳总结。 相似文献
10.
11.
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 and a data graph , the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of on . 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 -Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph ( ), 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 . Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms. 相似文献
12.
13.
针对目前最先进的增量子图匹配算法Symbi中的索引结构DCS中存在的信息冗余问题,提出了一种新的索引结构CDCS(compressed dynamic candidate space),并提出了CDCS的更新算法INCCDCS来动态维护CDCS索引结构和匹配结果,最后提出了动态图的增量子图匹配算法CSymbi。该方法通过引入邻域信息约束,在构建和更新辅助结构的过程中过滤候选集,提高算法的求解效率。最后,在Netflow和LSBench数据集上进行验证,相较于现有方法,候选节点数量最高可以删减56%,候选边数量最高可以删减62%,有效缩减了计算空间并提高了算法的求解效率。 相似文献
14.
针对以二分图形式发布的社会网络隐私泄露问题,提出了一种面向敏感边识别攻击的社会网络二分图匿名方法。在已有k-安全分组的理论基础上,结合二分图的稀疏性和敏感边识别攻击形式,分别提出了正单向、逆单向以及完全(c1,c2)-安全性原则,并在此基础上,形式化地定义了一类抗敏感边识别攻击的社会网络二分图安全匿名问题;同时,还提出了一种基于k-频繁子图聚类的二分图划分算法和一种基于二分图(c1,c2)-安全性的匿名算法来保证发布二分图的安全性。实验结果表明,该算法在与已有方法相当时间开销的前提下,能产生更小的信息损失度,有效地抵制了敏感边识别攻击,实现了二分图的安全发布。 相似文献
15.
16.
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. 相似文献
17.
基于描述方法的SAR图像分割* 总被引:2,自引:2,他引:0
针对减少SAR图像分割中自由参数的问题,提出了基于最小描述长度的SAR图像分割方法。该方法经对数变换将SAR图像乘性噪声转换为加性噪声,对其建立描述模型,在描述长度最短意义上计算出重建图像,在假设SAR图像各区域实际地物后向散射特性对应的像素值恒定的前提下,该重建图像即为SAR图像的分割结果。该方法在分割的同时很好地抑制了SAR图像的相干斑噪声,保留了原始SAR图像的区域边界,并且不需要参数调节,整个分割过程自动完成,是一种非监督SAR图像分割方法。给出了该方法的具体实现步骤,实验结果验证了该方法的有效性。 相似文献
18.
基于分水岭算法和图论的图像分割 总被引:2,自引:0,他引:2
提出一种新的基于分水岭算法和图论的图像分割方法FWTN(First Watershed Then Normalized cut),以克服传统的分水岭算法造成的图像过度分割。FWTN方法在分水岭算法之后,用Normalized Cut方法在区域之间进行分割,产生最终所分割的图像。FWTN成功地解决了过分割问题,同时还对Normalized Cut方法中的NP-hard问题有所改进。实验结果表明该算法是一种切实可行的图像分割方法。 相似文献