Space Efficient Data Structures and External Terrain Algorithms

Research output: Book/anthology/dissertation/reportPh.D. thesisResearch

Documents

  • Jakob Truelsen, Denmark
Denne afhandling omhandler h ̊ andtering af store datamængder, og best ̊ ar af to dele. Den første del handler om pladseffektive datastrukturer. Her ser vi første p ̊ a det (1 + ε)-approks- imative intervaltypetalsproblem. I dette problem er vi givet et array A, og skal konstruere en datastruktur, som understøtter approksimative intervaltypetalsforespørgsler. En s ̊ adan forespørgsel best ̊ ar af indekser i og j, og skal returnere et element e fra A[i, j], som har en hyppighed, der er højest en faktor (1 + ε) fra det mest hyppige element. Vi præsen- terer en (1 + ε)-approksimativ intervaltypetalsdatastruktur der bruger O( nε ) plads, og som understøtter forespørgsler i O(log 1 ε ) tid. Derefter ser vi p ̊ a implisite datastruktuere. En implicit datastruktur best ̊ ar af udelelige elementer, som er gemt i et array, hvor alt yderligere information skal kodes i rækkefølgen af elementerne. Vi studere to forskellige modeller: I den svage implicite model er det tilladt at vi gemmer O(1) ord af information mellem operationer, hvorimod man i den stærke implicite model kun m ̊ a gemme størrelsen af arrayet n. I den stærke implicite model konstruerer vi en ordbog med arbejdssæts egenskaben, som understøtter insert(e) og delete(e) i O(log n) tid, og find(e) i O(log ) tid, hvor antallet af unikke elementer, der er søgt efter siden e sidst blev søgt efter. Vi konstruerer en statisk ordbog med fingersøgnings egenskaben. Denne struktur understytter find(e), predecessor(e) og successor(e) i tid O(log d(e, f )) og change-finger(e) i tid O(n ε ) for et vilk ̊ arligt ε > 0. Her flytter change-finger(e) den nuværende finger f til elementet e, og d(e, f ) er rangafstanden mellem den nuværende finger f og e. Vi viser at denne struktur under visse betingelser er optimal i den stærke implicitte model, mens eksponentiel søgning i et sorteret array i den svage model vil have den samme udførselstid, undtagen for change-finger(e) som kun vil tage O(log n) tid. I den stærke implicitte model konstruerer vi ogs ̊ a en dynamisk fingersøgnings ordbog, der opn ̊ ar de samme udførselstider som den statiske struktur. I den anden del af denne afhandling ser vi p ̊ a I/O algoritmer, her opgiver vi at f ̊ a alt data til a være in rammen, og prøver istedet at begrænse antallet tilgange til disken. Specifikt ser vi p ̊ a praktisk effektive terrænalgoritmer. Først √ √ konstruerer vi en algoritme, som givet √ en raster af størrelse N × N , konstruerer alle N nedskaleringer i O(scan(N )) I/Oer i den cache uvidende model. Denne algoritme vises at være effektiv i praksis. Derefter konstruerer vi en algoritme, der kan simplificere planare opdelinger, som f.eks. kurvekort eller vandoplandskort. En s ̊ adan planar opdeling danner en planar graf med knuder og linjesegmenter mellem knuderne. Denne graf deler fladerne i opdelingen. Simpli- fikationen best ̊ ar i at fjerne knuder med grad to, hvor flere vigtige egenskaber overholdes. Input og output opdelingerne vil være homotopiske og ethvert segment i inputtet har højst afstand ε xy til det segment, der erstatter det i outputtet. For det specielle tilfælde af kurvekort giver vi ogs ̊ a en tilsvarende garanti for z-aksen. Algoritmen udfører O(sort(N )) I/Oer under visse realistiske antagelser, og vi viser at den er effektiv i praksis.
Original languageEnglish
PublisherDepartment of Computer Science, Aarhus University
Number of pages109
Publication statusPublished - 2015

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 84702309