Gebrochene Kaskadierung - Fractional cascading

In der Informatik ist die fraktionierte Kaskadierung eine Technik, um eine Folge von binären Suchen nach demselben Wert in einer Folge zusammengehöriger Datenstrukturen zu beschleunigen . Die erste binäre Suche in der Sequenz dauert logarithmisch, wie es bei binären Suchen üblich ist, aber nachfolgende Suchen in der Sequenz sind schneller. Die ursprüngliche Version von Fractional Cascading, in zwei Papieren von eingeführt Chazelle und Guibas 1986 ( Chazelle & Guibas 1986a ; Chazelle & Guibas 1986b ), die Idee der Kaskadierung, mit Ursprung in kombinierten Bereichssuche Datenstrukturen von Lueker (1978) und Willard (1978 ) mit der Idee des fraktionierten Samplings, die von Chazelle (1983) stammt . Spätere Autoren führten komplexere Formen der fraktionalen Kaskadierung ein, die es ermöglichen, die Datenstruktur beizubehalten, wenn sich die Daten durch eine Folge von diskreten Einfüge- und Löschereignissen ändern.

Beispiel

Betrachten Sie als einfaches Beispiel für fraktionale Kaskadierung das folgende Problem. Als Eingabe erhalten wir eine Sammlung von k geordneten Listen L _i von Zahlen, so dass die Gesamtlänge Σ| L _i | aller Listen ist n und muss sie verarbeiten, damit wir in jeder der k Listen binäre Suchen nach einem Abfragewert q durchführen können . Zum Beispiel mit k = 4 und n = 17,

L ₁ = 24, 64, 65, 80, 93

L ₂ = 23, 25, 26

L ₃ = 13, 44, 62, 66

L ₄ = 11, 35, 46, 79, 81

Die einfachste Lösung für dieses Suchproblem besteht darin, jede Liste separat zu speichern. Wenn wir dies tun, ist der Platzbedarf O( n ), aber die Zeit zum Durchführen einer Abfrage beträgt O( k log( n / k )), da wir in jeder von k Listen eine separate binäre Suche durchführen müssen . Der schlimmste Fall zum Abfragen dieser Struktur tritt ein, wenn jede der k Listen die gleiche Größe n / k hat , so dass jede der k binären Suchen, die an einer Abfrage beteiligt sind, Zeit O(log( n / k )) benötigt.

Eine zweite Lösung ermöglicht schnellere Abfragen auf Kosten von mehr Platz: Wir können alle k Listen zu einer einzigen großen Liste L zusammenführen und jedem Element x von L eine Liste der Ergebnisse der Suche nach x in jeder der kleineren Listen zuordnen L _ich . Wenn wir ein Element dieser zusammengeführten Liste als x [ a , b , c , d ] beschreiben, wobei x der Zahlenwert und a , b , c und d die Positionen (die erste Zahl hat Position 0) des nächsten Elements sind mindestens so groß wie x in jeder der ursprünglichen Eingabelisten (oder die Position nach dem Ende der Liste, wenn kein solches Element existiert), dann hätten wir

L = 11 [0,0,0,0], 13 [0,0,0,1], 23 [0,0,1,1], 24 [0,1,1,1], 25 [1, 1,1,1], 26 [1,2,1,1],

35 [1,3,1,1], 44 [1,3,1,2], 46 [1,3,2,2], 62 [1,3,2,3], 64 [1,3, 3,3], 65 [2,3,3,3],

66 [3,3,3,3], 79 [3,3,4,3], 80 [3,3,4,4], 81 [4,3,4,4], 93 [4,3, 4,5]

Diese zusammengeführte Lösung ermöglicht eine Abfrage in der Zeit O(log n  +  k ): Suchen Sie einfach nach q in L und melden Sie dann die Ergebnisse, die bei dem durch diese Suche gefundenen Element x gespeichert sind . Wenn zum Beispiel q = 50 ist, findet die Suche nach q in L das Element 62[1,3,2,3], von dem wir die Ergebnisse L ₁ [1] = 64, L ₂ [3] (ein Flag-Wert Dies zeigt an, dass q das Ende von L ₂ überschritten hat, L ₃ [2] = 62 und L ₄ [3] = 79. Diese Lösung zahlt jedoch einen hohen Nachteil an Raumkomplexität: Sie verwendet Raum O( kn ) als jede der n Elemente in L müssen eine Liste von k Suchergebnissen speichern .

Die fraktionierte Kaskadierung ermöglicht die Lösung desselben Suchproblems mit Zeit- und Raumgrenzen, die das Beste aus beiden Welten erfüllen: Abfragezeit O(log n  +  k ) und Raum O( n ). Die fraktionierte Kaskadierungslösung besteht darin, eine neue Sequenz von Listen M _i zu speichern . Die letzte Liste in dieser Folge, M _k , ist gleich L _k ; jede frühere Liste M _i wird durch Verschmelzen von L _i mit jedem zweiten Element von M _{i +1 gebildet} . Mit jedem Element x in dieser zusammengeführten Liste speichern wir zwei Zahlen: die Position, die sich aus der Suche nach x in L _i ergibt, und die Position, die sich aus der Suche nach x in M _{i +1} ergibt . Für die obigen Daten würden wir die folgenden Listen erhalten:

M ₁ = 24 [0, 1], 25 [1, 1], 35 [1, 3], 64 [1, 5], 65 [2, 5], 79 [3, 5], 80 [3, 6 ], 93 [4, 6]

M ₂ = 23 [0, 1], 25 [1, 1], 26 [2, 1], 35 [3, 1], 62 [3, 3], 79 [3, 5]

M ₃ = 13 [0, 1], 35 [1, 1], 44 [1, 2], 62 [2, 3], 66 [3, 3], 79 [4, 3]

M ₄ = 11 [0, 0], 35 [1, 0], 46 [2, 0], 79 [3, 0], 81 [4, 0]

Angenommen, wir möchten eine Abfrage in dieser Struktur für q = 50 durchführen. Wir führen zuerst eine binäre Standardsuche nach q in M _{1 durch} und finden den Wert 64 [1,5]. Die "1" in 64 [1,5], sagt uns , dass die Suche nach q in L ₁ zurückkehren sollte L ₁ [1] = 64. Die "5" in 64 [1,5] sagt uns , dass die ungefähre Lage des q in M ₂ ist Position 5. Genauer gesagt würde eine binäre Suche nach q in M ₂ entweder den Wert 79[3,5] an Position 5 oder den Wert 62[3,3] eine Stelle früher zurückgeben. Indem wir q mit 62 vergleichen und beobachten, dass es kleiner ist, bestimmen wir, dass das korrekte Suchergebnis in M ₂ 62 ist[3,3]. Die erste "3" in 62 [3,3] sagt uns , dass die Suche nach q in L ₂ zurückkehren sollte L ₂ [3], ein Flag - Wert, was bedeutet , q ist über das Ende der Liste L ₂ . Die zweite "3" in 62[3,3] sagt uns, dass die ungefähre Position von q in M ₃ Position ₃ ist. Genauer gesagt würde eine binäre Suche nach q in M ₃ entweder den Wert 62[2,3] an Position . zurückgeben 3, oder der Wert 44[1,2] eine Stelle früher. Ein Vergleich von q mit dem kleineren Wert 44 zeigt uns, dass das korrekte Suchergebnis in M ₃ 62 ist[2,3]. Die "2" in 62 [2,3] sagt uns , dass die Suche nach q in L ₃ sollte zurückkehren L ₃ [2] = 62, und die "3" in 62 [2,3] sagt uns , dass das Ergebnis des Suchens für q in M ₄ ist entweder M ₄ [3] = 79[3,0] oder M ₄ [2] = 46[2,0]; Vergleichen q mit 46 zeigt , dass das richtige Ergebnis ist 79 [3,0] und dass das Ergebnis des Suchens für q in L ₄ ist L ₄ [3] = 79. Somit haben wir gefunden , q in jedes der vier Listen, durch Durchführen einer binären Suche in der einzelnen Liste M ₁ gefolgt von einem einzelnen Vergleich in jeder der aufeinanderfolgenden Listen.

Allgemeiner gesagt führen wir für jede Datenstruktur dieses Typs eine Abfrage durch, indem wir eine binäre Suche nach q in M _{1 durchführen} und aus dem resultierenden Wert die Position von q in L ₁ bestimmen . Dann verwenden wir für jedes i > 1 die bekannte Position von q in M _i , um seine Position in M _{i +1 zu finden} . Der mit der Position von q in M _i verbundene Wert zeigt auf eine Position in M _{i +1} , die entweder das richtige Ergebnis der binären Suche nach q in M _{i +1 ist} oder nur einen Schritt von diesem korrekten Ergebnis entfernt ist, also stepping von i nach i  + 1 erfordert nur einen einzigen Vergleich. Somit beträgt die Gesamtzeit für eine Abfrage O(log n  +  k ).

In unserem Beispiel haben die fraktional kaskadierten Listen insgesamt 25 Elemente, weniger als das Doppelte der ursprünglichen Eingabe. Im Allgemeinen ist die Größe von M _i in dieser Datenstruktur höchstens

${\displaystyle |L_{i}|+{\frac {1}{2}}|L_{i+1}|+{\frac {1}{4}}|L_{i+2}|+\cdots +{\frac {1}{2^{j}}}|L_{i+j}|+\cdots ,}$

wie man leicht durch Induktion beweisen kann. Daher beträgt die Gesamtgröße der Datenstruktur höchstens

${\displaystyle \sum |M_{i}|=\sum |L_{i}|\left(1+{\frac {1}{2}}+{\frac {1}{4}}+\cdots \ rechts)\leq 2n=O(n),}$

wie man sehen kann, indem man die Beiträge zur Gesamtgröße, die von derselben Eingabeliste L _{i stammen,} miteinander umgruppiert .

Das allgemeine Problem

Im Allgemeinen beginnt die fraktionierte Kaskadierung mit einem Kataloggraphen , einem gerichteten Graphen, in dem jeder Scheitelpunkt mit einer geordneten Liste gekennzeichnet ist. Eine Abfrage in dieser Datenstruktur besteht aus einem Pfad im Graphen und einem Abfragewert q ; die Datenstruktur muss die Position von q in jeder der geordneten Listen bestimmen, die den Scheitelpunkten des Pfades zugeordnet sind. Für das obige einfache Beispiel ist der Kataloggraph selbst ein Pfad mit nur vier Knoten. Es ist möglich, dass spätere Scheitelpunkte im Pfad dynamisch als Teil einer Abfrage als Reaktion auf die Ergebnisse der Suchen in früheren Abschnitten des Pfads bestimmt werden.

Um Anfragen dieser Art zu handhaben, werden für einen Graphen, in dem jeder Knoten höchstens d eingehende und höchstens d ausgehende Kanten für eine Konstante d hat , die Listen, die jedem Knoten zugeordnet sind, um einen Bruchteil der Elemente von jedem ausgehenden Nachbarn des erweitert Scheitel; der Bruch muss kleiner als 1/ d gewählt werden , damit der Gesamtbetrag, um den alle Listen erweitert werden, in der Eingabegröße linear bleibt. Jedes Element in jeder erweiterten Liste speichert damit die Position dieses Elements in der nicht erweiterten Liste, die an demselben Scheitelpunkt gespeichert ist, und in jeder der ausgehenden Nachbarlisten. Im obigen einfachen Beispiel ist d = 1, und wir haben jede Liste mit einem 1/2-Anteil der benachbarten Elemente erweitert.

Eine Abfrage in dieser Datenstruktur besteht aus einer standardmäßigen binären Suche in der erweiterten Liste, die dem ersten Scheitelpunkt des Abfragepfads zugeordnet ist, zusammen mit einfacheren Suchen an jedem nachfolgenden Scheitelpunkt des Pfads. Wenn ein Bruchteil von 1/ r von Elementen verwendet wird, um die Listen von jedem benachbarten Element zu erweitern, dann kann jedes nachfolgende Abfrageergebnis innerhalb von höchstens r Schritten von der Position gefunden werden, die beim Abfrageergebnis vom vorherigen Pfadknotenpunkt gespeichert ist, und kann daher in konstanter Zeit gefunden, ohne eine vollständige binäre Suche durchführen zu müssen.

Dynamische Bruchkaskadierung

Bei der dynamischen fraktionalen Kaskadierung kann sich die an jedem Knoten des Kataloggraphen gespeicherte Liste dynamisch durch eine Folge von Aktualisierungen ändern, in die Listenelemente eingefügt und gelöscht werden. Dies verursacht mehrere Schwierigkeiten für die Datenstruktur.

Erstens, wenn ein Element an einem Knoten des Katalogdiagramms eingefügt oder gelöscht wird, muss es in die diesem Knoten zugeordnete erweiterte Liste platziert werden und kann bewirken, dass sich Änderungen auf andere Knoten des Katalogdiagramms ausbreiten. Anstatt die erweiterten Listen in Arrays zu speichern, sollten sie als binäre Suchbäume gespeichert werden, damit diese Änderungen effizient gehandhabt werden können und dennoch binäre Suchen der erweiterten Listen möglich sind.

Zweitens kann ein Einfügen oder Löschen eine Änderung der Teilmenge der Liste bewirken, die einem Knoten zugeordnet ist, der an benachbarte Knoten des Kataloggraphen weitergegeben wird. Es ist in der dynamischen Einstellung nicht mehr möglich, dass diese Teilmenge für einige d als die Elemente an jeder d- ten Position der Liste ausgewählt wird , da sich diese Teilmenge nach jeder Aktualisierung zu drastisch ändern würde. Vielmehr erlaubt eine Technik, die eng mit B-Bäumen verwandt ist, die Auswahl eines Bruchteils von Daten, der garantiert kleiner als 1/ d ist , wobei die ausgewählten Elemente garantiert eine konstante Anzahl von Positionen voneinander in der vollständigen Liste beabstandet sind, und so dass ein Einfügen oder Löschen in die einem Knoten zugeordnete erweiterte Liste bewirkt, dass sich Änderungen für einen Bruchteil der Operationen, der kleiner als 1/ d ist, an andere Knoten ausbreiten . Auf diese Weise erfüllt die Verteilung der Daten auf die Knoten die für einen schnellen Abfragealgorithmus erforderlichen Eigenschaften, während gleichzeitig gewährleistet wird, dass die durchschnittliche Anzahl von binären Suchbaumoperationen pro Dateneinfügung oder -löschung konstant ist.

Drittens und am kritischsten behält die statische kaskadierende Datenstruktur mit Bruchteilen für jedes Element x der erweiterten Liste an jedem Knoten des Kataloggraphen den Index des Ergebnisses bei, das bei der Suche nach x unter den Eingabeelementen von diesem Knoten erhalten würde und unter den erweiterten Listen, die an benachbarten Knoten gespeichert sind. Es wäre jedoch zu teuer, diese Informationen in der dynamischen Umgebung zu verwalten. Das Einfügen oder Löschen eines einzelnen Wertes x kann dazu führen, dass sich die Indizes ändern, die bei einer unbegrenzten Anzahl anderer Werte gespeichert sind. Stattdessen verwalten dynamische Versionen der fraktionierten Kaskadierung mehrere Datenstrukturen für jeden Knoten:

• Eine Abbildung der Elemente in der erweiterten Liste des Knotens auf kleine Ganzzahlen, so dass die Reihenfolge der Positionen in der erweiterten Liste der Vergleichsreihenfolge der Ganzzahlen entspricht, und eine umgekehrte Abbildung dieser Ganzzahlen zurück auf die Listenelemente. Eine Technik von Dietz (1982) erlaubt es, diese Nummerierung effizient aufrechtzuerhalten.
• Eine ganzzahlige Suchdatenstruktur wie ein van Emde Boas-Baum für die Zahlen, die der Eingabeliste des Knotens zugeordnet sind. Mit dieser Struktur und der Abbildung von Elementen auf ganze Zahlen kann man effizient für jedes Element x der erweiterten Liste das Element finden, das bei der Suche nach x in der Eingabeliste gefunden würde.
• Für jeden Nachbarknoten im Kataloggraphen wird eine ähnliche ganzzahlige Suchdatenstruktur für die Zahlen, die der Teilmenge der Daten zugeordnet sind, vom Nachbarknoten verbreitet. Mit dieser Struktur und der Abbildung von Elementen auf ganze Zahlen kann man effizient für jedes Element x der erweiterten Liste eine Position innerhalb einer konstanten Anzahl von Schritten der Position von x in der dem benachbarten Knoten zugeordneten erweiterten Liste finden.

Diese Datenstrukturen ermöglichen die Durchführung einer dynamischen fraktionalen Kaskadierung zu einer Zeit von O(log  n ) pro Einfügung oder Löschung, und eine Folge von k binären Suchen, die einem Pfad der Länge k im Kataloggraphen folgen , können in der Zeit O(log  n  +  k  log log  n ).

Anwendungen

Die konvexen Schichten eines Punktsatzes, Teil einer effizienten fraktional kaskadierten Datenstruktur für die Berichterstellung auf halber Ebene.

Typische Anwendungen der fraktionalen Kaskadierung umfassen Bereichssuchdatenstrukturen in der Computergeometrie . Betrachten wir zum Beispiel das Problem der Halbebene Bereich Reporting : Das heißt, eine feste Menge von sich schneid n Punkte mit einer Abfrage Halbebene und Auflistung aller Punkte in der Kreuzung. Das Problem besteht darin, die Punkte so zu strukturieren, dass eine solche Anfrage hinsichtlich der Schnittmenge h effizient beantwortet werden kann . Eine für diesen Zweck verwendbare Struktur sind die konvexen Schichten der Eingabepunktmenge, eine Familie verschachtelter konvexer Polygone, bestehend aus der konvexen Hülle der Punktmenge und den rekursiv konstruierten konvexen Schichten der restlichen Punkte. Innerhalb eines einzelnen Layers können die Punkte innerhalb der Abfragehalbebene gefunden werden, indem eine binäre Suche nach der Steigung der Halbebenen-Grenzlinie in der sortierten Folge von konvexen Polygonkantensteigungen durchgeführt wird, was zu dem Polygonscheitelpunkt führt, der sich innerhalb der Abfragehälfte befindet -ebene und am weitesten von seiner Grenze entfernt, und dann sequentiell entlang der Polygonkanten suchen , um alle anderen Scheitelpunkte innerhalb der Abfragehalbebene zu finden. Das Problem der Berichterstellung über die gesamte Halbebene kann gelöst werden, indem diese Suchprozedur beginnend von der äußersten Schicht und nach innen fortgesetzt wird, bis eine Schicht erreicht wird, die von dem Abfragehalbraum getrennt ist. Die fraktionierte Kaskadierung beschleunigt die aufeinanderfolgenden binären Suchen zwischen den Folgen von Polygonkantenneigungen in jeder Schicht, was zu einer Datenstruktur für dieses Problem mit Raum O( n ) und Abfragezeit O(log  n  +  h ) führt. Die Datenstruktur kann in der Zeit O (konstruiert werden n  log  n durch einen Algorithmus von) Chazelle (1985) . Wie in unserem Beispiel handelt es sich bei dieser Anwendung um binäre Suchen in einer linearen Abfolge von Listen (der verschachtelten Abfolge der konvexen Schichten), sodass der Kataloggraph nur ein Pfad ist.

Eine andere Anwendung der fraktionalen Kaskadierung in geometrischen Datenstrukturen betrifft die Punktposition in einer monotonen Unterteilung, das heißt eine Unterteilung der Ebene in Polygone, so dass jede vertikale Linie ein beliebiges Polygon in höchstens zwei Punkten schneidet. Wie Edelsbrunner, Guibas & Stolfi (1986) gezeigt haben, kann dieses Problem gelöst werden, indem eine Folge von polygonalen Pfaden gefunden wird, die sich von links nach rechts über die Unterteilung erstrecken, und binäres Suchen nach dem niedrigsten dieser Pfade, der über dem Abfragepunkt liegt. Das Testen, ob der Abfragepunkt über oder unter einem der Pfade liegt, kann selbst als binäres Suchproblem gelöst werden, indem nach der x-Koordinate der Punkte unter den x-Koordinaten der Pfadscheitelpunkte gesucht wird, um zu bestimmen, welche Pfadkante über oder unter dem Abfragepunkt. Somit kann jede Punktortsabfrage als äußere Schicht einer binären Suche unter den Pfaden gelöst werden, wobei jeder Schritt selbst eine binäre Suche unter x-Koordinaten von Scheitelpunkten durchführt. Die fraktionierte Kaskadierung kann verwendet werden, um die Zeit für die inneren binären Suchen zu beschleunigen, indem die Gesamtzeit pro Abfrage unter Verwendung einer Datenstruktur mit dem Leerzeichen O( n ) auf O(log n ) reduziert wird  . In dieser Anwendung ist der Kataloggraph ein Baum, der die möglichen Suchsequenzen der äußeren binären Suche darstellt.

Jenseits der Computergeometrie wenden Lakshman & Stiliadis (1998) und Buddhikot, Suri & Waldvogel (1999) die fraktionierte Kaskadierung beim Entwurf von Datenstrukturen für die schnelle Paketfilterung in Internet-Routern an . Gaoet al. (2004) verwenden Fractional Cascading als Modell für die Datenverteilung und -abfrage in Sensornetzwerken .

Verweise