Durchführungskosten ca. Suche nach dem nächsten Nachbarn in einem Quadtree überspringen

10

HINWEIS : Die Frage wurde in meinen Antworten angepasst: Unter der Annahme, dass wir jetzt die niedrigsten Geschwistervorfahren in -Zeit finden können, kann die ANN wirklich in ?O ( log n )O(1)O(logn)


Quadtrees sind effiziente räumliche Indizes. Ich habe ein Rätsel mit der Implementierung einer Suche nach dem nächsten Nachbarn in einer komprimierten Quadtree-Struktur, wie in [2] beschrieben. (Ohne auf Details einzugehen, erfolgt die Suche von oben nach unten entlang sogenannter äquidistanter Quadrate und endet am Endknoten eines äquidistanten Pfades. Im angehängten Bild kann dies einer der Knoten im Südosten sein, die mit Punkten gefüllt sind.)

Damit ihr Algorithmus funktioniert, muss für jeden Knoten - ein Quadrat mit mindestens zwei nicht leeren Quadranten - ein Zeiger für jeden niedrigsten (in der Hierarchie am nächsten gelegenen) Ahnenknoten in jeder der vier Richtungen (Nord, West, Süd) beibehalten werden , Osten). Diese werden durch die grünen Pfeile für den Vorfahren der Knoten nach Westen angezeigt (der Pfeil zeigt auf die Mitte des Ahnenquadrats).

Das Papier behauptet, dass diese Zeiger beim Einfügen und Löschen von Punkten in O (1) aktualisiert werden können. Wenn ich mir jedoch das Einfügen des grünen Punkts anschaue, muss ich anscheinend eine beliebige Anzahl von Zeigern aktualisieren, in diesem Fall sechs davon.

Ich hoffe auf einen Trick, um dieses Zeiger-Update in konstanter Zeit durchzuführen. Vielleicht gibt es eine Form der Indirektion, die ausgenutzt werden kann?

Quadtree vor (links) und nach (rechts) Punkt Einfügung

BEARBEITEN:

Der relevante Abschnitt aus dem Papier ist 6.3, wo er lautet: "Wenn der Pfad gebogen ist, sollten wir zusätzlich zu den niedrigsten Vorfahren von auch für jede der Richtungen die niedrigste berücksichtigen Vorfahr von , der in diese Richtung geht [...] Das Finden dieser Quadrate aus kann in Zeit pro Quadrat erfolgen, wenn wir jedem Quadrat in zusätzliche Zeiger die für jede Richtung auf seine nächsten Vorfahren zeigen Diese Zeiger können auch in -Zeit während des Einfügens oder Löschens eines Punkts aktualisiert werden. "log(c/ε)q2dqqO(1)2dQ0O(1)

[2]: Eppstein, D. und Goodrich, MT und Sun, JZ, „The Skip Quadtree: Eine einfache dynamische Datenstruktur für mehrdimensionale Daten“, in Proceedings of the einundzwanzigsten jährlichen Symposium über Computergeometrie, S. 296–305 , 2005.

0__
quelle
2
Es ist eine Weile her, also erinnere ich mich nicht genau, aber als ich heute Morgen das Papier noch einmal gelesen habe (sowohl die Arxiv- als auch die Journalversion), konnte ich nicht finden, wo es heißt, dass wir die Hinweise behalten, die Sie für nötig halten. Ich dachte, wir behalten nur Eltern-Kind-Zeiger und Stichprobenübergreifende Zeiger. Vielleicht könnten Sie genauer auf den Text in der Zeitung verweisen, der sagt, was Sie sagen, dass er tut.
David Eppstein
2
Hallo David, danke für den Blick. Die ANN-Suche ist der letzte Abschnitt (6). Das Problem ist in Abb. 1 dargestellt. 7 (b) was ungefähr das ist, was ich in der obigen Abbildung grafisch dargestellt habe, wenn q irgendwo unten links ist. Ich habe die Frage so bearbeitet, dass sie den bestimmten Teil des Textes aus Abschnitt 6.3 enthält. Ich habe einige Ideen, wie ich mit der Definition von Equistabbing vielleicht entspannt sein könnte, aber ich bin nicht sicher, ob ich beweisen kann, dass eine alternative Zählung nicht die angestrebte Leistung verletzt ...
0__
2
Ok, das sieht nach einem Problem aus. Ich diskutiere es mit Goodrich (wir haben den Kontakt zu Sun verloren, der die meisten Details hier gemacht hat). Unser aktuelles Gefühl ist, dass wir diese zusätzlichen Zeiger eigentlich nicht benötigen sollten (wir brauchen sie nicht für ungefähre Bereiche, warum sollten ungefähre Nachbarn anders sein, und es sollte dem Abfragealgorithmus möglich sein, sich an die Vorfahren zu erinnern, die er auf dem gesehen hat weit unten, anstatt Zeiger zu verwenden, um sie nachzuschlagen), aber wir werden uns bei Ihnen melden, wenn wir uns der Details hier etwas sicherer sind.
David Eppstein
2
Großartig, vielen Dank. Aus Gründen der Anzahl und des Layouts der Zeichen werde ich eine Antwort hinzufügen, die meine „intuitive Idee“ skizziert. Vielleicht ist dies ein Ausgangspunkt.
0__

Antworten:

11

Wie David weiß ich nicht, warum Jonathan diese Bemerkung über die 2D-Zeiger gemacht hat. Sie werden nicht benötigt. Wie David oben erwähnt hat, ist die wesentliche Eigenschaft, dass es ausreicht, sich die Geschwisterknoten (und ihre Kästchen) im Überspringquadtree zu merken, wenn wir eine Punktposition zu einem Blatt v in Q_0 machen. Wenn wir ein Feld aus P verarbeiten, erstellen wir eine Punktposition für das Blattfeld, das unserem Abfragepunkt am nächsten liegt, und fügen die Geschwisterfelder ein, wenn wir nach unten gehen. Es klingt so, als würde dies mehr oder weniger Ihrer Antwort entsprechen. Darüber hinaus ist dieses Verfahren sehr ähnlich, wie beispielsweise die ungefähre Punktposition in der folgenden Veröffentlichung beschrieben wird: Arya, Sunil und Mount, David M. und Netanyahu, Nathan S. und Silverman, Ruth und Wu, Angela Y., "Ein optimaler Algorithmus für die ungefähre Suche nach nächsten Dimensionen des nächsten Nachbarn", JACM, 1998. In der Tat,

Michael Goodrich
quelle
Das sind gute Neuigkeiten! Ich war mir einfach nicht sicher, ob das Hinzufügen der Geschwister während des Abstiegs die Grenze der Gesamtkosten für den schlimmsten Fall ändern würde oder nicht, aber ich nehme an, nein. Ich hatte in die Zeitung von Arya et al. Geschaut, fand sie aber viel weniger zugänglich als Ihre Quadtree-Zeitung :)
0__
5
Beeindruckend! Willkommen bei cstheory.SE!
Hsien-Chih Chang 16 之
5

Man kann sich Quadt Quadtree als eine Skip-List-Implementierung einer Datenstruktur vorstellen, in der die Punkte gemäß ihrer Z-Reihenfolge gespeichert sind. Es ist (wohl) zumindest konzeptionell einfacher ...

Siehe Kapitel 2 hier: http://goo.gl/pLiEO .

Und ja, vorausgesetzt, Sie können einige grundlegende Operationen der Z-Ordnung in konstanter Zeit ausführen, können Sie ANN definitiv in logarithmischer Zeit ausführen. Das oben erwähnte Kapitel zeigt auch, dass es keine Möglichkeit gibt, bizarre Operationen zu vermeiden, wenn man komprimierte Quadtrees will. Beachten Sie, dass der LCA-Betrieb nicht erforderlich ist ...

Sariel Har-Peled
quelle
3
Ja, und die deterministischen Varianten ähneln 2-3 Bäumen für dieselbe Z-Ordnung.
David Eppstein
Vielen Dank für den Link, ich habe Ihr Papier schon einmal gesehen. Auf jeden Fall konnte ich die Grenze mit dem gegebenen Algorithmus nicht empirisch verifizieren. Ich habe das Gefühl, dass der Verweis auf Lemma 7, mit dem die Anzahl der Runden in Satz 13 begrenzt wird, ungültig sein könnte, weil er einen konstanten Radius annimmt , während sich der Suchradius im ANN schrittweise ändert, und das auch Satz kritischer Quadrate. ? r
0__
Der Radius definiert sich während des Suchvorgangs. Ich bin ziemlich optimistisch, dass das Argument richtig ist.
Sariel Har-Peled
1

Ich habe auch intuitiv das Gefühl, dass man ohne diese Zeiger leben könnte, und da ich irgendwann alle Knoten auf der Festplatte beibehalten muss, ist jede Reduzierung der Zeiger großartig.

Meine Idee lautet ungefähr wie folgt: Abgesehen vom besten Kandidatenpunkt (Blatt) verfolgen wir auch den schlechtesten Abstand in jeder Runde, . Ein schlechtester Abstand wäre das Maximum der Abstände aller Ecken eines Knotens zum Abfragepunkt , unabhängig davon, ob innerhalb eines Quadrats oder außerhalb liegt.lbestrmaxdist(v,q)qvv

Eine Runde ist wie folgt: Wenn leer ist, geben Sie das , falls vorhanden. Andernfalls gibt delete-min den aktuellen in . Initialisieren Sie auf (oder setzen Sie es auf wenn noch kein bester Kandidat beobachtet wurde). Testen Sie zunächst jedes nicht leere Kind von in . Wenn dieses untergeordnete ein Blatt ist, aktualisieren Sie gegebenenfalls und . Wenn ein Knoten ist, berechnen Sie und , wobei letzterer der beste Abstand ist: Entweder Null, wennl b e s t p 0 Q 0 r m a x l b e s tp 0 Q 0 q l b e s t r m a x q d i s t ' ( q , v )Plbestp0Q0rmaxlbestp0Q0qlbestrmaxqdist(q,v)dist(q,v)v liegt innerhalb von oder dem kürzesten Abstand aller Ecken von zu .qqv

Wenn , vergiss , sonst behalte es. Wenn die Anzahl der Knoten gehalten wird , schieben diese Knoten auf . Ende der Runde.dist(q,v)>rmaxq2P

Andernfalls gehen Sie ähnlich wie bei der ursprünglichen Suche vor: Suchen Sie , den entsprechenden Knoten zu im höchstmöglichen , und beginnen Sie von dort aus: Anstatt nach einem Kind mit gleichem Abstand zum Abstieg zu fragen, testen Sie alle Kinder gemäß dem vorherigen Verfahren Überspringen Sie also diejenigen, deren bester Abstand überschreitet . Wenn nach diesem Test ein Kind übrig geblieben ist, steigen Sie darauf hin und wiederholen Sie den Vorgang. Wenn kein Kind mehr übrig ist, gehen Sie zu und wiederholen Sie den . Wenn der Test in , ist die Runde beendet.qp0QjrmaxQj1Q0

Im Moment weiß ich weder, ob dies garantiert, dass in jedem möglichen Fall der nächste Nachbar gefunden wird, noch dass es so gut funktioniert wie der ursprüngliche Algorithmus. Auch wenn die Initialisierung von ausreichend ist oder nicht. Und was sollte die Priorität in - immer noch die beste Entfernung?rmaxP


EDIT (April 2013)

Ich habe jetzt weitere Experimente mit einer Klarstellung des obigen Algorithmus durchgeführt, bei dem eine Definition von "äquipotenten" Knoten anstelle von äquistabierenden Knoten verwendet wird, basierend auf der Eigenschaft, dass der Abstieg zu einem solchen Knoten den Bereich, der von der aktuellen Abfrageform der Ausdehnung abgedeckt wird, nicht ändert .rmax

Leider kann man pathologische Fälle konstruieren (siehe Bild unten; Abfragepunkt ist unten in der Mitte), in denen sich die Leistung auf Runden verschlechtert .O(n)

Geben Sie hier die Bildbeschreibung ein

0__
quelle
0

Ich habe jetzt den auf Equistabbing basierenden Algorithmus implementiert, bei dem die Vorfahren der niedrigsten Geschwister mit Brute-Force durchsucht werden (bevor versucht wird, eine O (1) -Variante zu finden), um die maximale Anzahl der in Satz 13: beanspruchten Runden) zu überprüfen .O(ϵ1d(logn+logϵ1))

Ich verwende das "pathologische" Beispiel aus meiner vorherigen Antwort. Das zweidimensionale Wurzelquadrat hat eine Seitenlänge von 512, wobei die Mittelkoordinate (256, 256) ist. Koordinaten werden in ganzen Zahlen angegeben, was zu einem direkten . Die Punkte sind gleichmäßig horizontal über dem Wurzelquadrat verteilt, und der Abfragepunkt liegt bei (256, 511) (beachten Sie, dass 512 bereits außerhalb des Wurzelquadrats liegt).vϵ=1v

In der folgenden Abbildung ist der vollständige Baum dargestellt, und die Anzahl der Punkte in diesem Beispiel beträgt 16. Die blauen quadratischen Umrisse geben die interessanten Quadrate an, die in die Prioritätswarteschlange verschoben werden, und die Ziffern in ihrer Mitte geben die runde Zahl in an was sie geschoben werden. Entdeckte Blattpunkte sind auch mit der runden Nummer gekennzeichnet, in der sie berücksichtigt werden. Die drei transparenten blauen Kreise geben den bekannten NN-Radius nach der 1., 2. und 7. Runde an (der nächste Nachbar wird zuerst in der 7. Runde gesehen). Insgesamt gibt es 12 Runden (die letzten 6 nur Pop-Quadrate aus der Warteschlange, aber keine neuen Quadrate hinzufügen).Q0

Ich habe dieses Beispiel mit einer Reihe von immer größeren Wurzelquadraten und einer Anzahl von Punkten ausgeführt, wobei der Abstand der Punkte gleich blieb (32). Dies bestätigte, was aus der Abbildung bereits intuitiv ersichtlich ist: Der Algorithmus benötigt -Runden, während Satz 13 mit und besagt, dass nur -Runden benötigt würden.d=2ϵ=1O(logn)O(n)d=2ϵ=1O(logn)

Wenn mir also nichts Entscheidendes fehlt, kann der Algorithmus die angegebene Geschwindigkeit nicht erreichen. Irgendwelche Kommentare oder Ideen?

Durchquerung

0__
quelle