主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
符永铨,王意洁,周婧.基于自适应随机行走的可扩展无偏抽样方法.软件学报,2009,20(3):630-643
基于自适应随机行走的可扩展无偏抽样方法
A Scalable Unbiased Sampling Method Based on Multi-Peer Adaptive Random Walk
投稿时间:2007-06-30  修订日期:2007-10-12
DOI:
中文关键词:  无偏抽样  非结构化P2P 系统  随机算法  可扩展性
英文关键词:unbiased sampling  unstructured P2P system  randomized algorithm  scalability
基金项目: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 (国防科学技术大学优秀研究生创新资助)
作者单位
符永铨 国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073 
王意洁 国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073 
周婧 工程兵指挥学院 计算机教研室,江苏 徐州 221000 
摘要点击次数: 3085
全文下载次数: 3859
中文摘要:
      针对非结构化P2P 系统中可扩展的快速无偏抽样问题,提出了一种基于多个peer 自适应随机行走的抽样方法SMARW.在该方法中,基于代理随机行走选择一组临时的peer 执行抽样过程,一次产生一组可调数目的抽样节点,提高了抽样速度,选择每次产生的抽样节点作为临时peer 进行新的抽样过程,这种简单的方法可以保证系统具有近似最优的系统负载均衡程度.同时,SMARW 利用自适应的分布式随机行走修正过程提高抽样过程的收敛速度.理论分析和模拟测试表明,SMARW 方法具有较高的无偏抽样能力以及近似最优的系统负载均衡程度.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利