资源描述：
《k. external memory algorithms for string problems》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ExternalMemoryAlgorithmsforStringProblemsKanghoRoh1MaximeCrochemore2CostasS.Iliopoulos3KunsooPark1¤1SchoolofComputerScienceandEngineering,SeoulNationalUniversity2InstitutGaspard-Monge,Universit¶edeMarne-la-Vall¶ee3DepartmentofComputerSciences,King'sCollegeLondonAbstractInthispaperwepres
2、entexternalmemoryalgorithmsforsomestringproblems.Ex-ternalmemoryalgorithmshavebeendevelopedinmanyresearchareas,asthespeedgapbetweenfastinternalmemoryandslowexternalmemorycontinuestogrow.Thegoalofexternalmemoryalgorithmsistominimizethenumberofinput/outputoperationsbetweeninternalmemoryan
3、dexternalmemory.TheseyearsthesizesofstringssuchasDNAsequencesarerapidlyincreasing.However,externalmemoryalgorithmshavebeendevelopedforonlyafewstringproblems.Inthispaperweconsider¯vestringproblemsandpresentexternalmemoryalgorithmsforthem.Theyaretheproblemsof¯ndingthemaximumsu±x,stringmat
4、ching,period¯nding,Lyndondecomposition,and¯ndingtheminimumofacircularstring.EveryalgorithmthatwepresenthererunsinalinearnumberofI/Osintheexternalmemorymodelwithonedisk,andtheyruninanoptimalnumberofdiskI/Osintheexternalmemorymodelwithmultipledisks.1IntroductionDatasetsinmanyapplicationsa
5、reoftentoobigto¯tintomainmemory.Insuchapplicationsitisimportantthatalgorithmstakeintoaccountthememoryconstraintsofthesystem[30,35].Inmostmodernsystemsthememoryisorganizedintoahierarchy.Atthetoplevel,fastinternalmemorywhichisexpensiveandhaslowstoragecapacityislocated.Atthebottomlevel,slo
6、werexternalmemorywhichischeapandhashighstoragecapacityislocated.Thereforetheinput/outputcommunication(orsimplyI/O)betweentwolevelsinmemoryhierarchycanbeabottleneckinmassivedatasetapplications.OneapproachtooptimizingperformanceistodevelopalgorithmsthatminimizeI/Osbetweeninternalmemoryand
7、externalmemory.ThesealgorithmsarereferredtoasexternalmemoryalgorithmsormoresimplyEMalgorithms.Earlyworkinexternalmemoryalgorithmsfocusedonfundamentalproblemssuchassort-ing,matrixmultiplication,andFFT[1,29,36,3].Morerecently,researchonEMalgorithmshasmovedtowardssolvinggraphandge
