Choix approprié de la structure de données et de l'algorithme pour la recherche rapide de voisin-k le plus proche en 2D

Question

J'ai un ensemble de données d'environ 100 000 paires (X, Y) représentant des points dans l'espace 2D. Pour chaque point, je veux trouver ses k-plus proches voisins. Donc, ma question est - quelle structure de données/algorithme serait un choix approprié, en supposant que je veux absolument minimiser le temps de fonctionnement global? Je ne cherche pas de code - juste un pointeur vers une approche appropriée. Je suis un peu découragé par la gamme de choix qui semblent pertinents - les arbres quadruples, les arbres R, les arbres kd, etc.

Je pense que la meilleure approche est de construire une structure de données, puis de lancer type de recherche k-plus proche voisin pour chaque point. Cependant, puisque (a) je connais les points à l'avance, et (b) je sais que je dois exécuter la recherche de chaque point exactement une fois, peut-être qu'il y a une meilleure approche?

Quelques détails supplémentaires:

• Comme je veux minimiser toute la durée de la course, je ne se soucient pas si la majorité du temps est consacré à la structure vs recherche.
• Les paires (X, Y) sont assez bien étalées, donc nous pouvons supposer une distribution presque uniforme.

Answer 1

Si k est relativement faible (< 20 environ) et vous avez une distribution à peu près uniforme, créer une grille qui recouvre la plage où les points tombent, choisis de façon que le nombre moyen de points par grille est sensiblement plus élevé que k (de sorte qu'un point situé au centre obtiendra généralement ses k voisins dans ce point de grille). Ensuite, créez un ensemble d'autres grilles à moitié séparées du premier (chevauchement) le long de chaque axe. Maintenant, pour chaque point, calculez l'élément de grille dans lequel il tombe (puisque les grilles sont régulières, aucune recherche n'est nécessaire) et choisissez l'une des quatre (ou plusieurs grilles qui se chevauchent) qui a ce point le plus proche de son centre.

Dans chaque élément de grille, les points doivent être triés dans une coordonnée (disons x). En partant de l'élément que vous avez choisi (trouvez-le en utilisant la bissection), sortez de la liste triée jusqu'à ce que vous ayez trouvé k items (encore une fois, si k est petit, la méthode la plus rapide , en laissant la pire correspondance tomber à la fin lorsque vous insérez, le tri par insertion bat généralement tout le reste jusqu'à environ 30 éléments sur le matériel moderne). Continuez jusqu'à ce que votre plus proche voisin le plus proche soit plus proche de vous que les points suivants de x (ie sans compter leur décalage y, donc il ne pourrait y avoir aucun nouveau point qui pourrait être plus proche que le kième plus proche trouvé) . Si vous n'avez pas encore k points, ou si vous avez k points mais qu'un ou plusieurs murs de l'élément de grille sont plus proches de votre point d'intérêt que le plus éloigné des points k, ajoutez les éléments de grille adjacents dans le chercher.

Cela devrait vous donner des performances de quelque chose comme O(N*k^2), avec un facteur constant relativement faible. Si k est grand, alors cette stratégie est trop simpliste et vous devez choisir un algorithme linéaire ou log-linéaire en k, comme peut l'être kd-trees.