Uncertain graph management has been recognized as an important research topic in recent years. In this paper, we<br>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, ba
