Studies And Implementation On Pattern Match Queries Over Uncertain Planar Graphs

With the rapid development of the Internet technology and new science/technoloise, there comes more and more applications on the basis of graph structure, i.e., bioinformatics, social networks and World Wide Web. Uncertainties have widely appeared on graph data due to the inaccurate measurements and noise brought by graph itself. In recent years, the study on uncertain graph data management becomes an hot topic and acquires more and more emphasis from scientists all over the world. However, existing technologies on certain graph data and uncertain data cannot be used to deal with uncertain graph data. Therefore, we should develop novel solutions and technologies to support management on uncertain graph data. Pattern match search over uncertain graphs is very important and have many real applications in reality.This thesis mainly studies the technology of query processing on pattern match queries over uncertain planar graphs. Firstly, this paper use the possible world semantics, to model uncertain graph, and then formally define pattern match query over uncertain graphs. Based on the possible world model, this paper first proposes a straightforward approach to compute the query, i.e., enumerating all the possible world that match the query and summarizing their existence probabilities. However, the number of possible world increase in exponential, and thus the naive method is impractical. To avoid the huge computational costs, this paper also proposes a "solution tree" algorithm to exactly compute the accurate the final answers. In the solution tree, this paper defines successful event, failed event and uncertain event, based on which the algorithm decomposes uncertain event in each level of the solution tree, and adds up all the probabilities over all successful events. The summarize result is the matching probability.To further speed up the algorithm, the paper proposes four optimized algorithms,(1) isjoint match/cut:this method constructs disjoint matches and cuts of uncertain graph to approach bounds of matching probability;(2) Isomorphic graph reduction:this method improves efficiencies by combining all isomorphic graphs produced in solution tree;(3) Uncertain event bound:this method adds up all probabilities across failure and successful events and use these probabilities to filter out false positive results;(3) Sampling:this method simulates the producing process of possible worlds, and thus can quickly answer the query. Finally, this paper verifies the effectiveness of the proposed solutions for UPM queries through extensive experiments on real/synthetic uncertain graph datasets.