Font Size: a A A

Mining Frequent Subgraph Based On Pre-clipping In Uncertain Graph Databases

Posted on:2017-11-08Degree:MasterType:Thesis
Country:ChinaCandidate:J JiaFull Text:PDF
GTID:2348330503472498Subject:Computer technology
Abstract/Summary:PDF Full Text Request
With the development of information technology. Researchers in various fields began to use graph data structures to represent relationships between data objects. Because of the large amount of information in the graph data, it is of great academic value and practical significance to dig out the knowledge between different data object, It has obtain the wide attention and research for it can obtain a lot of valuable information.In many fields, however, because of the limited of data acquisition technology and the unaccurate of data.The data we obtained is uncertain.the graph data which contain uncertain property is called the uncertain graph data. Mining frequent subgraphs in uncertain graph data also has theoretical and practical significance.MUSE algorithm is the first efficient algorithm for mining frequent sub graph mining in uncertain graph databases. It successful reduce the complexity of the isomorphism of the subgraph to the linear level from the exponential level by calculate approximate isomorphic probability of the subgraph. However, the computational efficiency is still low when the scale of the database is large. Subgraph isomorphism probability calculation is the most important part in frequent subgraph mining. It needs to find out all the embed graph while calculate the probability of subgraph isomorphism. So edge index is built to find out the approximate embed graph quickly without subgraph isomorphism testing. At the same time, a approximate calculation method of sub graph isomorphism is introduced which does not consider the coincident relationship of subgraph model. MUSE+ algorithm is created combine the MUSE algorithm with the approximate calculation of subgraph isomorphism and approximate graph embedded sets.Experimental results show that in most cases, the MUSE+ algorithm performance better with the support threshold improve by using mixed strategy compare with the MUSE algorithm under the same data set.
Keywords/Search Tags:uncertain graph, frequent sub graph model, expected degree of support, uncertain graph index, data base
PDF Full Text Request
Related items