Font Size: a A A

Research On Graph Similarity Search On Uncertain Graph Databases

Posted on:2018-05-14Degree:MasterType:Thesis
Country:ChinaCandidate:F H ChenFull Text:PDF
GTID:2348330512987348Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Recently,graph data models have attracted increasing research interest,because many data in various applications can be represented by graphs.The growing popularity of graph data needs efficient management techniques.Thus,many queries have been investigated to solve the problems of graph similarity search,including bioinformatics,social network analysis,chemical compounds and so on.It has been widely used in these fields.But all of the works assume that the data graphs are certain.However,in reality,graphs are often noisy and uncertain due to various factors.For example,the errors in data extraction,inconsistencies in data integration,and privacy preserving purposes.Therefore,we study graph similarity search on uncertain graph databases in this paper.In the previous research,they usually assume that the edges in an uncertain graph are independent of each other.But in this paper,we study the uncertain graphs where edges occurrences are correlated.As usual,the problem of graph similarity search over probabilistic graphs is NP-hard.Thus,we employ a filter-and-verify framework to solve the problem so that we can speed up the search.We propose a systematic method to solve the similarity search problem on uncertain graph databases based on graph edit distance.Firstly,we propose a partition-based lower bound to make the ability of pruning be stronger.It is defined as a structure consisting of one vertex and its adjacent edges without including the other end points.The advantage of partition is that a single edit operation can affect only two partitions at most.Secondly,we propose the uncertain graph similarity search based on the lower bound of graph edit distance.It contains three part that structural optimization pruning,uncertain optimization pruning and verification.We compute the graph similarity probability of the query graph and the uncertain graph of the uncertain graph database.If the graph similarity probability no smaller than the threshold of graph similarity,it is our candidate.If the graph similarity probability is smaller than the threshold of graph similarity,we prune the graph.At last,extensive experiments confirm the efficiency of our proposed solutions that based on the lower bound of graph edit distance to solve the graph similarity search on uncertain graph database.
Keywords/Search Tags:graph edit distance, uncertain graph databases, graph similarity search, lower bound
PDF Full Text Request
Related items