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 () sampling, which typically result in large variances. To reduce the variance of , we propose two efficient estimators, called and estimators, based on the idea of recursive stratified sampling (). To further reduce the variances of and , we propose a recursive 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 . Moreover, the time complexity of all the proposed estimators are the same as that of 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.