###
DOI:
Journal of Software:2009.20(3):630-643

基于自适应随机行走的可扩展无偏抽样方法
符永铨,王意洁,周婧
(国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073;工程兵指挥学院 计算机教研室,江苏 徐州 221000)
A Scalable Unbiased Sampling Method Based on Multi-Peer Adaptive Random Walk
FU Yong-Quan,WANG Yi-Jie,ZHOU Jing
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3055   Download 3835
Received:June 30, 2007    Revised:October 12, 2007
> 中文摘要: 针对非结构化P2P 系统中可扩展的快速无偏抽样问题,提出了一种基于多个peer 自适应随机行走的抽样方法SMARW.在该方法中,基于代理随机行走选择一组临时的peer 执行抽样过程,一次产生一组可调数目的抽样节点,提高了抽样速度,选择每次产生的抽样节点作为临时peer 进行新的抽样过程,这种简单的方法可以保证系统具有近似最优的系统负载均衡程度.同时,SMARW 利用自适应的分布式随机行走修正过程提高抽样过程的收敛速度.理论分析和模拟测试表明,SMARW 方法具有较高的无偏抽样能力以及近似最优的系统负载均衡程度.
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.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60873215, 60621003 (国家自然科学基金); theNational Basic Research Program of China under Grant No.2005CB321801 (国家重点基础研究发展计划(973)); the SpecializedResearch Fund for the Doctoral Program of Higher Education of China No.200899980003 (高等学校博士学科点专项科研基金); theFoundation for the Author of National Excellent Doctoral Dissertation of China under Grant No.200141 (高等学校全国优秀博士学位论文作者专项); the Graduate Research Innovation Fund of NUDT of China under Grant No.B080602 (国防科学技术大学优秀研究生创新资助) Supported by the National Natural Science Foundation of China under Grant Nos.60873215, 60621003 (国家自然科学基金); theNational Basic Research Program of China under Grant No.2005CB321801 (国家重点基础研究发展计划(973)); the SpecializedResearch Fund for the Doctoral Program of Higher Education of China No.200899980003 (高等学校博士学科点专项科研基金); theFoundation for the Author of National Excellent Doctoral Dissertation of China under Grant No.200141 (高等学校全国优秀博士学位论文作者专项); the Graduate Research Innovation Fund of NUDT of China under Grant No.B080602 (国防科学技术大学优秀研究生创新资助)
Foundation items:
Reference text:

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

FU Yong-Quan,WANG Yi-Jie,ZHOU Jing.A Scalable Unbiased Sampling Method Based on Multi-Peer Adaptive Random Walk.Journal of Software,2009,20(3):630-643