Sind probabilistische Suchdatenstrukturen nützlich?

9

Eine SkipList bietet die gleichen -Grenzen für die Suche wie ein ausgeglichener Baum mit dem Vorteil, dass kein Neuausgleich erforderlich ist. Da die SkipList mit zufälligen Münzwürfen erstellt wird, gelten diese Grenzen nur, solange die Struktur der SkipList ausreichend "ausgeglichen" ist. Insbesondere mit der Wahrscheinlichkeit für eine Konstante kann die ausgeglichene Struktur nach dem Einfügen eines Elements verloren gehen. $O(\log n)$ $1/n^c$ $c>0$

Angenommen, ich möchte eine Überspringliste als Speicher-Backend in einer Webanwendung verwenden, die möglicherweise für immer ausgeführt wird. Nach einer polynomiellen Anzahl von Operationen geht die ausgeglichene Struktur der SkipList sehr wahrscheinlich verloren.

Ist meine Argumentation richtig? Haben solche probabilistischen Such- / Speicherdatenstrukturen praktische Anwendungen und wenn ja, wie wird das oben genannte Problem vermieden?

Bearbeiten: Mir ist bekannt, dass es deterministische Varianten der SkipList gibt, deren Implementierung im Vergleich zur (klassischen) randomisierten SkipList viel komplizierter ist.

data-structures search-trees probabilistic-algorithms jemanden
quelle

1

Welche spezielle Anwendung haben Sie im Sinn?

Pratik Deoghare

6

Ich glaube nicht, dass es eine polynomielle Wahrscheinlichkeit gibt, das Gleichgewicht zu verlieren. Nachdem Sie ein Element in eine Überspringliste eingefügt haben, erstellen Sie einen Turm mit Kopien darüber, indem Sie eine Münze werfen, bis sie auftaucht.

Sie haben also Ebenen mit immer weniger Elementen, wenn Sie oben ankommen. Da ein Turm eine Höhe mit einer Wahrscheinlichkeit von , gibt es ein Element in Höhe mit einer Wahrscheinlichkeit (Vereinigungsgrenze) von weniger als . Daher hat ein Element auf der Ebene eine Wahrscheinlichkeit von weniger als . Türme der Höhe haben eine subpolynomielle Wahrscheinlichkeit. Sei das maximale Niveau, dann haben wir $k$ $2^{-k}$ $k$ $n/2^k$ $c\log n$ $1/n^c$ $\omega(\log n)$ $M$

E [M] = \sum_{k \geq 1} P r (M \geq k) \leq \log (n) + \sum_{k \leq \log (n)} n / 2^{k} = \log (n) + 2.

$E[M] = \sum_{k\geq 1} Pr(M\geq k) \leq \log(n) + \sum_{k\le \log(n)} n/2^k = \log(n) + 2.$

Darüber hinaus auf Ebene gibt es Elemente mit sehr hohen Wahrscheinlichkeit, da dies die Summe ist unabhängige Zufallsvariablen und Sie können gebundenen Tschernows verwenden. $k$ $n/2^k$ $n$

Da Sie auch zeigen können, dass Sie nur eine konstante Anzahl von Schritten pro Ebene ausführen (mit sehr hoher Wahrscheinlichkeit!), Sind die Suchkosten logarithmisch.

Sie müssten also in der Tat sehr unglücklich sein, um eine unausgeglichene Liste zu erhalten. Beachten Sie, dass "Glück" hier unabhängig von Ihren Daten ist, anders als beispielsweise bei unausgeglichenen Suchbäumen. Münzwürfe in Überspringlisten sind immer zufällig.

Soweit ich weiß, sind Überspringlisten von großem praktischem Interesse, da sie relativ einfach als sperrfreie Suchstrukturen mit den offensichtlichen Vorteilen implementiert werden können. B-Bäume hingegen sind bei gleichzeitigen Zugriffen nur schwer performant zu machen.

adrianN
quelle

Die erwartete Tiefe von binären Suchbäumen ist ebenfalls logarithmisch. Warum ist die Situation hier besser? (Sie nehmen auch zufällige Permutationen an, richtig?)

Raphael

2

In Suchbäumen hängt die Tiefe von den Daten ab. Wenn Sie Zufallszahlen eingeben, hat es eine logarithmische Tiefe mit sehr hoher Wahrscheinlichkeit. In der Praxis sind Daten jedoch nicht zufällig. Überspringlisten verwenden die Daten nicht als Zufallsquelle, daher besteht dieses Problem nicht.

AdrianN

1

Überspringlisten haben andere Eigenschaften, die sie in Situationen attraktiv machen können, in denen andere Vorgänge als nur Einfügen / Nachschlagen / Löschen verwendet werden.

Zum Beispiel haben Sprunglisten erwartete lokale Aktualisierungen, wenn der Änderungsort bekannt ist. Dies ist sicherlich in Worst-Case-Zeit mit bestimmten ausgeglichenen binären Suchbäumen möglich, aber die Implementierung dieser Strukturen ist in der Regel ziemlich kompliziert. $O(1)$ $O(1)$

Darüber hinaus waren Überspringlisten eine beliebte Methode, um gleichzeitige vergleichsbasierte Suchstrukturen zu implementieren. In der Vergangenheit haben ausgewogene Suchbäume bei hohen gleichzeitigen Konflikten nicht so gut funktioniert.

jbapple
quelle

Sind probabilistische Suchdatenstrukturen nützlich?

Antworten: