Dynamic Data Structures: The Interplay of Invariants and Algorithm Design

Publikation: Bog/antologi/afhandling/rapportPh.d.-afhandling

I denne afhandling vil jeg behandle tre dynamiske datastruktursproblemer ved brug af invarianter. Første problem er at vedligeholde en dynamisk mængde af nøgler – kaldt en ordbog. Vi kan lave forespørgelserne: er en given nøgle indeholdt? og hvad er den foregående (eller efterfølgende) nøgle til denne nøgle? Vi kan foretage opdateringerne: indsæt en ny nøgle eller slet en given nøgle. Vores ordbog har arbejdsmængde egenskaben, hvilket betyder at udførselstiden for en forespørgsel afhænger af distributionen af alle forespørgslerne. Udførselstiden for en forespørgsel afhænger af hvornår vi sidst søgte efter den givne nøgle. Vores datastruktur er implicit hvilket betyder at vi ikke bruger yderligere plads end det som inputtet bruger. Vores datastruktur er indkodet implicit i permutationen af inputtet. Andre ordbøger med arbejdsmængde egenskaben bruger en konstant faktor mere plads, vores ordbog bruger ingen ekstra plads og har således det optimale pladsforbrug, men opnår stadig arbejdsmængde egenskaben. Vores resultat er tilmed cache-oblivious og er derfor også effektivt i ekstern hukommelse.

Andet problem er at vedligeholde en first-in-first-out kø over elementer med prioriteter – kaldet en prioritetskø med afskæring. Vi sletter elementer i fronten og indsætter elementer i enden. Når vi indsætter et element så slettes – afskæres – alle elementer med en nøgle som er større eller lig med den indsatte. Vi udvider en tidligere løsning af Sundar med en sammenkædningsoperationen. Når vi sammenkæder to køer så slettes alle elementer i den første kø, der er større eller lig det mindste element i den anden kø, og den anden kø sammenkædes med den første kø. Vores resultat er effektivt i ekstern hukommelse.

Tredje problem er at vedligeholde en to-dimensionel dynamisk punktmængde, hvor forespørgelserne er at rapportere alle punkter som ikke har nogen punkter over eller til højre for sig, inde i et rektangulært område. Disse punkter kaldes udominerede punkter og udgøre skylinen i det rektangulære område. Vores resultater er de første dynamiske resultater som er effektive i ekstern hukommelse. I gennem hele afhandlingen bruger vi invarianter til at løse datastruktursproblemer. I designet af dynamiske datastrukturer har vi en mængde af forespørgsler og opdateringer som vi ønsker at vores datastruktur skal understøtte, men vi vælger ikke selv rækkefølgen som de udføres i. Invarianter er logiske udsagn om vores datastrukturer som er baserede på strukturen af det problem vi prøver på at løse. Vi kan afhænge af udsagnene fra invarianterne i vores forespørgsler, men tilgengæld skal vi garantere at de forbliver sande når vi udfører opdateringer. Når vi designer datastrukturer er der et samspil mellem at foreslå nye invarianter og at tjekke at de effektivt kan vedligeholdes ved opdateringer og er tilstrækkelige til effektivt at besvare forespørgsler. Vi har løst vores datastruktursproblem når vi har fundet en mængde "gode" invarianter som balancere de to sider.
OriginalsprogEngelsk
ForlagDepartment of Computer Science, Aarhus University
Antal sider94
StatusUdgivet - 2013

Note vedr. afhandling

Supervisor: Gerth Stølting Brodal

Se relationer på Aarhus Universitet Citationsformater

ID: 56197304