资源描述：
《a forest-structured bloom filter with flash》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、AForest-structuredBloomFilterwithFlashMemoryGuanlinLuz,BiplobDebnathy;1,DavidH.C.DuzzUniversityofMinnesota,Minneapolis,USA.yEMCCorporation,SantaClara,USA.E-mail:lv@cs.umn.edu,biplob.debnath@emc.com,du@cs.umn.eduAbstract—ABloomFilter(BF)isadatastructurebasedonindexisusedto
2、determinewhetherachunkalreadyexistsandprobabilitytocompactlyrepresent/recordasetofelements(keys).toretrieveadatachunkfromdisk.However,inmanypracticalIthaswideapplicationsonefficientlyidentifyingakeythatcases(e.g.,hundredsTBofdatatobede-duplicated),thehasbeenseenbeforewithm
3、inimumamountofrecordingspacechunkindexsizeistoobigtofitinRAManddisk-basedindexused.BFisheavilyusedinchunkingbaseddatade-duplication.Traditionally,aBFisimplementedasin-RAMdatastructure;istooslow.Toreducethefrequencyofdiskaccesses,Zhuetal.henceitssizeislimitedbytheavailableR
4、AMspaceonthe[15]adoptsanin-RAMBloomFiltertoidentifynewchunks.machine.Forcertainapplicationslikedatade-duplicationthatIfachunkisidentifiedbyBFasnew,itistemporarilystoredrequireabigBFbeyondthesizeofavailableRAMspace,itinanin-RAMcontainerwithoutqueryingdisk-basedchunkbecomesn
5、ecessarytostoreaBFintoasecondarystoragedevice.index.Whenin-RAMcontainerbecomesfull,itiswrittentoSinceBFoperationsareinherentlyrandominnature,magneticdiskprovidesworseperformancefortherandomreadandwritediskatonceandthedisk-basedchunkindexisupdated.Itoperations.Itwillnotbea
6、goodfitforstoringthelargeBF.Flashhasbeendemonstratedthatbydeployinganin-RAMBloommemorybasedSolidStateDrive(SSD)hasbeenconsideredasFilter,aconsiderableamountofdiskaccessesforchunkindexanemergingstoragedevicethathassuperiorperformanceandlookupcouldbeavoided.Ontheotherhand,th
7、isin-RAMBFcanpotentiallyreplacedisksasthepreferredsecondarystorageconsumesasignificantamountofRAMspace(e.g.1GBsizedevices.However,severalspecialcharacteristicsofflashmemorymakedesigningaflashmemorybasedBFverychallenging.InBFperbillionuniquechunks[15]).Furthermore,whenthethis
8、paper,ourgoalistodesignanefficientflashmemorybaseddatasetsizecouldnotbedeterminedinadvance,BFsizem
