Advanceret Algoritmik
Ugeseddel 10

Emne: Den tredie og sidste forelæsning (3. april) om External Memory Algoirthms vil omhandle beregningen af minimum udspændende træer for store grafer. Forelæsningen tager udgangspunkt i nedenstående to artikler. Fra Abello et al. vil blive gennemået de dele der vedrører minimum udspændende træer i afsnitene 1-4 og 6, og fra Arge et al. vil blive gennemgået afsnitene 1 og 2.

A Functional Approach to External Graph Algorithms.
James Abello, Adam L. Buchsbaum, Jeffery R.Westbrook.
Proc. 6th Annual European Symposium on Algorithms, LNCS 1461, 332-343, 1998.
(online udgave: http://www.research.att.com/~alb/biblio/func-esa98.ps.Z).

On External Memory MST, SSSP and Multi-way Planar Graph Separation.
Lars Arge, Gerth Stølting Brodal, Laura Toma.
Proc. 7th Scandinavian Workshop on Algorithm Theory, LNCS 1851, 433-447, 2000. (online udgave: swat20mst.pdf).

Slides fra forelæsningen i uge 9 [ps,pdf]

Opgaver

Opgave 3 forneden er afleveringsopgave, dvs. den skal afleveres 17/4.

Opgave 1

I denne opgave antager vi at vi i ekstern hukommelse har givet et statisk B-træ af højde h, hvor alle blade gemmer B elementer og alle interne knuder har B børn. Vi antager desuden at M>=h*B og at vi i intern hukommelse altid husker de M/B sidste tilgange blokke i ekstern hukommelse.
En øvre grænse for antallet af I/Oer for en enkelt forespørgsel er O(log_BN) I/Oer. For en sekvens af k forespørgsler giver dette en øvre grænse på O(k*log_BN) I/Oer. Dette er dog en pessimistisk øvre grænse, da effekten af at huske tidligere læste blokke ignoreres. I det følgende søges bedre øvre grænser for nogle specifikke tilgangsmønste.

a)

Antag at der søges efter k elementer i sorteret rækkefølge og at disse udgør en sammenhængde delfølge af elementerne gemt i bladene af B-træet. Vis at der bruges O(log_BN+k/B) I/Oer for at finde de k elementer.

b)

Antag nu at der søges efter k elementer i sorteret rækkefølge, men hvor de k elementer er uniformt fordelte blandt elementerne i B-træet, fx at det i'te element der søges efter er det i*N/k'et element i B-træet. Vis at der bruges O(M/B+k(log_BN-log_BM)) I/Oer når der søges efter elementerne i sorteret rækkefølge.

c)

Som b), men hvor det skal vises at der bruges højest O(M/B+k(log_BN-log_B M)) I/Oer når man tilgår de k elementer i vilkårlig rækkefølge, dvs intuitivt huskes de log_BM øverste niveauer af B-træet i intern hukommelse.

Opgave 2

Givet et B-træ som gemmer N elementer med nøgler fra et totalt ordnet univers og et forespørgsels interval [x,y], så vil vi i denne opgave finde alle de elementerne i T som har en nøgle som er indeholdt i intervalet [x,y].

a)

Beskriv hvordan interval forespørgsler kan udføres med O(log_BN+k/B) I/Oer, hvor k er antallet af elementer der skal rapporterets.

b)

Beskriv hvordan en sorteret liste af k elementer kan flettes ind i et B-træ med O(log_BN+(k+D)/B) I/Oer, hvor D er antallet af elementer i B-træet med nøgler i intervalet givet ved det første og det sidste element der skal indsættes. Kan du give en bedre øvre grænse som funktion af N, k, B, og D?

Opgave 3

En klassisk implementation af prioritetskøer understøttende insert og deletemin i intern hukommelse er en binær bunke (``Heap sort'', Cormen et al., Kapitel 7). I ekstern hukommelse er binære bunker dog ikke særligt effektive, specielt kræver en deletemin typisk et konstant antal I/Oer. I denne opgave studeres mulige forbedringer af binære bunker således at de bliver I/O effektive.

Vi definerer en ekstern binær bunke til at være et perfekt binært træ (ligesom i en traditionel bunke) hvor hver knude istedet for kun ét element nu gemmer B elementer. Invarianten er nu at alle elementer i en knude skal have nøgler der er større end eller lig med nøglerne af alle elementerne i fader knuden.

a)

Vis at en ekstern binær bunke har højde log₂(N/B), hvor N er antallet af elementer i prioritetskøen.

b)

Vis hvordan man kan indsætte B nye elementer i en ekstern binær bunke med O(log₂(N/B)) I/Oer, ved først at indsætte de B nye elementer i det næste ``frie'' blad, og derefter at bobble disse elementer op indtil invarianten igen er opfyldt.

c)

Vis tilsvarende hvordan man kan slette de B mindste elementer fra en ekstern binær bunke, dvs de B elementer der er gemt i roden. Ligesom i en (intern) binær bunke kan man flytte indholdet af det ``sidste'' blad op til roden, og derefter ``bobble'' store elementer ned.

d)

Vis vha ``indsættelse'' og ``fjernelse'' buffere i intern hukommelse hvordan eksterne binære bunker understøtter insert og deletemin med amortiseret O((1/B)*log₂(N/B)) I/Oer (hvilket er optimalt for M=O(B)).

Datastruktureren betragtet i denne opgave er beskrevet i artikelen.

L. M. Wegner and J. I. Teuhola. The external heapsort.
IEEE Transactions on Software Engineering, volume 15, 917-925,1989.