| ¡¡ | Chinese Journal of Computers Full Text |
| Title | Efficient Query Processing on Uncertain Graph Databases |
| Authors | ZHANG Shuo GAO Hong LI Jian-Zhong ZOU Zhao-Nian |
| Address | (School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001) |
| Year | 2009 |
| Issue | No.10(2066¡ª2079) |
| Abstract & Background | Abstract 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. Keywords uncertainty; uncertain graph; top-k query; query processing; graph indexing |