子图匹配算法研究
时间:2019-07-21 09:56 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：图形数据库是基于图论，主要用来描述和存储图中所包含的节点以及这些节点之间关系的一种数据库。在图形数据库中，子图匹配问题是一个研究热点。现有的很多算法都采用的是静态消耗测算模式在搜索边和节点上查询时间长，计算效率低。因此，本文围绕这个问题展开研究，主要介绍了子图匹配的相关定义和子图同构问题。通过分析子图同构算法和改进后的精简过程算法，最后引入信息熵，根据信息熵的作用以及它在匹配算法中的可行性，实现以信息熵为基础的子图匹配算法。37325 毕业论文关键词：图数据；信息熵；子图匹配 The Research on Graph Matching Algorithm Abstract:Graphical database is based on graph theory, which is a kind of graph theory,mainly used to describe and store the nodes in graph or the relationship between these nodes. In the graphics database, the sub-graph matching problem is a hot research topic. Many of existing algorithms adopt the static consumption calculation model ,but it spends long time in querying and has low efficiency in calucating.Therefore, this paper focuses on this issue, mainly introduces the related definitions about subgraph matching and the subgraph isomorphism problem .Through the analysis of subgraph isomorphism algorithm and the improved streamline process algorithm, finally, the information entropy is introduced.According to the role of information entropy and its feasibility in matching algorithm, implentate the sub-graph matching algorithms based on information entropy. Keywords: Graph; Information Entropy; Sub graph matching query 目 录 摘 要 1 引言 2 1图数据研究的相关课题及现状 2 1.1研究课题 2 1.2目前国内外研究状况 2 2 概念介绍 3 2.1子图匹配的的有关定义 3 2.2子图同构问题的定义 3 2.3信息熵 3 3 子图匹配的两种算法 4 3.1子图同构相关的算法 4 3.2基于信息熵的子图匹配算法 7 4实验分析 9 5结束语 10 参考文献 10 致 谢 12 子图匹配算法研究 引言 随着信息技术的飞速发展和数据的不断更新。怎样检索这些大量的数据成为数据库研究的一个热门问题。这些大量的数据中存在着很多图示数据。当前很多数据库系统只是对关系型数据提出了存储策略和查询优化策略[3]。所以这些图数据的检索和存储成了一个热点就话题。 1图数据研究的相关课题及现状 1.1研究课题 目前图数据库研究的有如下主要课题： (1)图数据库中的索引策略和查询优化。怎样快速响应用户的查询，是数据库主要研究的问题。跟传统的关系型数据一样，一个好的索引可节省很多搜索时间。图数据库的查询大致可分为两类： ①匹配查询。在图数据中找到与其匹配的地方，如子图匹配查询。 ②基于路径的查询。这种查询主要是讨论两点间的最短距离。 （2）图数据库中的数据挖掘。传统的数据挖掘的对象是关系型数据。如何从大量的图数据中找到有效的模式，成为数据挖掘的新课题。 1.2目前国内外研究状况 由于社交网络的发展，图数据库的查询处理得到了广泛应用。因此，子图匹配算法具有很好的发展前景。 目前已有的很多算法都比较复杂难以计算，并且查询的效率也比较低。本文主要围绕图数据库中的“子图匹配查询”这个核心问题展开。图数据库可分为两种：一种是事务性数据库；一种是单图数据库。事务性数据库在响应查询时，要告诉你哪个数据图中有匹配；单图数据库数据库在响应匹配查询时，要告诉你匹配在数据图中出现的位置。 (责任编辑：qin) |