Graph database, and its tale on uncertainty

In the real world, many complex objects are modelled as graphs. For instance, social networks, protein interaction networks, chemical compounds, World Wide Web, network design, work flows, and etc. While many models utilise Certain Graphs, in some cases, uncertainty on data is inherent, thus they are more precise to be modelled as Uncertain Graphs. This thesis studies three fundamental problems in processing and analysing both Certain Graphs and Uncertain Graphs. These problems are: (1) Uncertain Reachability (2) Certain Graph All-Matching (3) \Probabilistic Supergraph Search. The first problem, Uncertain Reachability, studies the techniques of answering reachability queries over an Uncertain Graph. The traditional reachability answers whether or not there exists a path between a source node and a destination node. Whereas in Uncertain Graphs, it is to determine if a source node could reach a destination node with probability larger than a user specified probability value θ. Uncertain Reachability has been shown to be NP-hard. We first propose novel and effective bounding techniques to obtain the upper bound of reachability probability between the source and destination. If the upper bound fails to prune the query, an efficient Monte Carlo simulation technique will be applied to answer the Uncertain Reachability query with an accuracy guarantee. The second problem, Certain Graph All-Matching, studies the problem of finding all subgraphs of a database graph $g$, which are isomorphic to the given query graph $q$. In this thesis, we have observed that the neighbourhood signature can effectively prune the search space. Based on this pruning technique, this thesis further proposes an eager verification algorithm which aims to identify false matches as early as possible. The last problem, Probabilistic Supergraph Search, studies the problem of retrieving data graphs g^u from a uncertain graph database, $D$ such that the probability of $q$ containing g^u is not smaller than θ. In this thesis, we present several effective pruning rules to dramatically reduce the search space. In addition, we propose an efficient algorithm to verify the remaining candidates.

Grantor dc:publisher

UNSW, Sydney

Year dc:date

2013

Author dc:creator

• Zhu, Ke

• Uncertain Data
• Graph
• Database

Statement dc:rights

• open access
• CC BY-NC-ND 3.0
• free_to_read

Licence

• https://purl.org/coar/access_right/c_abf2
• https://creativecommons.org/licenses/by-nc-nd/3.0/au/

Language dc:language

EN

Identifier

https://doi.org/10.26190/unsworks/16195

OAI identifier oai:identifier

oai:unsworks.library.unsw.edu.au:1959.4/52699