The Query Research Based On Reachability Of Uncertain Graph

As a typical data model to deal with large-scale data, graph has been widelyconcerned. Many kinds of data can be abstracted into graphs, such as protein interactionnetworks, social networks, RDF data and so on. With the improvement of dataprocessing technology, the requirement of the accuracy of data is getting higher, andnoises and errors in data’s acquisition and processing are included into studies. With thesubject extending to uncertain data from certain data, the model expands to uncertaingraph model, adding probability dimension to the certain graph. Due to the increasedprobability dimension, the researching results in certain graphs can not be applied touncertain graphs directly. So we need to explore new methods. There are a variety ofresearches on uncertain graph including query processing, data mining, dividing and soon. This article studies the reachability queries and pattern matching queries.Given an uncertain graph G, two vertex s and t in G and distance threshold d, thereachability query returns the probability that s and t is reachable within d. This paperproposes a sampling based reachability query processing algorithm. First, define a graphinstance classification tree to partition the possible graph instances of an uncertain graph.In order to improve the efficiency on retrieving the graph instance classification tree, abi-directional graph traversal based classification tree is designed. Finally, thethreshold-based reachability query is processed by random sampling on theclassification tree. The performance of the algorithm is evaluated through theoreticalanalysis and experimental verification.In the pattern matching query, we studies one matching problem which has notbeen studies ever. First, we give the definition of probability threshold-based patternmatching in uncertain graphs. Second, we explain the methods including thesimplification of pattern graph and filter-verify mode manipulating probabilitythreshold-based reachability queries and the matching processing. Finally, theeffectiveness of the methods are verified by experiments.