Nearest Neighbour Problem

[DocEW]

Hallo,

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?

Bin für jeden Tipp dankbar,

DocEW

[ScottManDeath]

Riecht das nach LVQ?

k-d Trees sollten helfen, ich hab aber keine praktische Erfahrungen damit.

[DocEW]

LVQ war mir bisher noch gar nicht bekannt. Ich habe gerade mal ein bißchen gelesen, und das ganze dient ja anscheinend der Clusterung wenn ich das richtig verstanden habe. Ich bin mir nicht sicher, ob das viel helfen würde. Für die Punkte in der Mitte des Clusters wäre es zwar sinnvoll, die NN im Cluster zu suchen, aber zum Rand hin wäre das dann schon ab dem vielleicht 10. oder 20. NN nicht mehr richtig.
Trotzdem danke! :)

[micki]

naja, ich denke mir der 2d baum wird wohl schon ein KD-Tree sein und das ist eigentlich das optimalste (*athsärger*) was man beim nearest neighbour machen kann.

was man dabei optimieren kann, ist das allignment und den aufbau des baumes.
1. das allignment sowie die größe des 2d Tress sollte möglichst so sein, dass es zum einen in den cache passt (am besten 1LVL). zum anderen kann man das versuchen so zu gestallten, dass immer der "linke" teilbaum gleich im anschluss an das aktuelle objekt im speicher liegt, durch sowas hab ich schon öfter ein paar prozent rausgehollt.
2. das aufbauen des baumes hat ja zwei probleme, das große ist die art der partitionierung und das kleine ist welchen teil man als "linke" hälfte und welchen als "rechte" hälfte wählt.
das erst problem lässt sich zum einen trivial lösen, indem man immer die größte achse der spaceextend nimmt und dort das mittigste element. wenn man jedoch zeit hat zum vorberechnen des baumes bzw es "offline" machen kann, lohnt es sich einen "usagecounter" für die nodes zu machen, sodass man bei einem starken übergewicht einer seite irgendwo im baum, noch einiges umhängen kann, bis man nach mehreren iterationen vielleicht einen gut balancierten baum hat. zum anderen kann man versuchen eine leichte übergewichtung auf der "linken" seite zu erzwingen, sodass diese seite öfter durchlaufen wird, das hat den vorteil, dass zum einen die linke seite, weil sie ja an das aktuelle objekt alligned ist, schon im cache liegt und zum anderen wird die branchprediction der cpu vielleicht mehr treffer landen, da sie bei einem perfekt balanced tree leider den worstcase hat bei random zugriffen.

MfG
micki

btw. hier meinte ich mit allignment die art der anreihung der objekte, nicht das padding. jedes objekt im speicher sollte am besten natürlich 4,8,16,32 oder 64byte groß sein und an einer speichergrenze die modulo 0 dazu ist liegen.

[DocEW]

Hi micki,

danke für die vielen Tips! Mit der Balancierung des Baums usw. habe ich schon rumgespielt und etwas rausgeholt, war aber nicht viel. An so low-level Sachen werde ich mich nicht ranbegeben denke ich, da es mir mehr darum ging, ob man es von der eigentlichen Datenstruktur noch prinzipiell verbessern kann.
Meinst du denn, daß die Cache-Tipps bei so einem großen Baum was helfen..? Vielleicht sollte ich das ganze in z.B. 4 kleinere kd-trees aufteilen..?

[micki]

danke für die vielen Tips! Mit der Balancierung des Baums usw. habe ich schon rumgespielt und etwas rausgeholt, war aber nicht viel. An so low-level Sachen werde ich mich nicht ranbegeben denke ich, da es mir mehr darum ging, ob man es von der eigentlichen Datenstruktur noch prinzipiell verbessern kann.
eine wichtige verbesserung ist, wenn sie an 16,32 oder 64 byte addressen anliegen. und wenn du weißt, wie hoch die anzahl der elemente ist, nicht jedes einzeln per new allokieren, sondern ein array anlegen und nach der reihe verwenden, falls du keinen default c-tor hast, dann notfalls mit inplacement new.


Meinst du denn, daß die Cache-Tipps bei so einem großen Baum was helfen..? Vielleicht sollte ich das ganze in z.B. 4 kleinere kd-trees aufteilen..?
in der theorie macht es keinen sinn den KD-tree in mehrere trees zu unterteilen, weil jedes child eines kd-trees ja selber schon ein kd-tree ist. ginge es auch nur um die suche nach einer zelle, wäre das zwar möglich, aber nutzlos. bei der suche nach dem nearest neighbour würden hingegen mehrere trees eventuell schaden, da du ja erst nach unten durchstepst und dann wieder hoch (jedenfalls läuft das bei mir so wenn ich für das problem mein KDTree nutze).


zum cache:
naja, kommt auf die größe der einzelnen objekte an. ich hab bei meinem raytracer und meinem collisionsystem bis ca 10^6 triangles und mein KD-Tree (der aus axis alligned planes besteht) hat aber viel weniger elemente, weil ich immer versuche mehrere triangles (bis4) zu clustern, so hab ich zum einen einen sehr speichereffizienten KD-Tree (16byte pro node, und nur n/4elementeprocluster/2clusterproSplittingplane, bei n=10^6 also ca 2MB und bei n=10^5 nur 200kb, was im 2lvl cache der meisten cpus sein sollte) und zum anderen ist die sache dank 4elements pro cluster SSE fähig.
die frage ist nur, ob sich das bei dir lohnt den baum und die punkte seperat zu handhaben.

kannst du nicht ein wenig mehr sagen über z.b. den wertebereich der punkte sagen und z.b. wie oft ändert sich die punktmenge, und ist jeder query unique oder ist der query immer mit den selben punkten die nur leicht ihre position verändert haben? dafür wäre z.b. sweep&prune eventuell anwendbar, das hätte im gegensatz zu KD-Trees die O(n log n) haben sollten, eine laufzeit von O(n ).

MfG
micki

[DocEW]

(...) bei n=10^6 also ca 2MB und bei n=10^5 nur 200kb, was im 2lvl cache der meisten cpus sein sollte (...)
Oh. Also das ganze ist bei mir Teil eines relativ komplexen Greedy-Algorithmus für das Facility Location Problem, so dass die Objekte (="Punkte") auch sehr fett sind. Vielleicht sollte ich darüber nachdenken für den kd-Tree extra abgespeckte Versionen zu erstellen...

kannst du nicht ein wenig mehr sagen über z.b. den wertebereich der punkte sagen und z.b. wie oft ändert sich die punktmenge, und ist jeder query unique oder ist der query immer mit den selben punkten die nur leicht ihre position verändert haben?
Der Wertebereich der Punkte ist generell offen, liegt aber bei den Problemen an denen ich getestet habe immer zwischen 0 und 1000000, wobei anscheinend 10er Schritte benutzt werden. Also quasi 0 bis 100000. Die Punktemenge bleibt die ganze Zeit gleich (=Elemente eines Chips). Die Queryreihenfolge sieht generell so aus, daß die Entfernung eines NN die Reihenfolgeposition festlegt. Also zum Beispiel so:

1.) 1. NN zum Punkt x (Entfernung 10)
2.) 1. NN zum Punkt y (Entfernung 11)
3.) 2. NN zum Punkt y (Entfernung 14)
4.) 1. NN zum Punkt z (Entfernung 15)
5.) 2. NN zum Punkt x (Entfernung 21)

usw.

Viele Grüße,

DocEW