Efficient query processing on uncertain graph databases

In recent years, lots of data in various domains have been naturally modeled by graphs, e.g. protein interaction networks, social networks, etc. Uncertainty is inherent in many of these graphs due to the imprecise characteristics of equipments or the nature of data. This paper addresses efficient query processing on uncertain graph databases. A data model is proposed for representing uncertainties in graphs, and a new formulation for probabilistic top-k subgraph matching query is presented. An effective index structure based on neighborhood subgraphs with probabilistic information in uncertain graphs in databases is devised. In addition, based on indexes, an efficient search-tree based algorithm with probabilistic pruning techniques is proposed to search large uncertain graphs. Experimental results show that the proposed algorithms are efficient and scalable.