ich habe für folgendes Problem eine Lösung überlegt und möchte gerne wissen, ob es nicht noch irgendwie besser geht.
Ich habe eine große Menge von Punkten (ca. 10^5 - 10^6) und benötige nach und nach die nearest neighbours von den Punkten. Ich bezeichne das jetzt mal Englisch, damit es gleich nicht verwirrend wird.
Also zunächst brauche ich den nearest neighbour von irgendeinem Punkt, dann von einem anderen und so weiter. Irgendwann brauche ich dann evtl. auch den „nächsten“ nearest neighbour (also den, der am 2. nächsten dran ist) usw…
Ich kann vorher nicht sagen, wie viele ich brauche (also nicht k-nearest neighbours) und auch nicht wann. Es sind auch zu viele Punkte um für alle Punkte alle NN auszurechnen.
Ich löse das ganze momentan durch Suche in einem 2D-Tree. Dabei wird der letzte nearest neighbour als Schranke genutzt, um beim Suchen unnötige Teilbäume zu sparen. Ist schon nicht schlecht denke ich, aber diese ganze Sucherei nimmt ungefähr 30% der Gesamtlaufzeit ein, so daß sich Verbesserungen da noch richtig lohnen könnten.
Es gibt ja z.B. Voronoi-Diagramme, um die nearest neighbours schnell zu finden. Kann man damit auch die jeweils nächsten nearest neighbours finden?
ich habe für folgendes Problem eine Lösung überlegt und möchte
gerne wissen, ob es nicht noch irgendwie besser geht.
Schau’n mer mal, wie der Hesse so sagt
Ich habe eine große Menge von Punkten (ca. 10^5 - 10^6) und
benötige nach und nach die nearest neighbours von den Punkten.
Ich bezeichne das jetzt mal Englisch, damit es gleich nicht
verwirrend wird.
Also zunächst brauche ich den nearest neighbour von
irgendeinem Punkt, dann von einem anderen und so weiter.
Irgendwann brauche ich dann evtl. auch den „nächsten“ nearest
neighbour (also den, der am 2. nächsten dran ist) usw…
Ich kann vorher nicht sagen, wie viele ich brauche (also nicht
k-nearest neighbours) und auch nicht wann. Es sind auch zu
viele Punkte um für alle Punkte alle NN auszurechnen.
Es gibt ja z.B. Voronoi-Diagramme, um die nearest neighbours
schnell zu finden. Kann man damit auch die jeweils nächsten
nearest neighbours finden?
Spontan würde ich vorschlagen, einen der polylogarithmischen dynamischen nearest Neighbor-Algorithmen
zu nehmen (siehe z.B. http://citeseer.ist.psu.edu/167339.html) und um den
zweitnächsten Punkt zu berechnen den nächsten einfach vorübergehend zu entfernen
(entsprechend um den k’t nächsten zu finden die k-1 anderen löschen und nach dem
Finden wieder einfügen). Je nach Anwendung kannst Du ja evtl. sogar auf das Wiedereinfügen verzichten oder der Algorithmus läßt sich so modifizieren, daß
man das Löschen gar nicht explizit vornehmen muß.
Ja, Voronoi-Diagramme sind der korrekte Ansatz:
Das „normale“ Voronoi-Diagramm erster Ordnung läßt sich in Zeit O(n*log(n)) konstruieren.
Zu prüfen sind dann jeweils nur die Nachbarpunkte, deren Voronoiregion eine gemeinsame Kante zu der Region des aktuellen Punktes haben.
Um „k-nearest neighbours“ zu finden, wird ein Voronoi-Diagramm k-ter Ordnung benötigt.
ich habe für folgendes Problem eine Lösung überlegt und möchte
gerne wissen, ob es nicht noch irgendwie besser geht.
Ich habe eine große Menge von Punkten (ca. 10^5 - 10^6) und
benötige nach und nach die nearest neighbours von den Punkten.
Ich bezeichne das jetzt mal Englisch, damit es gleich nicht
verwirrend wird.
Also zunächst brauche ich den nearest neighbour von
irgendeinem Punkt, dann von einem anderen und so weiter.
Irgendwann brauche ich dann evtl. auch den „nächsten“ nearest
neighbour (also den, der am 2. nächsten dran ist) usw…
Ich kann vorher nicht sagen, wie viele ich brauche (also nicht
k-nearest neighbours) und auch nicht wann. Es sind auch zu
viele Punkte um für alle Punkte alle NN auszurechnen.
Ich löse das ganze momentan durch Suche in einem 2D-Tree.
Dabei wird der letzte nearest neighbour als Schranke genutzt,
um beim Suchen unnötige Teilbäume zu sparen. Ist schon nicht
schlecht denke ich, aber diese ganze Sucherei nimmt ungefähr
30% der Gesamtlaufzeit ein, so daß sich Verbesserungen da noch
richtig lohnen könnten.
Es gibt ja z.B. Voronoi-Diagramme, um die nearest neighbours
schnell zu finden. Kann man damit auch die jeweils nächsten
nearest neighbours finden?