The Technology Of Index And Isomorphism Query Based On Encoding Graph

Graph is a basic data structure, and it is also an important research object in computer science area. Alone with the rapid development of computer network technology and the increasing demand for graph datas storage management, the study of graph datas caught the serious attentions in recent years. It is the basis work of other graph datas operations that building graph data index struct and the query processing of graph isomorphism, at the same time it is one of the most challenging key technologies.In this thesis, the research focuses on the creation of graph data index, the determinant of graph isomorphism and the study of encoding graph related technologies. And then based on original study, a new graph index struct which is based on coding graph and a graph isomorphism query processing method are presented. The core ideas of the technology are: designing a graph storage structure which is easy to encode, and then meet the mapping relationship between graph and coding. The graph coding set is a partial order set, so there is a clear relationship between any two graph codings (the coding is converted to corresponding vector), then the existing index structs can be utilized to improve the query efficiency.Tht contributions of the technology that index and isomorphism query based on encoding graph mainly lie in the following areas:Firstly, the "maximum adjacency matrix" concept is proposed. It is one of graph storage structures that can meet the one-to-one mapping relationship between graphs and codings, so it is a good solution for the problem of one-to-many mapping relationship between graphs and memory types, which is difficult to solve. At the same time, the maximum adjacench matrix itself is an adjacency matrix, so it is able to compatible with other existing graph storge methods perfectly.Secondly, an encoding graph method is designed. It can be well applied to determine graph isomorphism because of the one-to-one mapping relationship between graph and the encoding, any two codings have a size relationship, and their codings are eaqual only when the two corresbonding graphs are isomorphism, so we can determine whether the two graphs are isomorphism by comparing the coding characters. The experiments show that our encoding method has an obvious advantage to traditional ways on the responding time.Thirdly, an index structure is created that can support querying graph isomorphism. Previous querying methods are all based on traversalling and pruning. But our method utilizes index structure to support querying isomorphism, so it can avoid traveling effectively, and reduce the times of comparing, then improve the querying efficiency. Finally, experiments show that the querying efficiency of the index and isomorphism query technology based on encoding graph proposed in this paper is higher than that of the traditional determine and query methods, especially when the scale of graphs is large and the edge density is dense, which expresses a great deal of usability and efficiency.