Recursive Stratified Sampling: A New Framework for Query Evaluation on Uncertain Graphs

Uncertain graph management has been recognized as an important research topic in recent years. In this paper, we first introduce two types of query evaluation problems on uncertain graphs, named expectation query evaluation and threshold query evaluation. Most previous solutions for these problems are based on naive Monte-Carlo (NMC ) sampling, which typically result in large variances. To reduce the variance of NMC, we propose two efficient estimators, called RSS-I and RSS-II estimators, based on the idea of recursive stratified sampling (RSS). To further reduce the variances of RSS-I and RSS-II, we propose a recursive cut-set based stratified sampling estimator for a particular kind of query evaluation problem. We show that all the proposed estimators are unbiased and their variances are significantly smaller than that of NMC. Moreover, the time complexity of all the proposed estimators are the same as that of NMC under a mild assumption. In addition, we develop an elegant graph simplification technique to further improve the accuracy and running time of our estimators. We also apply the proposed estimators to three different uncertain graph query evaluation problems. Finally, we conduct extensive experiments to evaluate the proposed estimators, and the results show the accuracy, efficiency, and scalability of our estimators.