Dein Lernbereich wird geladen
App wird gestartet …
Dein Lernbereich wird geladen
App wird gestartet …
Die Näherung schätzt die Wahrscheinlichkeit eines Falsch-Positivs bei einem klassischen Bloom-Filter.
Ansehen kostenlos · Karteikarten oder Multiple-Choice-Test · übernehmen ab Essential
Formel
pFP dimensionslos; m Bitplätze; n gespeicherte Elemente; k Hashfunktionen
| Symbol | Bedeutung | Einheit |
|---|---|---|
| Wahrscheinlichkeit, ein nicht gespeichertes Element fälschlich als vorhanden zu melden | dimensionslos | |
| Anzahl Bits im Filter | Bits | |
| Anzahl eingefügter Elemente | Elemente | |
| Anzahl unabhängiger Hashfunktionen | Anzahl |
p_{FP}\approx\left(1-e^{-kn/m}\right)^kDie klassische Näherung setzt gleichmäßig verteilte, hinreichend unabhängige Hashfunktionen und einen Standard-Bloom-Filter ohne Löschungen voraus. Ein Bloom-Filter hat keine Falsch-Negative, kann aber Falsch-Positive liefern. Die Formel nutzt die approximierte Setzwahrscheinlichkeit eines Bits 1−e^(−kn/m). Bei kleinem m/n steigt die Rate; optimale k liegt näherungsweise bei (m/n)ln 2. Reale Hashkorrelationen können die Näherung verändern.
Die klassische Näherung setzt gleichmäßig verteilte, hinreichend unabhängige Hashfunktionen und einen Standard-Bloom-Filter ohne Löschungen voraus. Ein Bloom-Filter hat keine Falsch-Negative, kann aber Falsch-Positive liefern. Die Formel nutzt die approximierte Setzwahrscheinlichkeit eines Bits 1−e^(−kn/m). Bei kleinem m/n steigt die Rate; optimale k liegt näherungsweise bei (m/n)ln 2. Reale Hashkorrelationen können die Näherung verändern.
Die Näherung schätzt die Wahrscheinlichkeit eines Falsch-Positivs bei einem klassischen Bloom-Filter.
Optimale Hashanzahl
kopt≈(m/n)ln 2
Erkläre am Beispiel zu Bloom-Filter: Falsch-Positiv-Wahrscheinlichkeit, welche Eingabegrößen zur gesuchten Ausgabe führen.
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Die Näherung schätzt die Wahrscheinlichkeit eines Falsch-Positivs bei einem klassischen Bloom-Filter.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Die Beziehung ohne ihre angegebenen Voraussetzungen auf einen anderen Fall übertragen.
Prüfe vor dem Einsetzen den Gültigkeitsbereich: Die klassische Näherung setzt gleichmäßig verteilte, hinreichend unabhängige Hashfunktionen und einen Standard-Bloom-Filter ohne Löschungen voraus. Ein Bloom-Filter hat keine Falsch-Negative, kann aber Falsch-Positive liefern. Die Formel nutzt die approximierte Setzwahrscheinlichkeit.
Formelcluster
Die Näherung schätzt die Wahrscheinlichkeit eines Falsch-Positivs bei einem klassischen Bloom-Filter.
Für m=1000 Bits, n=100 Elemente und k=7 gilt p≈(1−e^(−0,7))7≈0,0082, also rund 0,82 Prozent Falsch-Positive.
Speicherplatz, Hashanzahl und tolerierte Falsch-Positiv-Rate probabilistischer Mengenfilter dimensionieren.
Eine typische Aufgabe Schritt für Schritt: Bloom-Filter: Falsch-Positiv-Wahrscheinlichkeit (pFP ≈ (1−e⁻ᵏⁿ/ᵐ)ᵏ).
Aufgabe
Erkläre am Beispiel zu Bloom-Filter: Falsch-Positiv-Wahrscheinlichkeit, welche Eingabegrößen zur gesuchten Ausgabe führen.
Rechenweg
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Die Näherung schätzt die Wahrscheinlichkeit eines Falsch-Positivs bei einem klassischen Bloom-Filter.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Ein Bloom-Filter prüft probabilistisch, ob ein Element eingefügt wurde. Ein positives Ergebnis kann stimmen oder ein Falsch-Positiv sein; ein negatives Ergebnis bedeutet bei klassischem Filter sicher, dass das Element fehlt. pFP beschreibt die Wahrscheinlichkeit eines falschen positiven Ergebnisses für ein nicht eingefügtes Element unter dem angenommenen Hashmodell. Sie ist kein Fehleranteil unter allen Abfragen. Die Standardnäherung nimmt gleichmäßige unabhängige Hashfunktionen und keine Löschungen an. Ein Bloom-Filter kann Falsch-Positive, aber keine Falsch-Negative liefern; Hashkorrelationen und Überfüllung ändern die tatsächliche Rate. n bezeichnet die Zahl unterschiedlicher eingefügter Elemente, m die Bitzahl und k die Hashfunktionen. Die theoretische Erwartung garantiert keine Rate für konkrete Hashfamilien; plane Kapazitätsmarge ein und beobachte den Füllgrad im Betrieb.
Setze m=1000, n=100 und k=7 ein. Dann ist kn/m=0,7 und 1−e^(−0,7)≈0,5034. Die siebte Potenz ergibt ungefähr 0,0082, also 0,82 Prozent. Probe: kopt≈(m/n)ln2=10·0,693≈6,93; sieben Hashfunktionen liegen nahe am Modelloptimum. Die Standardnäherung nimmt gleichmäßige unabhängige Hashfunktionen und keine Löschungen an. Ein Bloom-Filter kann Falsch-Positive, aber keine Falsch-Negative liefern; Hashkorrelationen und Überfüllung ändern die tatsächliche Rate. n bezeichnet die Zahl unterschiedlicher eingefügter Elemente, m die Bitzahl und k die Hashfunktionen. Die theoretische Erwartung garantiert keine Rate für konkrete Hashfamilien; plane Kapazitätsmarge ein und beobachte den Füllgrad im Betrieb.
Beim Einfügen setzt jede Hashfunktion Bits auf eins; Bits werden beim normalen Bloom-Filter nicht zurückgesetzt. Ein tatsächlich eingefügtes Element findet bei der Abfrage daher alle seine gesetzten Bits wieder. Ein nicht eingefügtes Element kann zufällig ebenfalls nur Einsen treffen und dadurch als vorhanden gelten. Löschungen oder fehlerhafte Implementierungen können diese Eigenschaft aufheben. Die Standardnäherung nimmt gleichmäßige unabhängige Hashfunktionen und keine Löschungen an. Ein Bloom-Filter kann Falsch-Positive, aber keine Falsch-Negative liefern; Hashkorrelationen und Überfüllung ändern die tatsächliche Rate. n bezeichnet die Zahl unterschiedlicher eingefügter Elemente, m die Bitzahl und k die Hashfunktionen. Die theoretische Erwartung garantiert keine Rate für konkrete Hashfamilien; plane Kapazitätsmarge ein und beobachte den Füllgrad im Betrieb.
Mehr Speicherbits m senken bei festem n typischerweise die Belegung und damit pFP. Mehr gespeicherte Elemente n setzen mehr Bits und erhöhen die Falsch-Positiv-Rate. Mehr Hashfunktionen k helfen zunächst, können bei zu vielen Hashes den Filter aber stärker sättigen. Die drei Größen müssen gemeinsam gewählt werden; die optimale k-Näherung hängt von m/n ab. Die Standardnäherung nimmt gleichmäßige unabhängige Hashfunktionen und keine Löschungen an. Ein Bloom-Filter kann Falsch-Positive, aber keine Falsch-Negative liefern; Hashkorrelationen und Überfüllung ändern die tatsächliche Rate. n bezeichnet die Zahl unterschiedlicher eingefügter Elemente, m die Bitzahl und k die Hashfunktionen. Die theoretische Erwartung garantiert keine Rate für konkrete Hashfamilien; plane Kapazitätsmarge ein und beobachte den Füllgrad im Betrieb.
Die klassische Herleitung modelliert Hashplätze als gleichmäßig und weitgehend unabhängig und nähert (1−1/m)^(kn) durch e^(−kn/m) an. Bei großen m ist das oft brauchbar, aber reale Hashfunktionen können korreliert sein. Der Filter kann auch stärker gefüllt werden als geplant. Für kritische Systeme miss die empirische Rate oder nutze engere Analysen statt die Näherung als Garantie zu lesen. Die Standardnäherung nimmt gleichmäßige unabhängige Hashfunktionen und keine Löschungen an. Ein Bloom-Filter kann Falsch-Positive, aber keine Falsch-Negative liefern; Hashkorrelationen und Überfüllung ändern die tatsächliche Rate. n bezeichnet die Zahl unterschiedlicher eingefügter Elemente, m die Bitzahl und k die Hashfunktionen. Die theoretische Erwartung garantiert keine Rate für konkrete Hashfamilien; plane Kapazitätsmarge ein und beobachte den Füllgrad im Betrieb.
Quanta-Prüfungsset
Kuratiertes Prüfungsset für "Bloom-Filter: Falsch-Positiv-Wahrscheinlichkeit":
Frage (Vorderseite)
Welche Formel beschreibt Bloom-Filter: Falsch-Positiv-Wahrscheinlichkeit?
Antwort in deinem Set
Frage (Vorderseite)
Wie stellst du pFP ≈ (1−e⁻ᵏⁿ/ᵐ)ᵏ nach Optimale Hashanzahl um?
Antwort in deinem Set
Frage (Vorderseite)
Welcher typische Fehler passiert bei pFP ≈ (1−e⁻ᵏⁿ/ᵐ)ᵏ?
Antwort in deinem Set
+ 7 weitere Karten: Einheiten, Variablen, Herleitung, Beispiel, Klausuraufgabe
Das Formelset enthält 10 Karten. Nach der Übernahme kannst du sie prüfen und lernen; deine Bewertungen bestimmen die weiteren Wiederholungen.
Die Liste nennt Fachquellen und weiterführende Literatur. Eine Seiten- oder Abschnittsnummer steht dabei, wenn sie Teil der Literaturangabe ist; es handelt sich nicht um wörtliche Zitate.
Erstelle ein kuratiertes FSRS-Prüfungsset für pFP ≈ (1−e⁻ᵏⁿ/ᵐ)ᵏ: Formelabruf, Variablen, Herleitung, Umstellung, Beispiel, typische Fehler und Klausurkontext.
Kuratiertes Formelset · LaTeX · FSRS Spaced Repetition · übernehmen ab Essential