资源描述：
《Uniquely Represented Data Structures for》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、UniquelyRepresentedDataStructuresforComputationalGeometryGuyE.Blelloch1DanielGolovin2VirginiaVassilevska3April2008CMU-CS-08-115SchoolofComputerScienceCarnegieMellonUniversityPittsburgh,PA15213AbstractWepresentnewtechniquesfortheconstructionofuniquelyrepresenteddatastructuresin
2、aRAM,andusethemtoconstructefficientuniquelyrepresenteddatastructuresfororthogonalrangequeries,lineintersectiontests,pointlocation,and2-Ddynamicconvexhull.Uniquelyrepresenteddatastructuresrepresenteachlogicalstatewithauniquemachinestate.Suchdatastructuresarestronglyhistory-indep
3、endent.Thiseliminatesthepossibilityofprivacyviolationscausedbytheleakageofinformationaboutthehistoricaluseofthedatastructure.Uniquelyrepresenteddatastructuresmayalsosimplifythedebuggingofcomplexparallelcomputations,byensuringthattworunsofaprogramthatreachthesamelogicalstaterea
4、chthesamephysicalstate,evenifvariousparallelprocessesexecutedindifferentordersduringthetworuns.1SupportedinpartbyNSFITRgrantCCR-0122581(TheAladdinCenter).2SupportedinpartbyNSFITRgrantsCCR-0122581(TheAladdinCenter)andIIS-0121678.3SupportedinpartbyNSFITRgrantCCR-0122581(TheAladd
5、inCenter)andaComputerScienceDepartmentPh.D.Scholarship.Keywords:UniqueRepresentation,CanonicalForms,HistoryIndependence,ObliviousDataStructures,OrderedSubsets,RangeTrees,PointLocation,ConvexHull1IntroductionMostcomputerapplicationsstoreasignificantamountofinformationthatishidde
6、nfromtheap-plicationinterface—sometimesintentionallybutmoreoftennot.Thisinformationmightconsistofdataleftbehindinmemoryordisk,butcanalsoconsistofmuchmoresubtlevariationsinthestateofastructureduetopreviousactionsortheorderingoftheactions.Forexampleasimpleandstandardmemoryalloca
7、tionschemethatallocatesblockssequentiallywouldrevealtheorderinwhichobjectswereallocated,oragapinthesequencecouldrevealthatsomethingwasdeletedeveniftheactualdataiscleared.Suchlocationinformationcouldnotonlybederivedbylookingatthememory,butcouldevenbeinferredbytimingtheinterface
8、—memoryblocksinthesamecacheline(ordiskpage)haveverydifferentp
