close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

1. Große Varianz unwahrscheinlich: Hatten: vk(h) := ∑ f2 . Frage

EinbettenHerunterladen
1. Große Varianz unwahrscheinlich:
2
j∈h−1 (z),j>k f j .
Hatten: v >k (h) :=
¨
Frage: Wie groß kann das fur
¨ zufalliges
h werden?
¨
Also h → H ∈ H zufallig.
¨
H aus 2-fach unabhangiger
Hashklasse ⇒
Wskt., dass einzelner Wert auf z abgebildet wird, ist 1/b.
m
E v >k (H) =
j=k+1
m
E([H(j) = z]) · f j2 =
f j2 /b
j=k+1
= F2>k /b.
Sei G ROSSE VARIANZ := [v >k (H) > 8F2>k /b].
Markoff-Ungleichung liefert:
Pr{GROSSE VARIANZ } ≤
1
.
8
444
¨
2. Hashen von großen Haufigkeitswerten
auf z = h(i)
unwahrscheinlich:
Sei KOLLISION := [H −1 (z) ∩ {1, . . . , k } = ∅].
¨ Voraussetzung folgt:
Mit b ≥ 8k gemaß
k
1
Pr{KOLLISION } ≤
≤ .
b
8
¨
3. Große Abweichungen des Schatzers
von f i
unwahrscheinlich:
Sei
GROSSE
A BWEICHUNG das Ereignis, dass
|YH(i) X i − f i |2 > 8V (YH(i) X i ).
Da E |YH(i) X i − f i |2 = V (YH(i) X i ), folgt wieder mit Markoff:
1
Pr{GROSSE A BWEICHUNG } ≤ .
8
445
Insgesamt gilt:
Pr{GROSSE VARIANZ ∨ KOLLISION
∨GROSSE A BWEICHUNG } ≤
3
.
8
Andererseits, falls keines der drei Ereignisse eintritt:
√
|YH(i) X i − f i | ≤ 8V (YH(i) X i ) ≤ 8 v >k (H)
√
≤ 8 8F2>k /b = 8 F2>k /b.
Fehlschlagswskt. 3/8 → Fehlschlagswskt. δ wie immer
mit (Median-)Probability-Amplification, (log(1/δ)) Kopien.
446
4.7.2 Sketching-Algorithmus fur
¨
Top-k -(ε, δ)-Approximation
Algorithmus TOP -k -C OUNT S KETCH (grob):
• Schatzung
¨
¨
absoluter Haufigkeiten
mit C OUNT S KETCH.
• Suchbaum mit k Werten, die bisher großte
¨
¨
Schatzwerte
¨
hatten, zusammen mit exakten absoluten Haufigkeiten.
Parameterwahlen fur
¨ C OUNT S KETCH:
• Fehlschlagswskt. δ ′ := δ/n. Dann Wskt. mindestens 1 − δ,
dass zu jedem Updatezeitpunkt Abweichung der
¨
¨
geschatzten
absoluten Haufigkeit
von exakter
¨
hochstens
8γ .
• Bucketanzahl b so, dass 8γ ≤ (ε/2)fk .
!
8γ = 8 F2>k /b ≤ (ε/2)fk
fk =0
⇔
b ≥ 256F2>k /(εfk )2 .
447
Arbeite im Folgenden unter Annahme, dass C OUNT S KETCH
¨
zu jedem Update-Zeitpunkt Abschatzungen
fur
¨ alle
¨
¨
Haufigkeiten
mit Fehler hochstens
(ε/2)fk liefert.
(Das passiert mit Wskt. mindestens 1 − δ.)
Beobachtung:
• Zu jedem Zeitpunkt alle Schatzwerte
¨
fur
¨ Daten im
¨
(ε/2)fk .
Suchbaum mit Fehler hochstens
• Damit kann Algorithmus Werte richtig sortieren, deren
¨
Haufigkeiten
sich um mehr als εfk unterscheiden.
448
Behauptung: Im Baum zum Schluss kein Wert i ≥ k + 1
¨
mit Haufigkeit
kleiner als (1 − ε)fk .
• Perfekte Losung
¨
hat zum Schluss 1, . . . , k im Suchbaum.
¨
Algorithmus muss einen Wert davon verdrangt
haben,
dies sei j ∈ {1, . . . , k }.
• Einfugezeitpunkt
¨
¨
von i: Schatzwerte
f i , f j mit f i > f j
¨
(Verdrangung).
Aber:
• f i ≤ f i + (ε/2)fk < (1 − ε/2)fk .
• f j ≥ f j − (ε/2)fk ≥ (1 − ε/2)fk .
Widerspruch.
¨
¨
Analog: Alle Werte mit absoluter Haufigkeit
großer
als
(1 + ε)fk zum Schluss im Suchbaum.
449
Insgesamt:
Satz 4.44:
Sei b = max 8k , 256F2>k /(εfk )2 . Dann stellt der
Algorithmus TOP -k -C OUNT S KETCH auf der Basis von
r = (log(n/δ)) Kopien von C OUNT S KETCH und einer
Dictionary-Datenstruktur einen Datenstromalgorithmus fur
¨
¨
die Losung
des Problems Top-k -(ε, δ)-Approximation dar.
Speicherplatz im Wesentlichen dominiert von F2>k /fk2
¨
(genauere Analyse Ubungsaufgabe).
Wann liefert das gute Ergebnisse?
Verteilung fk+1 /n, . . . , fm /n nicht zu nahe an
Gleichverteilung, z. B. fur
¨ Potenzgesetzverteilungen.
450
4.8 Histogramme
Problem in allgemeiner Form:
Approximation von Funktion durch abschnittsweise
konstante Funktion, mit wenigen Abschnitten.
Hier: Funktion gegeben durch f1 , . . . , fn ∈ {−w , . . . , w }.
¨
¨
Haufig:
f1 , . . . , fn absolute Haufigkeiten.
Motivation:
Anfrageoptimierung, approximative Anfragebearbeitung,
allgemein Komprimierung von Zeitreihen, . . .
451
Mathematisches Szenario:
Gegeben Funktion f , Klasse von Funktionen F , Norm
Finde Funktion a ∈ F , sodass f − a minimal.
Gegenstand der Approximationstheorie.
· .
Hier: Kleinste-Quadrate-Approximation.
• F abschnittsweise konstante Funktionen mit
fester Abschnittsanzahl k ;
• · = · 2 , euklidische Norm.
Datenbank-Gemeinde: V-optimale Histogramme“.
”
Auch andere Normen (z. B. · 1 ) und
viele Problemvarianten.
452
Konkretere Umformulierung:
Finde Zerlegung von {1, . . . , n} in Intervalle I1 , . . . , Ik und
Werte c1 , . . . , ck ∈ Ê, sodass:
k
i=1
VARi → min, VARi :=
Leicht zu sehen: Muss
1
c i = AVGi :=
|Ii |
j∈Ii
|f j − c i |2 .
fj
j∈Ii
¨
wahlen
(dann VARi /|Ii | = Varianz in Intervall Ii ).
Damit verbleibt Wahl der Intervalle I1 , . . . , Ik .
453
Offline-Problem:
Funktionswerte f1 , . . . , fn vorab bekannt.
Berechne Fehler des optimalen Histogramms und
¨
zugehorige
Intervalleinteilung I1 , . . . , Ik .
Idee: Dynamische Programmierung.
Sei
OPT[p, i]
:= Fehler des optimalen Histogramms
fur
¨ f1 , . . . , f i mit p Intervallen.
b
VAR[a . . . b] :=
AVG[a . . . b] :=
i=a
(f i − AVG[a . . . b])2 , wobei
1
b−a+1
b
fi.
i=a
454
¨
Bellmansche Optimalitatsgleichung:
• OPT[1, i] = VAR[1 . . . i], i = 1, . . . , n;
• Fur
¨ p = 2, . . . , k und i = 1, . . . , n:
OPT[p, i] = min1≤x≤i−1 OPT[p − 1, x] + VAR[x + 1 . . . i] .
Lemma 4.45:
b
VAR[a . . . b] =
i=a
f i2 + (b − a + 1) · AVG[a . . . b].
¨
(Beweis Ubugungsaufgabe.)
i
i
Arrays mit j=1
f j bzw. j=1
¨ alle i in Zeit O(n)
f j2 fur
berechnen, dann alle VAR-Werte in Zeit O(1).
Insgesamt Platz O(kn), Rechenzeit O kn2 .
455
Bemerkung:
Wie (fast) immer bei dynamischer Programmierung reicht es
im Wesentlichen, sich Berechnung der OPT-Tabelle zu
uberlegen.
¨
¨
Erganzung
fur
¨ Ausgabe der Intervallzerlegung:
Speichere fur
¨ alle p, i auch optimalen Zerlegungspunkt x,
¨ wurde.
der fur
¨ OPT[p, i] gewahlt
(Wieder k × n-Tabelle.)
Dieses x ist linke Grenze fur
¨ letztes Intervall in optimaler
Zerlegung. Rekursiv weiter durch Tabelle hangeln.
Aber: Ohne Zerlegung Speicherplatz leicht auf O(n)
verbesserbar, mit Zerlegung schwerer und problematisch fur
¨
Erweiterung auf 1-Runden-Datenstromalgorithmus.
456
¨
Problem fur
¨ sortierte Datenstrome:
¨ Definitionsbereich der Funktion,
Werte sortiert gemaß
Eingabedatenstrom ist a = (f1 , . . . , fn ).
(Komplexer Algorithmus fur
¨ unsortiertes Problem,
benutzt u. a. auch hier vorgestellte Ideen.)
¨
Berechne ε-approximative Losung,
d. h.
¨
OPT[k , n] ≤ Wert der Losung
≤ (1 + ε)OPT[k , n].
Hier: Deterministischer Algorithmus dafur.
¨
Arbeit: Guha, Koudas, Shim (2001).
457
Bei genugend
¨
Speicherplatz
Anpassung des alten Algorithmus einfach:
Sei OPT-Tabelle mit optimalen Werten
fur
¨ f1 , . . . , fn bekannt.
Dann Update fur
¨ neuen Wert fn+1 , indem
(n + 1)-te Spalte der OPT-Tabelle neu berechnet wird.
¨
Problem: OPT-Tabelle benotigt
Platz
(kn).
458
Idee: Nur noch logarithmisch viele Zwischenpunkte x in
OPT[k , n] =
min
1≤x≤n−1
OPT[k − 1, x] + VAR[x + 1 . . . n] .
Zwischenpunkte d1 , . . . , dℓ so, dass Abweichung vom
Optimum nicht zu groß.
Wichtige Beobachtung:
Proposition 4.46:
Fur
¨ 1 ≤ a ≤ x ≤ b ≤ n gilt:
• VAR[x, n] ≥ VAR[b, n];
• OPT[p, a] ≤ OPT[p, x].
459
¨
Sei OPT∗ [k , n] Optimum auf vergrobertem
Definitionsbereich mit Zwischenpunkten
d1 = 1, d2 , . . . , dℓ−1 , dℓ = n.
Will Zwischenpunkte mit
OPT∗ [k , di+1 ] ≤ (1 + δ) · OPT∗ [k , di ]
¨
fur
¨ kleines δ > 0, falls di+1 > di + 1 (Wahl von δ spater.)
Dazu Einteilung d1 , . . . , dℓ und OPT∗ gleichzeitig
mit Datenstromalgorithmus berechnen.
460
Document
Kategorie
Gesundheitswesen
Seitenansichten
17
Dateigröße
88 KB
Tags
1/--Seiten
melden