Abstract
In this paper, we introduce a novel, general purpose, technique for faster sampling of nodes over an online social network. Specifically, unlike traditional random walks which wait for the convergence of sampling distribution to a predetermined target distribution - a waiting process that incurs a high query cost - we develop WALK-ESTIMATE, which starts with a much shorter random walk, and then proactively estimate the sampling probability for the node taken before using acceptance-rejection sampling to adjust the sampling probability to the predetermined target distribution. We present a novel backward random walk technique which provides provably unbiased estimations for the sampling probability, and demonstrate the superiority of WALK-ESTIMATE over traditional random walks through theoretical analysis and extensive experiments over real world online social networks.
Original language | English (US) |
---|---|
Pages (from-to) | 678-689 |
Number of pages | 12 |
Journal | Proceedings of the VLDB Endowment |
Volume | 8 |
Issue number | 6 |
DOIs | |
State | Published - 2015 |
Event | 41st International Conference on Very Large Data Bases, VLDB 2015 - Kohala Coast, United States Duration: Aug 31 2015 → Sep 4 2015 |
All Science Journal Classification (ASJC) codes
- Computer Science (miscellaneous)
- General Computer Science