Algorithmus für 2D Nearest-Neighbour-Abfragen mit dynamischen Punkten

Question

Ich versuche, einen schnellen Algorithmus zum Auffinden der (näherungsweise, wenn nötig) nächsten Nachbarn eines gegebenen Punktes in einem zweidimensionalen Raum zu finden, wo Punkte häufig aus dem entfernt werden Datensatz und neue Punkte werden hinzugefügt.

(Im Zusammenhang damit gibt es zwei Varianten dieses Problem, die mich interessieren:., In dem Punkte können als gedacht werden hinzugefügt und zufällig entfernt und eine andere, in der alle Punkte sind in ständiger Bewegung)

Some Gedanken:

• kd-Bäume eine gute Leistung bieten, sondern nur für den statischen Punkt Sets
• R * -Bäume scheinen gute Leistung für eine Vielzahl von Dimensionen, aber die Allgemeinheit ihrer Konstruktion (beliebige Dimensionen anbieten , allgemeine Inhaltsgeometrien) schlägt die Möglichkeit vor, dass ein mo re spezifischen Algorithmus könnte Leistungsvorteile
• Algorithmen mit bestehenden Implementierungen bevorzugt anbieten (obwohl dies nicht notwendig ist)

Was ist eine gute Wahl, denn hier?

Answer 1

Überprüfen Sie die Bkd-Tree, das ist:

ein I/O-effiziente dynamische Datenstruktur basierend auf dem kd-Baum. [..] der Bkd-Baum behält seine hohe Raumauslastung und ausgezeichnete Abfrage und Update-Performance unabhängig von der Anzahl der durchgeführten Updates.

Diese Datenstruktur ist jedoch multidimensional und nicht auf niedrigere Dimensionen (wie den kd-Baum) spezialisiert.

Spielen Sie mit ihm in bkdtree.

---

Dynamic Quadtrees kann auch ein Kandidat, mit O (logn) Abfragezeit und O (Q (n)) Einfügen/Löschen Zeit sein, wobei Q (n) die Zeit ist, eine Abfrage in der Daten durchzuführen, Struktur verwendet. Beachten Sie, dass diese Datenstruktur auf 2D spezialisiert ist. Für 3D hingegen haben wir Octrees, und in ähnlicher Weise kann die Struktur für höhere Dimensionen verallgemeinert werden.

Eine Implementierung ist QuadTree.

---

R*-tree ist eine andere Wahl, aber ich stimme mit Ihnen auf der Allgemeinheit. Eine r-star-tree Implementierungen existiert auch.

---

A Cover tree könnte auch in Betracht gezogen werden, aber ich bin nicht sicher, ob es Ihre Beschreibung passt. Lesen Sie mehr here, und überprüfen Sie die Implementierung auf CoverTree.

---

Kd-tree noch in Betracht gezogen werden sollte, da es auf zwei Dimensionen bemerkenswerte Leistung ist ist, und seine Einführung Komplexität ist logarithic groß.

nanoflann und CGAL sind nur zwei Implementierungen davon, wobei die erste keine Installation erfordert und die zweite, aber möglicherweise leistungsfähiger ist.

---

Auf jeden Fall würde ich mehr als einen Ansatz und Benchmark versuchen (da sie alle Implementierungen haben und diese Datenstrukturen in der Regel durch die Art der Ihre Daten betroffen sind).

Answer 2

Ich stimme mit (fast) alles, was @gsamaras sagte, nur ein paar Dinge hinzufügen:

• Nach meiner Erfahrung (mit großer Datenmenge mit> = 500.000 Punkten), kNN-Leistung von KD-Bäumen ist um einen Faktor von 10 bis 100 schlechter als jeder andere räumliche Index. Ich habe sie (2 KD-Bäume und verschiedene andere Indizes) an einem großen OpenStreetMap-Datensatz getestet. Im folgenden Diagramm werden die KD-Bäume KDL und KDS genannt, der 2D-Datensatz heißt OSM-P (linkes Diagramm): Das Diagramm wurde von this document übernommen, weitere Informationen finden Sie in den folgenden Aufzählungspunkten.
• This research beschreibt eine Indizierungsmethode zum Verschieben von Objekten, falls Sie die gleichen Punkte in leicht unterschiedlichen Positionen (wieder) einfügen.
• Quadtrees sind auch nicht schlecht, sie können sehr schnell in 2D sein, mit ausgezeichneter kNN-Performance für Datensätze < 1.000.000 Einträge. Wenn Sie nach Java-Implementierungen suchen, sehen Sie sich meine index library an. In hat Implementierungen von Quadtrees, R-Stern-Baum, Ph-Baum und andere, alle mit einer gemeinsamen API, die auch kNN unterstützt. Die Bibliothek wurde für die TinSpin geschrieben, die ein Framework zum Testen mehrdimensionaler Indizes ist. Einige Ergebnisse finden Sie enter link description here (es beschreibt nicht wirklich die Testdaten, aber 'OSM-P' Ergebnisse basieren auf OpenStreetMap-Daten mit bis zu 50.000.000 2D-Punkten.
• Abhängig von Ihrem Szenario, möchten Sie vielleicht auch in Betracht ziehen .Sie scheinen für kNN-Abfragen langsamer als R * -Tree in niedriger Dimensionalität (obwohl immer noch schneller als KD-Trees), aber sie sind schneller für die Entfernung und Updates als R * Trees. Wenn Sie eine große Entfernung haben/Insertion, kann dies eine bessere Wahl sein (siehe die TinSpin results, Figuren 2 und 46). ein C++ Version verfügbar ist enter link description here.