Recursive Stratified Sampling: A New Framework for Query Evaluation on Uncertain Graphs
Rong-Hua Li, Jeffrey Xu Yu, Rui Mao, Tan Jin · IEEE Transactions on Knowledge and Data Engineering · 2015
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 ofNMC, we propose two efficient estimators, calledRSS-IandRSS-IIestimators, based on the idea of recursive stratified sampling (RSS). To further reduce the variances ofRSS-IandRSS-II, we propose a recursivecut-setbased 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 ofNMC. Moreover, the time complexity of all the proposed estimators are the same as that ofNMCunder 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.