当前位置：文档之家 › Web caching and zipf-like distributions Evidence and implications

Web caching and zipf-like distributions Evidence and implications

  • 格式：pdf
  • 大小：790.52 KB
  • 文档页数：25

WebCachingandZipf-likeDistributions:Evidenceand

Implications

LeeBreslauPeiCaoLiFanGrahamPhillipsScottShenker

Abstract

ThispaperaddressestwounresolvedissuesaboutWebcaching.ThefirstissueiswhetherWebre-questsfromafixedusercommunityaredistributedaccordingtoZipf’slaw[Zip29].Severalearlystudieshavesupportedthisclaim[Gla94,CBC95,ABCdO96]whileotherrecentstudieshavesuggestedother-wise[NHo98,ACC98].ThesecondissuerelatestoanumberofrecentstudiesonthecharacteristicsofWebproxytraces,whichhaveshownthatthehit-ratiosandtemporallocalityofthetracesexhibitcer-tainasymptoticpropertiesthatareuniformacrossthedifferentsetsofthetraces[CI97,RV98,DMF97,GB97a,KLM97].Inparticular,thesecondissueiswhetherthesepropertiesareinherenttoWebaccessesorwhethertheyaresimplyanartifactofthetraces.AnanswertotheseunresolvedissueswillfacilitatebothWebcacheresourceplanningandcachehierarchydesign.Weshowthattheanswerstothetwoquestionsarerelated.WefirstinvestigatethepagerequestdistributionseenbyWebproxycachesusingtracesfromavarietyofsources.Wefindthatthedistribu-tiondoesnotfollowZipf’slawprecisely,butinsteadfollowsaZipf-likedistributionwiththeexponentvaryingfromtracetotrace.Furthermore,wefindthatthereis(i)aweakcorrelationbetweentheaccessfrequencyofaWebpageanditssizeand(ii)aweakcorrelationbetweenaccessfrequencyanditsrateofchange.WethenconsiderasimplemodelwheretheWebaccessesareindependentandthereferenceprobabilityofthedocumentsfollowsaZipf-likedistribution.Wefindthatthemodelyieldsasymptoticbehaviorsthatareconsistentwiththeexperimentalobservations,suggestingthatthevariousobservedpropertiesofhitratiosandtemporallocalityareindeedinherenttoWebaccessesobservedbyproxies.Finally,werevisitWebcachereplacementalgorithmsandshowthatthealgorithmthatissuggestedbythissimplemodelperformsbestonrealtracedata.Theresultsindicatethatwhilepagerequestsdoindeedrevealshort-termcorrelationsandotherstructures,asimplemodelforanindependentrequeststreamfollowingaZipf-likedistributionissufficienttocapturecertainasymptoticpropertiesobservedatWebproxies.

1Introduction

DuetotheexplosivegrowthoftheWeb,Webproxycachinghasrecentlyreceivedconsiderableattention.

ItisconsideredoneofthemostimportanttechniquesatreducingWebtraffic,whichaccountsforalarge

percentageofInternettraffictoday.Severalresearchershaveobservedthattherelativefrequencywith

whichWebpagesarerequestedfollowsZipf’slaw[Zip29].Zipf’slawstatesthattherelativeprobabilityofarequestforthe’thmostpopularpageisinverselyproportionalto1/.Glassman[Gla94]wasperhapsthefirst

useofZipf’slawtomodelthedistributionofWebpagerequestsandseveralotherauthorshavealsoapplied

Zipf’slawtothedistributionofwebrequests[CBC95,ABCdO96].However,recentlyseveralstudieshave

questionedwhethertherequestsdoindeedfollowZipf’slawandconcludedotherwise[NHo98,ACC98]

.OneofourgoalsinthispaperistoinvestigatetheapplicabilityofZipf’slaw.Usingsixtracesfromprox-

iesatacademicinstitutions,corporationsandISPs,wefindthatthedistributionofpagerequestsgenerally

followaZipf-likedistributionwheretherelativeprobabilityofarequestforthe’thmostpopularpageis

inverselyproportionalto1/,withtypicallytakingonsomevaluelessthanunity.Theobservedvaluesof

theexponentvaryfromtracetotrace.Thatis,therequestdistributiondoesnotfollowthestrictZipf’slaw

2(forwhich),butinsteadfollowsamoregeneralZipf-likedistributionwithvarying.Moreover,we

findthatthereislittlecorrelationbetweentheaccessfrequencyofadocumentanditssize;thatis,popular

documentsarenotnecessarilysmallerthanunpopularones.Thecorrelationbetweentheaccessfrequency

ofadocumentanditsrateofmodificationvariesfromverylowtonone,dependingonthetraces.These

resultsraisethepossibilitythat,forsomepurposes,onemightbeabletosufficientlymodelwebaccessesbyasimplemodelthatassumesindependentreferencesfollowingaZipf-likedistributionandnocorrelation

betweenrequestfrequencyandresponsesizeorrateofchange.

InlookingatWebproxytraces,researchershavealsoinvestigatedhowthehit-ratiodepends,asymptoti-

cally,onthecachesizeandthenumberofrequests,andhaveexaminedthetemporallocalityoftheserequest

streams[CI97,RV98,DMF97,GB97a,KLM97].Althoughvariousstudieshaveuseddifferentsetoftraces,

thefollowingthreequalitativeasymptoticpropertieshavebeenidentified:

Foraninfinitesizedcache,thehit-ratioforaWebproxygrowsinalog-likefashion1asafunction

oftheclientpopulationoftheproxyandofthenumberofrequestsseenbytheproxy.Caoetal.

observedthispropertyinDigitalEquipmentCorporation’sproxytraces[CI97,KMM96],Gribbleetal.observedthispropertyinUniversityofCaliforniaatBerkeley’sproxytraces[GB97a,GB97b]

andDuskaetal.observedthispropertyinanumberoftracesfromuniversityproxiesandISPprox-

ies[DMF97].

Thehit-ratioofaWebcachegrowsinalog-likefashionasafunctionofthecachesize.ManyWeb

cachingstudiesreachthisconclusion[ABCdO96,Gla94,CI97,WAS96,GB97a,RV98,CBC95,DMF97].

合集下载

【计算机科学】_web挖掘_期刊发文热词逐年推荐_20140722

【计算机科学】_web挖掘_期刊发文热词逐年推荐_20140722

序号科研热词推荐指数序号科研热词1页面聚类21关联规则2web挖掘22音乐情感3频繁访问页组13隐私保护4频繁子树挖掘14随机化回答5路径选择偏爱度15语义web使用挖掘6访问模式挖掘16网页内容分析7自适应站点17网络信息挖掘8聚类18粗糙聚类9紧密耦合19用户识别10粗糙集110日志本体11粗糙度111文章发布时间检测12矩阵112文档对象模型13相似度113文本消重14用户兴趣模型114文本挖掘15浏览预测115数据预处理16浏览兴趣度116数据挖掘17最大频繁项目集117数据场18文本分类118情感计算19数据挖掘119情感化20改进的mafia算法120影响度因子21搜索引擎121归纳逻辑编程22技术标准122异构系统23应用程序架构123势值24向量空间模型124事务识别25关联规则125事件进展图26信息抽取126事件时间线分析27中文自动分类127web日志挖掘28中文信息处理128web日志29web日志挖掘129web数据挖掘30web日志130web挖掘31web使用挖掘131web可信数据32web事务间关联规则132web信息提取33swrl133dom树扩展34markov模型134davies-bouldin指标35fca12008年2009年

高级项目经理在线考试试题与答案

高级项目经理在线考试试题与答案

 当前文档修改密码：8362839

 当前文档修改密码：8362839

 更多资料请访问.(.....)

更多企业学院：...../Shop/

《中小企业管理全能版》 183套讲座+89700份资料 ...../Shop/40.shtml

《总经理、高层管理》 49套讲座+16388份资料 ...../Shop/38.shtml

《中层管理学院》 46套讲座+6020份资料 ...../Shop/39.shtml

《国学智慧、易经》 46套讲座 ...../Shop/41.shtml

《人力资源学院》 56套讲座+27123份资料 ...../Shop/44.shtml

《各阶段员工培训学院》 77套讲座+ 324份资料 ...../Shop/49.shtml

《员工管理企业学院》 67套讲座+ 8720份资料 ...../Shop/42.shtml

《工厂生产管理学院》 52套讲座+ 13920份资料 ...../Shop/43.shtml

《财务管理学院》 53套讲座+ 17945份资料 ...../Shop/45.shtml

《销售经理学院》 56套讲座+ 14350份资料 ...../Shop/46.shtml

《销售人员培训学院》 72套讲座+ 4879份资料 ...../Shop/47.shtml

截至2011年5月

高级项目经理在线考试试题及答案 2011年5月真题

一、单选题（共40题）

1、问题: 在WINDOWS AZURE BLOB中，PUT BLOB方法一次最多可以上传（ ）MB的BLOB到云端服务器上。

答案: B

A) 32

B) 64

C) 128

D) 256

2、问题: 下面关于负载均衡描述不正确的是（ ）

答案: B

A) 负载均衡可以横向扩展服务器，提高网站响应速度

B) 用APACHE可以实现硬件负载均衡

C) 软件负载均衡成本低于硬件负载均衡

Web相互合作缓存置换改进算法的模拟实现

Web相互合作缓存置换改进算法的模拟实现

科技信息2008年第27期SCIENCE&TECHNOLOGYINFORMATION

0.引言Web缓存是一种在互连网关键节点存储经常访问的信息的一种技术,缓存代理进行工作时,用户访问的内容其实是保存在缓存当地的磁盘上的,当缓存剩余空间不足以存放新文档时,使用某种算法将缓存中的某个文档置换出去,以腾出足够的空间存放新的文档。缓存置换算法所做的事就是决定将哪一个文档将会被置换出缓存。1.现有的置换算法缓存置换算法是影响缓存系统整体性能的一个重要因素,目前已有的Web缓存置换算法大体可以划分为以下三类[1]:传统经典的置换算法及其直接演化,其代表算法有:①LRU最近最少使用算法;②LFU最不经常使用算法,即是将缓存内在固定的时间段内访问次数最少的内容置换出;③Pitkow/Recker提出的一种置换算法,如果Cache中所有内容都是同一天被缓存的,则将最大的文档置换出缓存,否则按LRU算法进行置换;基于缓存内容关键特征的置换算法[2-4],其代表算法有:①Size[2]置换算法,每次进行替换时,都将Cache中最大的文档替换出去;②LRU-MIN[3]置换算法,该算法力图使被置换的文档个数最少。③LRU-Threshold[3]置换算法,和LRU算法一致,只是大小超过某个固定值的文档不能被缓存;④LowestLacencyFirst[4]置换算法,将访问延迟最小的文档置换出缓存;基于代价的置换算法,该类算法使用一个代价函数对缓存中的对象进行评估,最后根据代价值的大小决定置换对象。其代表算法有:①Hybrid算法:算法对Cache中的每一个对象赋予一个效用函数,将效用最小的对象置换出缓存;②LowestRelativeValue算法,将效用值最低的对象置换出缓存;③LeastNormalizedCostReplacement(LCNR)算法:该算法使用一个关于文档访问频次、传输时间和大小的推理函数来确定置换文档;④Bolot等人提出了一种基于文档传输时间代价、大小、和上次访问时间的权重推理函数来确定文档置换;⑤Size-AdjustLRU(SLRU)算法:对缓存的对象按代价与大小的比率进行排序,并选取比率最小的对象进行置换。2.改进的置换算法2.1改进置换算法的理论基础本文主要从整个缓存组的磁盘空间利用率和本地缓存的命中率两个方面考虑缓存组的置换算法:争取实现二者的最优化,使较大的文档存储的份数少点,节约整个缓存组的空间,较小的文档存储的份数多点,提高本地缓存的命中率,从而降低延迟率。2.2ECTB的定义在本文中使用组成文档的数据块在缓存中的期望存储时间(ExpectCacheTimeofBlock,”ECTB”forshort)来表示磁盘空间的竞争度。具体定义为:设Victim(C,Ti,Tj)表示在有限时间(Ti,Tj)内被移出缓存C的文档的集合,而表示在时间(Ti,Tj)内被移出缓存C的文档的数量,则缓存C在有限时间(Ti,Tj)内的ECTB可以表示为:CacheExpCacheTimeBlock(C,Ti,Tj)=!D∈Victim(C,Ti,Tj)DocExpCacheTimeBlockLRU(D,C)Victim(C,Ti,Tj)DocExpCacheTimeBlockLRU(D,C)代表在缓存C中,文档D自上次被访问过之后,组成文档D的数据块在缓存C中保存的期望时间。2.3基于ECTB的置换算法本文中的置换算法,主要包括以下两个算法:请求缓存算法:请求缓存接收到用户请求以后,如果本地缓存没有命中,或者向相临节点或者向源服务器获取文档,然后在本地缓存备份。回复缓存算法回复缓存接收请求缓存的查询信息,告知请求缓存有或没有请求的文档。如果接收到用户请求文档的信息或者将本地缓存中的文档发送给请求缓存,或者向源服务器获取文档,发送给请求缓存,并在本地缓存备份。3.仿真模拟为了提高仿真的可信度,我们从Boston大学网站上下载了从1994年11月到1995年1月的代理服务器访问纪录[5],并对其数据进行精简,去除一些冗余的信息,使之适合本文的Web缓存仿真器。精简后的输入文件的格式为:Web服务器id(webserver_uid)、URL路径id(urlpath_uid)、文件大小(file_size)、延迟时间(latency)、上次修改时间(last_modified_time)。如下所示:1119345324660216773120306810webserver_uid表示用户请求的服务器的id,urlpath_uid表示用户请求的URL,file_size表示用户请求的文件的大小,latency表示用户请求的内容从服务器获取需要的持续时间,last_modified_time表示用户请求内容的上次修改的时间。由于我们从Boston大学网站上下载的日志记录没有last_modified_time字段,所以我们在测试中都假设last_modified_time为0。我们在Linux环境下用C语言对WisconsinSimulator[6]代码进行了修改,使之适合多缓存相互合作置换算法的仿真。实验中,我们使用的总的日志纪录为:10,821条,即用户总的请求数是:TotalRequests=10,821条;在所有请求中,用户请求不同的页面数为:TotalUniqueRequests=1,297条;用户请求的所有文档的大小为:TotalBytes=7.50644e+07;用户请求的不同页面的大小为:TotalUniqueBytes=4.831e+07。实验中我们使用一个随机数代表用户每次请求的缓存,所以程序每次运行的结果都会不同。使用仿真程序运行了三组数据,然后再根据三组数据取平均值。在实验中,我们做了以下假设:假设一:以下得出的实验数据全部都是基于分布式缓存体系结构的。采用的算法是基于LRU的改进的算法。假设二:缓存组中所有缓存的大小是一样的,则测试中,我们分别设置为TotalUniqueBytes的0.05%、0.5%、5%、50%。假设三:缓存组中每个缓存的ECTB初始值设置为0,即刚开始各个缓存都为空时,不管第一个请求多大,都进行缓存。实际中,由于缓存从本地获取文档相对于缓存从源服务器获取文档的时间要小的多,因此实验中我们假设从缓存获取文档的时间为0,因此,上面公式就可简化为:H_latency=Ni=1!t(1-Qi)Ni=1!t。在实验中,我们未考虑从其他缓存获取文档的时间,因此,实验的数据误差可能较大,但在缓存空间比较小时,由于命中率较低,误差会比较小,因此实验数据还是很有参考价值的。据此公式,我们可以得出以下实验数据。如下图表所示:

基于受限玻尔兹曼机的Web_服务质量预测方法

基于受限玻尔兹曼机的Web_服务质量预测方法

第49卷第11期 中南大学学报(自然科学版) Vol.49 No.11 2018年11月 Journal of Central South University (Science and Technology) Nov. 2018

DOI: 10.11817/j.issn.1672-7207.2018.11.015

基于受限玻尔兹曼机的Web服务质量预测方法

王兴菲1, 2，万健1, 2, 3，陈璐1, 2，殷昱煜1, 2，俞立峰4 (1. 杭州电子科技大学 计算机学院，浙江 杭州，310018；

2. 复杂系统建模与仿真教育部重点实验室，浙江 杭州，310018；

3. 浙江科技学院 信息与电子工程学院，浙江 杭州，310023；

4. 杭州核新同花顺网络信息股份有限公司，浙江 杭州，310023)

摘要：针对协同过滤算法无法有效处理数据稀疏的问题，提出1种基于受限玻尔兹曼机的Web服务质量(QoS)预测方法；第1阶段使用受限玻尔兹曼机模型对所有缺失的QoS值进行预测，并对原始的QoS矩阵进行填充；在第2阶段基于该QoS矩阵进行全局邻居筛选，同时将受限玻尔兹曼机引入到用户近邻的协同过滤模型中，以预测目标QoS值。研究结果表明：该方法能提高QoS预测精确度，在一定程度上降低数据稀疏对预测的影响。 关键词：Web服务；服务质量预测；协同过滤；受限玻尔兹曼机 中图分类号：TP312 文献标志码：A 文章编号：1672−7207(2018)11−2745−08 Web service QoS prediction based on

restricted Boltzmann machines

WANG Xingfei1, 2, WAN Jian1, 2, 3, CHEN Lu1, 2, YIN Yuyu1, 2, YU Lifeng4 (1. School of Computer, Hangzhou Dianzi University, Hangzhou 310018, China; 2. Key Laboratory of Complex Systems Modeling and Simulation of Ministry of Education, Hangzhou 310018, China; 3. School of Information and Electronic Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, China; 4. Hithink RoyalFlush Information Network Co. Ltd., Hangzhou 310023, China)