Experiments on the Practical IO Efficiency of Geom

ExperimentsonthePracticalI/OEciencyofGeometricAlgorithms:DistributionSweepvs.PlaneSweepYi-JenChiangy(April1995;revisedJune1997)ToappearinComputationalGeometry:TheoryandApplicationsAbstractWepresentanextensiveexperimentalstudycomparingtheperformanceoffouralgorithmsforthefollowingorthogonalsegmentintersectionproblem:givenasetofhorizontalandverticallinesegmentsintheplane,reportallintersectinghorizontal-verticalpairs.TheproblemhasimportantapplicationsinVLSIlayoutandgraphics,whicharelarge-scaleinnature.Thealgo-rithmsunderevaluationareourimplementationsofdistributionsweepandthreevariationsofplanesweep.Distributionsweepisspecicallydesignedforthesituationsinwhichtheproblemistoolargetobesolvedininternalmemory,andtheoreticallyhasoptimalI/Ocost.Planesweepisawell-knownandpowerfultechniqueincomputationalgeometry,andisoptimalforthisparticularproblemintermsofinternalcomputation.Thethreevariationsofplanesweepdierbythesortingmethods(externalvs.internalsorting)usedinthepreprocessingphaseandthedynamicdatastructures(Btreevs.2-3-4tree)usedinthesweepingphase.Wegeneratethetestdatabythreeprogramsthatusearandomnumbergeneratorwhileproducingsomeinterestingpropertiesthatarepredictedbyourtheoreticalanalysis.Thesizesofthetestdatarangefrom250thousandsegmentsto2.5millionsegments.Theexperimentsprovidedetailedquantitativeevaluationoftheperformanceofthefouralgorithms,andtheobservedbehaviorofthealgorithmsisconsistentwiththeirtheoreticalproperties.Thisis,tothebestofourknowl-edge,therstexperimentalalgorithmicstudycomparingthepracticalperformancebetweenexternal-memoryalgorithmsandconventionalalgorithmswithlarge-scaletestdata.Keywords:Segmentintersection,planesweep,distributionsweep,B-tree,external-memoryalgorithm,implementation,experimentation,probabilisticanalysis.Anextendedabstractofthispaperwaspresentedatthe4thWorkshoponAlgorithmsandDataStructures,Kingston,Ontario,Canada,August,1995.yDepartmentofAppliedMathematicsandStatistics,SUNYStonyBrook,StonyBrook,NY11794-3600;[e-mail]theauthorwasattheComputerScienceDepartmentofBrownUniversity.ResearchsupportedinpartbytheNationalScienceFoundation,bytheU.S.ArmyResearchOce,andbytheOceofNavalResearchandtheAdvancedResearchProjectsAgency.1IntroductionInput/Output(I/O)communicationbetweenfastinternalmemoryandslowerexternalmemoryisthemajorbottleneckinmanylarge-scaleapplications.TheissueofthisI/Obottleneckisbecomingmoreandmoreimportant,sinceproblemsizesofapplicationsaregettinglargerandlarger,andtechnologicaladvancesareincreasingCPUspeedsatanannualrateof40{60%whiledisktransferratesareonlyincreasingby7{10%annually[32].Duetothisincreasingimportance,moreandmoreattentionhasbeengiventothedevelopmentofI/O-ecientalgorithmsinrecentyears.Mostofthedevelopedalgorithms,however,areshowntobeecientonlyintheory,andtheirperformanceinpracticeisyettobeevaluated.Inparticular,allsuchalgorithmsassumethattheinternalcomputationisfreecomparedtotheI/Ocost,whichalsohastobejustiedinpractice.Inthispaper,weestablishthepracticaleciencyofonesuchalgorithmbyanextensiveexperimentalstudy.PreviousRelatedWorkAsmentionedabove,mostofthepreviousworkonI/O-ecientcomputationistheoretical.Earlyworkonalgorithmsforparalleldisksystemsconcentrateslargelyonfundamentalproblemssuchassorting,matrixmultiplication,andFFT[1,28,38].Themainfocusofthisearlyworkisthereforedirectedatproblemsthatinvolvepermutationatabasiclevel.Indeed,justtheproblemofimplementingvariousclassesofpermutationhasbeenacentralthemeinexternal-memoryI/Oresearch[1,14,15,17,38].Also,ageneralconnectionbetweenthecomparison-complexityandtheI/O-complexityofagivenproblemisshownin[4].Morerecently,external-memoryresearchhasmovedtowardssolvinggraphandgeometricprob-lems.Workongraphproblemsincludestransitiveclosurecomputations[35],somegraphtraversalproblems[23],andmemorymanagementproblemsformaintainingconnectivityinformationandpathsongraphs[19].Recently,Chiangetal.[12]presentacollectionofnewtechniquesfordesign-ingandanalyzingI/O-ecientgraphalgorithms,andapplythesetechniquestoawidevarietyofspecicproblems.Concurrenttotheworkpresentedinthispaper,Arge[3]considerstheproblemofmanipulatingorderedbinary-decisiondiagramsinexternalmemory.Forgeometricproblems,Goodrichetal.[24]studyanumberofproblemsincomputationalgeometryanddevelopseveralparadigmsforI/O-optimalgeometriccomputations.Furtherresultsinthisareahavebeenobtainedin[20,39].Also,Kanellakisetal.[25]andRamaswamyandSubramanian[31,34]giveecientdatastructuresforperformingrangesearchinginexternalmemory.Concurrenttotheworkinthispaper,anewdatastructurecalledbuertreeanditsapplicationsaregivenin[2,5],andanexternal-memoryversionofthedirectedtopologytree([21])calledtopologyB-treeisgivenin[11].Forexcellentexamplesofexperimentalworkincomputationalgeometry,seeBentley[7,8,9,10].AsforexperimentalworkonI/O-ecientcomputation,concurrenttoourworkVengrobuildsanenvironmentcalledTPIEforprogrammingexternal-memoryalgorithmsasheproposedearlierin[36],andalsoVengroandVitter[37]reportsomebenchmarksofTPIEonsortingandmatrixmultiplication.Thisw