A Scalable Unbiased Sampling Method Based on Multi-Peer Adaptive Random Walk
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    To deal with the scalable and fast unbiased sampling problems in unstructured P2P systems, a sampling method based on multi-peer adaptive random walk (SMARW) is proposed. In the method, based on the multi-peerrandom walk process, a set of provisional peers are selected as agents which start the sampling processes, by whichthe sampling process is speeded up with receiving a set of tunable number samples each time; Meanwhile, afterreceiving new samples earlier agents are replaced with these new samples which repeat the sampling process. Withthis simple replacement, it can be guaranteed with high probability that the system can reach the optimal loadbalance; furthermore, SMARW adopts an adaptive distributed random walk adjustment process to increase theconvergence rate of the sampling process. A detailed theorical analysis and performance evaluation confirm thatSMARW has a high level of unbiased sampling and near-optimal load balancing capability.

    Reference
    Related
    Cited by
Get Citation

符永铨,王意洁,周婧.基于自适应随机行走的可扩展无偏抽样方法.软件学报,2009,20(3):630-643

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 30,2007
  • Revised:October 12,2007
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063