Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | yvo-leidner |
View: | 106 times |
Download: | 0 times |
1
Vorlesung Informatik 2
Algorithmen und Datenstrukturen
(23 –Persistente und vergessliche Datenstrukturen)
Prof. Th. Ottmann
2
Übersicht
• Motivation: Vergessliche und persistente Strukturen
• Beispiele: Arrays, Suchbäume, Z-stratifizierte Suchbäume, Relaxierung
• Methoden zur Persistenzsicherung: Struktur-Kopier-, Pfad-Kopier-, DSST-Methode
• Anwendung: Punktlokalisation
• Vergessliche Strukturen: Randomisierte und eindeutige Strukturen, insbesondere
Sprung-Listen
• Praktisches Beispiel zeitabhängiger Datenströme: Aufzeichnung und Wiedergabe
von Whiteboard Daten, insbesondere Handschrift
3
Motivation
Eine Struktur zur Speicherung einer Menge von Schlüsseln heißt vergesslich, wenn
aus der Gestalt der Struktur nicht auf die Erzeugungshistorie geschlossen werden
kann.
Eine Struktur heißt persistent, wenn neben der aktuellen auch frühere Versionen
existieren.
Partiell persistent: Modifikationen nur bei aktueller, Zugriff (Suche) auch bei früheren
Versionen möglich.
Voll persistent: Zugriff und Modifikation für alle Versionen
Konfluent persistent: Mehrere frühere Versionen können zu neuer aktueller Version
verknüpft werden.
4
Beispiel: Arrays
Array:
2 4 8 15 17 43 47 ……
Eindeutige Struktur, daher vergesslich!
Suchen: In Zeit O( log n) möglich, binäres Suchen
Update (Einfügen, Entfernen): (n)
Aber Vorsicht:Speicherbelegung könnte dennoch von Erzeugungshistorie abhängen!
5
Beispiel: Natürliche Suchbäume
Nur teilweise vergesslich!
• Einfügereihenfolge teilweise rekonstruierbar.
• Entfernte Schlüssel nicht sichtbar.
Suchen, Einfügen. Entfernen von Schlüsseln: (n) Zeit
1, 3, 5, 7 5, 1, 3, 7
13
57 3
1
5
7
6
Beispiel: Balancierte Suchbäume
Problem:(Zu) viele Updates auf einmal (Z.B. bei der Aufzeichnung von Handschrift)Nicht genügend Zeit zur sequentiellen BearbeitungLösung:Relaxiert balancierte Suchbäume: Update und Rebalancierungs-Operationen werden nebenläufig ausgeführt!
10
6 15
2 9 11 23
5 7 20 30
6 7 9
10 11 15
5
2
20 23
7
Stratifizierte Suchbäume
....
…..
… …
… …
8
Beispiel
9
Beispiel
10
Einfügen
Füge neuen Schlüssel ganz unten ein und deponiere einen „push-up-request“
… …
… … ....
…..
…..
x p
11
Iterierte Folge von Einfügungen
12
Beseitigung eines Push-up-requests (1)
• Push-up-request führt entweder zu einer lokalen strukturellen Änderung mit
konstantem Aufwand (Fall 1)
• oder zu einer Verschiebung des Push-up-requests auf das nächst höhere Niveau
ohne Strukturänderung (Fall2)
Fall1 [Genug Platz auf nächster Schicht]
1 2 31 2
3
1 2
3 4 1 2 3 4
1
2 3
4 2 31 4
13
Beseitigung eines Push-up-requests (2)
• Fall2 [Nächste Schicht voll]
Schaffe ggfs. neue Schicht an der Spitze
1
2 3
4 5 1
2 3
4 5
14
Entfernen
Deponiere für jede Entfernung einen Lösch-Vermerk.Beseitige Lösch-Vermerke.
… …
… … ....
…..
… …
15
Beseitigung eines Löschvermerks
Fall 1 [genügend Knoten auf unterster Schicht]
Fall 2 [unterste Schicht zu dünn]
Deponiere „pull-down-request“ p q q
16
Beseitigung von Pull-down-requests (1)
1p 2 3 1p 2 3
1p 2 3 4 p 1 2 3 41 p2 3 4
1 2 3 4p
Fall1 [genügend Knoten auf nächster Schicht]
Endliche Strukturänderung undHalt!
17
Beseitigung von Pull-down-requests (2)
p
p
Fall2 [nicht genügend Knoten auf nächster Schicht]
Verschiebe Pull-down-request auf nächst höhere Schicht,ohne strukturelle Änderungen
18
Z-stratifizierte Bäume: Beobachtungen
Einfüge-, Entferne- und Rebalancierungs-Operationen (Beseitigung von , ) lassen
sich beliebig verzahnen.
Die amortisierten Umstrukturierungskosten pro Einfügung und Entfernung sind
konstant.
Erzeugungshistorie ist aus aktueller Version teilweise erkennbar (Einfügereihenfolge
und entfernte Schlüssel sind teilweise sichtbar)
Aber:
• Update Operationen beziehen sich stets nur auf aktuelle Version
• Z-stratifizierte Bäume sind nicht persistent
19
Übersicht
• Motivation: Vergessliche und persistente Strukturen
• Beispiele: Arrays, Suchbäume, Z-stratifizierte Suchbäume
• Methoden zur Persistenzsicherung: Struktur-Kopier-, Pfad-Kopier-, DSST-Methode
• Anwendung: Punktlokalisitation
• Vergessliche Strukturen: Randomisierte und eindeutige Strukturen, insbesondere
Sprung-Listen
• Praktisches Beispiel zeitabhängiger Datenströme: Aufzeichnung und Wiedergabe
von Whiteboard Daten, insbesondere Handschrift
20
Einfache Strategien zur Persistenz-Erhaltung
• Kopiere gesamte Struktur vor jeder Update-Operation, liefert volle Persistenz zum
Preis von (n) Zeit pro Update und Platz (m n) für m Updates auf Strukturen der
Größe n. (Struktur-Kopier-Methode)
• Tue nichts sondern speichere ein log-File der Updates! Um auf Version i
zuzugreifen, führe zunächst die i ersten Updates auf der Anfangsstruktur aus, um
Version i zu erzeugen. (i) Zeit per Zugriff, O(m) Platz für m Operationen.
• Hybrid-Ansatz: Speichere die gesamte Folge der Updates und zusätzlich jede k-te
Version für ein geeignetes k. Folge: Zeit oder Platzbedarf nimmt mindestens um
Faktor sqr(m) zu!
Gibt es bessere Methoden? …. Für Suchbäume ….
21
Persistente Suchbäume (1)
Pfadkopiermethode
5
1 7
3
0
Version 0:
22
Persistente Suchbäume (1)
Pfad-Kopier-Methode
5 5
1 1 7
3 3
2
0 1
Version 1:Einfüge (2)
23
Persistente Suchbäume (1)
Pfad-Kopier-Methode
5 5 5
1 1 1 7
3 3 3
2 4
0 1 2
Version 1:Einfüge (2)Version 2:Einfüge (4)
24
Persistente Suchbäume (1)
Pfad-Kopier-Methode
Umstrukturierungs-Kosten O(log n) pro Update Operation
5 5 5
1 1 1 7
3 3 3
2 4
0 1 2
Version 1:Einfüge (2)Version 2:Einfüge (4)
25
Persistente Suchbäume (2)
DSST-Methode: Erweitere jeden Knoten um Modifikationsfeld mit Zeitstempel
? alle Versionenvor Zeit t
alle Versionenab Zeit t
Modifikationsfelder•sind anfangs leer•werden v.u.n.o. gefüllt
k
t: rplp rp
26
DSST Methode
5
1
3
7
Version 0
27
DSST Methode
5
1
3
2
7
1 lp
Version 0:
28
DSST Methode
5
1
3
2
3
4
7
1 lp
Version 1:Einfüge (2)Version 2:Einfüge (4)
29
DSST Methode
Die amortisierten Kosten (Zeit und Platz) pro Update Operation sind O(1)
5
1
3
2
3
4
72 rp
1 lp
Version 1:Einfüge (2)Version 2:Einfüge (4)
30
Übersicht
• Motivation: Vergessliche und persistente Strukturen
• Beispiele: Arrays, Suchbäume, Z-stratifizierte Suchbäume, Relaxierung
• Methoden zur Persistenzsicherung: Struktur-Kopier-, Pfad-Kopier-, DSST-Methode
• Anwendung: Punktlokalisation
• Vergessliche Strukturen: Randomisierte und eindeutige Strukturen, insbesondere
Sprung-Listen
• Praktisches Beispiel zeitabhängiger Datenströme: Aufzeichnung und Wiedergabe
von Whiteboard Daten, insbesondere Handschrift
31
Anwendung: Planare Punktlokalisation
Suppose that the Euclidian plane is subdivided into polygons by n line segments that intersect only at their endpoints.
Given such polygonal subdivision and an on-line sequence of query points in the plane, the planar point location problem, is to determine for each query point the polygon containing it.
Measure an algorithm by three parameters:
1) The preprocessing time.
2) The space required for the data structure.
3) The time per query.
32
Planar point location -- example
33
Planar point location -- example
34
Solving planar point location (Cont.)
Partition the plane into vertical slabs by drawing a vertical line through each endpoint.
Within each slab the lines are totally ordered.
Allocate a search tree per slab containing the lines at the leaves with each line associate the polygon above it.
Allocate another search tree on the x-coordinates of the vertical lines
35
Solving planar point location (Cont.)
To answer query
first find the appropriate slab
Then search the slab to find the polygon
36
Planar point location -- example
37
Planar point location -- analysis
Query time is O(log n)
How about the space ?
(n2)
And so could be the preprocessing time
38
Planar point location -- bad example
Total # lines O(n), and number of lines in each slab is O(n).
39
Planar point location & persistence
So how do we improve the space bound ?
Key observation: The lists of the lines in adjacent slabs are very similar.
Create the search tree for the first slab.
Then obtain the next one by deleting the lines that end at the corresponding vertex and adding the lines that start at that vertex
How many insertions/deletions are there alltogether ?
2n
40
Planar point location & persistence (cont)
Updates should be persistent since we need all search trees at the end.
Partial persistence is enough
Well, we already have the path copying method, lets use it.What do we get ?
O(nlogn) space and O(nlog n) preprocessing time.
We shall improve the space bound to O(n).
41
Übersicht
• Motivation: Vergessliche und persistente Strukturen
• Beispiele: Arrays, Suchbäume, Z-stratifizierte Suchbäume
• Methoden zur Persistenzsicherung: Struktur-Kopier-, Pfad-Kopier-, DSST-Methode
• Anwendung: Punktlokalisation
• Vergessliche Strukturen: Randomisierte und eindeutige Strukturen, insbesondere
Sprung-Listen
• Praktisches Beispiel zeitabhängiger Datenströme: Aufzeichnung und Wiedergabe
von Whiteboard Daten, insbesondere Handschrift
42
Strategien für vergessliche Strukturen
Mache die Struktur eindeutig:
• Mengeneindeutigkeit: Für jede Menge von n Schlüsseln gibt es genau eine
Struktur, die sie speichert.
• Die Speicherung ist ordnungseindeutig, d.h. die Knoten der Struktur sind
angeordnet und die Schlüssel sind der Größe nach in den Knoten mit
aufsteigenden Nummern gespeichert.
Randomisiere die Struktur:
• Sichere, dass der Erwartungswert für das Auftreten einer Struktur, die eine Menge
M von Schlüsseln speichert, unabhängig davon ist, wie M entstanden ist.
Beobachtung: Die Zuweisung von Speicheradressen zu Zeigern muss randomisiert
erfolgen!
43
Beispiel für eine randomisierte Struktur
Z-stratifizierter Suchbaum
Wähle auf jeder Schicht eineZufällige Verteilung der Bäume aus Z
Einfügen ?Entfernen ?
… …
… … ....
…..
…..
44
Mengen- und ordnungseindeutige Strukturen
Untere Schranken?
Annahmen: Wörterbuch der Größe n wird repräsentiert durch Graph mit n Knoten
Knotengrad endlich (fest),
feste Ordnung der Knoten,
i-ter Knoten speichert i-ten Schlüssel.
Operationen zur Veränderung von Graphen:
Schaffen | Entfernen von Knoten
Pointer change
Austausch von Schlüsseln
Satz: Für jede mengen- und ordnungs-eindeutige Repräsentation von Wörterbüchern gilt, daß wenigstens eine der drei Operationen Suchen, Einfügen und Entfernen Zeit (n1/3) kostet.
45
Sprung-Listen
(Halbdynamische) 2-Ebenen Sprung-Listen
2-Ebenen-Sprung-Liste der Größe n
niini 22 )1(
Suchen: O(i) = O( ) ZeitEinfügen: Entfernen: O( )
Zeit
n
n
22 4113
tail
0 i 2i n
(n-1)/i · i
2 3 5 7 8 10 11 12 14 17 19
46
3-Ebenen Sprung-Listen
33 )1( ini
33 43,30 nnin 3
level 2
Suche(x): bestimme x durch Nachlaufen der level-2-Zeiger unter i2 Schlüsseln, die x enthalten können,level-1-Zeiger unter i Schlüsseln, die x enthalten können,level-0-Zeiger unter i Schlüsseln
Suchzeit: O(i) = O(n1/3)
0 i 2i i2 i2+i 2·i2
47
3-Ebenen Sprung-Listen
33 )1( ini
33 43,30 nnin 3
level 2
Update erfordertÄnderung von 2 Zeigern auf level 0Änderung von i Zeigern auf level 1Änderung aller i Zeiger auf level 2
Update Zeit: O(i) = O(n1/3)
0 i 2i i2 i2+i 2·i2
48
c-Ebenen Sprung-Liste
Sei
Lower levels:
level 0: alle Zeiger mit Länge 1:
...
level j: alle Zeiger mit Länge ij-1:
...
level c/2 : ...
Upper levels:
level j: verbinde in einer Liste die Knoten
1, 1·ij-1+1, 2· ij-1+1, 3· ij-1+1, ...
level c:
cc ini )1(
49
Satz:
Für jedes sind c-Ebenen Sprung-Listen eine größen- und ordnungseindeutige
Repräsentation von Wörterbüchern mit folgenden Eigenschaften:
Platzbedarf O(c·n)
Suchzeit O(c·n1/c)
Updatezeit , falls n gerade
, falls n ungerade
)( nO
)( 2/)1( ccnO
3c
c-Ebenen Sprung-Liste
50
Übersicht
• Motivation: Vergessliche und persistente Strukturen
• Beispiele: Arrays, Suchbäume, Z-stratifizierte Suchbäume
• Methoden zur Persistenzsicherung: Struktur-Kopier-, Pfad-Kopier-, DSST-Methode
• Vergessliche Strukturen: Randomisierte und eindeutige Strukturen, insbesondere
Sprung-Listen
• Praktisches Beispiel zeitabhängiger Datenströme: Aufzeichnung und Wiedergabe
von Whiteboard Daten, insbesondere Handschrift
51
Author Audience
Data sources
Lightweight
content creation
Recorded learning module Document
Input media• Whiteboard• TouchScreen• Tablet PC
Zeitabhängige Daten beim Presentation Recording
52
Aufzeichnungs Technologie
• Low End: Digitale Tafelbilder und Audio/Video-
Aufzeichnung einer Tafel- und Kreide Vorlesung.
(Real audio/video + hi-res. digital images)
• High End: Direkte Aufzeichnung einer
Computerpräsentation (mit Whiteboard und Daten
Projektor für die Zuhörer, Stifteingabe, Tablet PC,
Wacom Tablet ...)
Software: RealPresenter, Camtasia, ..., AOF)
53
Dozent im Hörsaal
54
Integrierte Hardware Lösung
55
Cintiq Tablet (Wacom)
• Stifteingabe, großes Display
• Augenkontakt mit Zuhörern
56
Datenströme
57
Random Acess Fähigkeit
Zugriff auf ink-Object sj zum Zeitpunkt tj erfordert die sofortige Darstellung
von sj sowie aller ink-Objekte seit t0
58
Whiteboard Daten
Whiteboard Datenstrom erfordert
• Schnelles Einfügen, Entfernen graphischer Objekte (Linien, Kreise, pen-traces, …)
in sehr großer Zahl,
• Partiell persistente Speicherung mit,
• Zugriff (Ausgabe und „Rendering“) aller Daten zu gegebenem Zeitpunkt,
• Synchronisierbarkeit (als slave) mit Audiostrom (master).
Problem: Finde eine geeignete Speicherungsform für Whiteboarddatenstrom!
59
Postprocessing
Whiteboard-Strom wird nach der Struktur-Kopier-Methode persistent gemacht:
Für jeden Zeitpunkt t wird die Liste aller zu diesem Zeitpunkt sichtbaren Objekte
berechnet und für direkten Zugriff gespeichert
Nachteil: Hohes Datenvolumen
Vorteil: Visible Scrolling
Speicherung und Darstellung von Handschrift: Finde guten Kompromiss zwischen:
Datenvolumen
Zugriffskosten (Zeit) und dynamischer Wiedergabe (visible scrolling)
Natürlichkeit (persönliche Note)
Skalierbarkeit (Vektor- vs. Rasterdarstellung)