近似图包含搜索和索引技术的研究

在对图形数据库中的几种有代表性的传统相似性搜索及索引构造方法进行总结分析的基础上,探讨了近似图包含搜索区别于传统相似性搜索的特征,并且提出了一种针对近似图包含搜索的基于覆盖率和支持度对频繁子模式进行筛选的索引构造算法。实验结果验证了该方法的有效性。     

基于邻域等价类的同构子图搜索算法

节点异质图常作为复杂网络的数据模型,同构子图搜索是异质图挖掘过程中的重要问题,但现有算法的子图去重步骤降低了搜索效率。为此,基于Turbo_(ISO)算法中的邻域等价类(NEC)概念,提出同构子图搜索算法NEC-COMB。该算法包含预处理、节点顺序确定、子图同构匹配和子图提取4个部分,在子图同构匹配时对NEC中的节点使用组合策略,避免等价节点重复匹配。实验结果表明,与经典算法VF2,GraphQL,Turbo_(ISO)相比,NEC-COMB可有效提高搜索效率,优化去重效果。     

LSI芯片图象的双子图同构匹配法

本文提出一种用于LSI芯片图象的双子图同构匹配方法.该方法是在芯片分割图象的区 域邻接图上搜索同构匹配结点间的对应关系. 同构匹配算法利用启发信息提高搜索的效率.算法根据专门建立的区域相似性度量和环 境串匹配值这些判据选取同构匹配起始结点. 文中将详细说明双子图同构匹配法的原理,并提供匹配结果.本算法已在实际中采用.     

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

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

选择-验证-过滤:一种迭代的子图包含查询处理机制

近年来,图模型广泛应用于生物信息、计算化学、语义网等领域.目前,"过滤-验证"机制被广泛用于子图包含查询,即首先根据图数据的特征构造索引,然后根据索引产生候选集,最后对候选集中的每一个图进行子图同构验证.在这类算法中,"过滤"阶段是关注的重点,力争过滤掉更多的数据;而"验证"阶段则只是单纯地进行候选图子图同构检测,并没有进一步优化查询性能的可能.因此,提出了一种新的子图包含查询的迭代处理机制:"选择-验证-过滤",可利用从子图同构验证过程中得到的信息,结合数据库中图数据之间的相关关系,进行迭代查询处理.该机制首先选择数据库中的图与查询图进行同构验证,然后根据本次验证得到的信息,结合图数据之间的子图映射关系,进行迭代查询处理.一旦子图同构验证成功则可直接获得查询结果,而若验证不成功,则可以缩小下次迭代的查询搜索空间.为提高验证成功概率,提出了一种基于搜索空间预测的图选择策略.大量实验表明,该算法具有较"过滤-验证"机制更高的查询处理性能.     

基于拓扑序列的DAG子图包含查询算法研究

图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,...     

一种处理图数据库中超图集合的查询方法

针对图数据库中超图集合查询问题给出有效解决方案,算法采用过滤-验证框架机制,过滤器是基于特征的索引树。给出从数据库中快速提取特征的算法以及索引建立方法。将特征组织在一棵树中,使得过滤阶段两个特征的公共诱导子图只与查询图做一次子图同构测试。在验证阶段,将Ullman算法与极大团查找算法相结合进行子图同构检测。     

基于增量信息索引的子图查询算法

当前图数据库中的子图同构查询算法主要是依赖倒排索引,然而处理那些具有庞大数据的数据库和复杂的查询愈发成为挑战。研究目的是设计一个算法,使用新的索引作为查询处理的核心,记录查询图的每一个细小改变,并使用一种特殊的数据结构来维护。先是引出一个索引算法,然后逐渐分析整个索引、查询过程,并利用该算法实现一个系统,最后在不同数据集和查询上进行实验。实验证明了该算法具有良好的时间、空间效率和扩展性。新的索引算法能够支持更大的查询图和更加灵活的查询。通过实现的系统和其他系统的对比实验,验证了算法的有效性。     

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

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

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

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

基于特征索引的图相似查询过滤算法

分析图相似查询候选集的产生过程以及特征图之间的关系对候选图集的影响,提出一种基于特征索引的图相似查询过滤算法,使用GIndex算法建立特征图索引结构,通过特征图之间的选择性关系给出一个有序的特征集,并借助特征-图矩阵对数据库进行筛选得到候选图集。实验结果证明,该方法能准确地产生候选图集,从而提高图查询的效率。     

基于最小Steiner树的关键词查询方法

在关系数据库中,关键词查询无需用户学习查询语言和数据库模式相关知识,而且有效地扩大了查询范围.采用元组图描述关系数据库中元组关系,可使关键词查询问题转化为元组图的最小Steiner树求解问题.本文提出元组图上基于相似度的边权重计算方法,使边权重能够反映元组与关键词相似度的大小.然后,鉴于最小Steiner树求解问题是NP-完全问题,提出按照贪心策略执行Dijkstra算法的最小Steiner树较优解求解算法.最后,通过实验对算法进行了分析和验证.     

基于SQL的图相似性查询方法

图作为一种表示复杂信息的数据结构,被广泛应用于社交网络,知识图谱,语义网,生物信息学和化学信息学等领域.随着各领域应用的普及和深入开展,如何管理这些复杂图数据是目前图数据库技术面临的巨大挑战.图的相似性查询是图数据管理中的热点问题之一.对图查询问题的研究主要包括图的相似性查询等.本文重点研究基于编辑距离（Graph Edit Distance）的图相似性查询处理问题.首先,通过对目前代表性的问题求解算法分析发现,其提出的过滤规则都具有自己的优缺点和适用性.其次,针对已有方法在过滤阶段自身存在优缺点和适用性的问题,提出一种全新的面向关系型数据库的过滤框架,新的过滤框架可以支持所有已有的过滤规则,从而通过结合不同的过滤规则来优化图相似查询算法以提高查询效率.该方法可以最大程度保留不同过滤规则的优点并克服其缺点,从而对不同查询具有普遍适用性.最后,基于PubChem数据集,通过比较算法在求解查询结果的时间消耗,验证本文提出算法的高效性及可扩展性,实验结果表明,本文提出的方法优于现有算法.     

基于gSpan的数据筛选算法研究与应用*

针对图结构数据库中如何实现图结构的快速有效检索问题,提出了一种新的数据筛选算法。它在gSpan算法原理的基础上引入了新的剪枝规则,修改了DFS编码的形式。其次利用改进后的gSpan挖掘出频繁图结构的DFS编码,以此建立索引并对图结构分类。最后将新算法应用于化学数据库,实验结果证明了该算法的正确性和高效性。     

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.     

面向图相似性搜索的高效图编辑距离算法

在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。     

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

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

Fast graph similarity search via hashing and its application on image retrieval

Similarity search in graph databases has been widely investigated. It is worthwhile to develop a fast algorithm to support similarity search in large-scale graph databases. In this paper, we investigate a k-NN (k-Nearest Neighbor) similarity search problem by locality sensitive hashing (LSH). We propose an innovative fast graph search algorithm named LSH-GSS, which first transforms complex graphs into vectorial representations based on prototypes in the database and later accelerates a query in Euclidean space by employing LSH. Because images can be represented as attributed graphs, we propose an approach to transform attributed graphs into n-dimensional vectors and apply LSH-GSS to execute further image retrieval. Experiments on three real graph datasets and two image datasets show that our methods are highly accurate and efficient.     

基于谱特征和图分割的图聚类算法

为了对图数据库中的结构化数据有效的聚类分析,首先对不同的图数据样本进行特征的深度挖掘,构造了包含节点间连接层次关系的关联度矩阵,与拉普拉斯矩阵结合共同完成谱特征分析;然后利用高斯核函数进行相似度矩阵的构建,将相似度归一化到0到1的范围内便于后期处理;最后结合图分割与k-means算法将相似度矩阵进行k分割,得到k个聚类。经过大量分析实验表明,改进的拉普拉斯矩阵对样本内部结构有更为精细的划分,提高了前期样本处理效果。最小比率割算法在保证精度的前提下,将NP难的问题转化为多项式时间内解决的问题,提高了算法的效率。