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

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

基于邻居向量的近似子图匹配

将近似子图匹配分成节点匹配和边匹配两个阶段。将数据图中所有节点的h-邻居节点表示成向量形式,采用一种启发式推理算法进行节点匹配得到节点对应关系,使用查询节点权重提高匹配相似度,使用节点过滤、索引技术和孤立候选节点提高运算效率;利用邻居向量索引得到匹配节点集合的扩展图,进行边匹配,得到匹配图。在真实数据上进行实验,实验结果表明,该算法效果较好,运算效率较高,可以应用于节点标签稀疏的情况和top-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的查询响应时间更短，具有更高的查询效率。     

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

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

基于自学习近邻图策略的短文本匹配方法

针对自然语言处理中的文本匹配问题,提出一种基于自学习文本近邻图框架的深度学习模型,以处理短文本匹配问题。文本近邻图可使用词嵌入将文本转换为向量形式,再通过构建文本相似度关系矩阵获得,可表达文本样本的近邻关系。现有方法通常构造静态的近邻图,这些方法一方面依赖先验知识,另一方面难以获得句子对的最优表示。因此,提出了利用孪生卷积神经网络学习更优的动态更新的近邻图。该模型在Quora数据集上的准确率和◢F◣▼1▽值分别是84.15%和79.88%,在MSRP数据集上的准确率和◢F◣▼1▽值分别是74.55%和81.63%。实验表明,提出的模型能有效地提高文本识别和匹配的准确率。     

异构图形数据的近似语义匹配技术研究

以流程工厂协同设计应用为背景,提出基于允许误差的最大语义图匹配（MSMGE）算法的异构图形数据近似语义匹配模型。利用类无向图来描述2D和3D异构图形数据的工程属性和拓扑关系,消除了图形信息的异构性,并建立各种类实体的属性标签词典来消除2D和3D属性信息的异构性,用语义表达式来表示类无向图顶点和边的语义关系,将异构图形匹配转化为近似语义图匹配。通过基于工程语义对类无向图进行语义分割和基于最大公共序列算法的语义表达式比较、语义规整和语义裁剪等方法,降低了匹配搜索空间,提高了近似语义图匹配效率,实现了近似语义图匹配判断。该研究已经在流程工厂设计软件中得到较好地应用。     

SQM:基于Spark的大规模单图上的子图匹配算法

针对大规模数据图下基于回溯法的子图查询算法的准确率低、开销大等问题，为提高查询准确率，降低大图下的查询开销，提出一种基于Spark的子图匹配（SQM）算法。首先根据结构信息过滤数据图，再将查询图分割成基本查询单元；然后对每一个基本查询单元分别匹配后进行Join操作；最后运用并行化提高了算法的运行效率，减小了搜索空间。实验结果表明，与Stwig、TurboISO算法相比，SQM算法在保证查询结果不变的情况下，速度提高了50%。     

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

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

面向图数据的结构化正则路径查询方法

正则路径查询是一种应用正则表达式在图数据上进行查询的技术,通常利用有限状态自动机实现查询匹配。现有正则路径查询方法的匹配结果为顶点对的序列,未能充分保留图的结构,为了解决这一问题,提出了一种面向图数据的结构化正则路径查询方法,通过在不同的序列间加以结构化约束,使得查询结果由路径转变为子图。为了实现这一目的,首先定义了一种结构化的正则路径查询语言,并设计了结构化的查询解析以及基于此结构的匹配算法。实验在模拟数据集和真实数据集上进行了测试与分析,验证了网络规模对查询速度的影响,并设置了对照实验。实验结果表明,提出方法能够在保证满足正则表达式约束的前提下实现结构化查询。     

基于近似子图的规则空间压缩算法

规则空间模型是一种高效的知识结构诊断模型，但较高的规则空间构造代价阻碍了在小规模、实时认知诊断中的应用.为了提高规则空间模型的可扩展性，提出使用近似子图生成理想属性模式集进而压缩规则空间的方法.近似子图能够通过忽略和测试项目无关的属性降低子图规模量级，从而有效缩减理想属性模式集规模，达到压缩规则空间的目的；同时通过构建顶点间的虚拟边模拟领域知识图上的传递依赖关系，使近似子图在不引入额外属性的前提下保持领域知识图上的依赖关系，实现对不合理属性模式的有效过滤.在此基础上，给出了构造规则空间所需的近似子图构造算法以及由近似子图生成理想属性模式集的方法.最后在标准测试集上开展了近似子图与依赖保持子图和顶点导出子图两种方法的性能对比实验，并将近似子图应用于实际教学认知诊断中验证其诊断准确率，实验结果表明近似子图能够在不损失诊断结果准确率的前提下显著压缩规则空间，降低规则空间模型应用于小规模、实时诊断的门槛.     

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.     

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

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

图数据流上时间尊重图模式匹配算法研究

现有的动态子图匹配研究中忽略了模式图中的时间信息,使用户难以得到想要查询的真实结果.针对这种情况,首先设计一种简洁的中间结果保存形式,将匹配结果直接在数据图中以图进行存储;接着改进边缘转换模型,当数据图有边插入/删除时对其快速增量维护并报告结果;最后根据边转换模型设计了一个时间尊重图模式匹配算法,提高了匹配搜索效率.对真实网络流量数据和综合社交流数据进行实验评估,结果表明算法能够有效减少图模式匹配的执行时间和空间花销.     

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

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

一种基于局部保形映射(LPP)的相关反馈方法

目前图像检索通常采用高效的图像降维算法和适当的相关反馈技术来提高检索的效率。局部保形映射(LPP)算法是保留图像本质特征的一种有效的线性降维算法。本文在LPP算法的基础上引入相关反馈技术,进一步提高了检索准确度。利用LPP算法得到降维子空间,在子空间上得出查询数据的k-近邻构成候选数据集,并与查询数据集构建一个权图G,通过弗洛伊德算法求得图G中任意两个数据点之间的测地线距离并排序进而得出反馈结果。实验表明,该算法提高了检索的准确度,并使检索结果得到一定的优化。