self-organizing lists and independent references — astatistical synergy

《self-organizing lists and independent references — astatistical synergy》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SELF-ORGANIZINGLISTSANDINDEPENDENTREFERENCES—ASTATISTICALSYNERGYMichaHofri†andHadasShachnaiComputerScienceDepartment,Technion-IsraelInstituteofTechnologyHaifa32000,Israel(October1988,revisedApril1997).ABSTRACTLetR1,...,Rnbealinearlistofnelements.Weassumetheindependentreferencemodel,withafixedb

2、utunknownaccessprobabilityvector.Wesurveybrieflytheproblemofreorganizingthelistdynamically,onthebasisofaccruedreferences,withtheobjectiveofminimizingtheexpectedaccess-cost.TheCounterScheme(CS)isknowntobeasymptoticallyoptimalforthispurpose.ThepaperexplorestheCS,withtheaimofreducingitsstoragereq

3、uirements.Westartwithadetailedexpositionofitscostfunctionandthenpointoutthatitinteractswiththeaccessmodeltoproducesomeremarkablesynergisticeffects.Thesemakeitpossibletouseveryeffective`truncatedversions'oftheCS,whichhaveverymodestspacerequirements.Theversionsweconsiderare:(i)The`Limited-Count

4、ersScheme',whichboundseachofthefrequencycounterstoamaximalvaluec.(ii)TheoriginalCSwithaboundonthenumberofreferencesduringwhichtheschemeisactive.Theboundischosentoachieveadesiredaccesscost,comparedwiththeoptimalpolicy.1.IntroductionAlinearlistisadatastructureinwhichthereislittlestructure.Thusi

5、tissimpletobuildandmaintain,withtheconsequentpenaltythatitisrelativelyinefficientinuse.Nevertheless,underquitecommoncircumstancesitisthestructureofchoice.Weassumethefollowinglayout:AlistLcontainsnrecords{Ri,1£i£n},thatareidentifieduniquelybytheirkeys{Ki}.Thecontentofthelistisassumedtoremainunch

6、angedovertime.Theliststructureimpliesasequentialsearchaccessscheme:inordertoaccessRi,thekeysinpositions1,2,...arecomparedsuccessivelyagainstKiuntilanequalityisobtained.Thenumberofcomparisonsisdefinedasthecostoftheaccess,anddenotedbyCC.Thefollowingreferencemodelisassumed:eachrequestmayaddressth

7、erecordRifor1£i£n,withatime-homogeneousprobabilitypi>0.Thisholdstrueindependentlyofthelistorderandthehistoryofpastaccesses.Suchaschemeisknownasthe(stationary)independent-referencemodel(irm).Anaturalobjectiveistohavethesmallestpossiblecostpera