Déclaration de problème:
J'ai le problème suivant:
Il y a plus d'un milliard de points dans l'espace 3D. L'objectif est de trouver le plus grand nombre de voisins au sein de la distance donnée à distance R. Une autre condition est que la distance entre deux points de ces points Top N doit être supérieure à celle de R. La distribution de ces points ne sont pas uniformes. Il est très courant que certaines régions de l'espace contiennent beaucoup de points.
5 Réponses :
Je n'ai pas de réponse définitive pour vous, mais j'ai une suggestion pour une approche pouvant donner une solution.
Je pense que cela vaut la peine d'enquêter hachage sensible à la localité . Je pense que diviser les points de manière uniforme puis appliquer ce type de LSH à chaque ensemble devrait être facilement parallèle. Si vous concevez votre algorithme de hachage de telle sorte que la taille du godet soit définie en termes de Après avoir effectué cela localement, vous pouvez peut-être appliquer une stratégie de style de la carte pour combiner des godets spatiaux de différentes pistes parallèles de l'algorithme de LSH de manière peu sale, en utilisant le fait que vous pouvez commencer à Exclure les parties de votre espace problématique en réduisant des godets entiers. Évidemment, vous devrez faire attention aux cas de bords qui couvrent différents seaux, mais je soupçonne qu'à chaque étape de la fusion, vous pouvez appliquer différents tailles / compensations de seau de sorte que vous supprimez cet effet (par exemple, effectuer la fusion de seaux équivalents spatialement. comme des seaux adjacents). Je crois que cette méthode pourrait être utilisée pour garder les exigences de mémoire petit (c'est-à-dire que vous n'avez pas besoin de stocker beaucoup plus que les points eux-mêmes à un moment donné, et vous opérez toujours sur de petits sous-ensembles (ish)).
Si vous recherchez une sorte de heuristique, je pense que ce résultat donnera immédiatement quelque chose qui ressemble à une "bonne" solution - c'est-à-dire qui vous donnera un petit nombre de points probables que vous pouvez vérifier satisfaire vos critères. Si vous recherchez une réponse exacte, vous devrez alors appliquer d'autres méthodes pour couper l'espace de recherche lorsque vous commencez à fusionner des godets parallèles.
Une autre pensée que j'avais eu était que cela pourrait se rapporter à la recherche du métrique k -center . Ce n'est certainement pas exactement le même problème, mais peut-être certaines des méthodes utilisées dans la résolution applicable dans ce cas. Le problème est que cela suppose que vous avez un espace métrique dans lequel calculer la mesure de distance est possible - Dans votre cas, toutefois, la présence d'un milliard de points le rend indésirable et difficile à effectuer tout type de traversé global (par exemple, tri des distances entre points). Comme je l'ai dit, juste une pensée, et peut-être une source d'inspiration supplémentaire. R , il semble probable que, pour un ensemble de points donné divisé en seaux, les points satisfaisant de vos critères sont susceptibles d'exister dans le les godets plus complètes.
C'est vraiment très similaire au problème de la couverture maximale. La fonction d'objet est différente. L'objet ici est de minimiser: somme (((CT / K) ^ 2), i = 1, .. k, où k est le numéro de la partition, CI est le nombre de points dans le jeu I et CT est le nombre de points Nombre total de points.
CI n'est pas exactement la variable que nous voulons optimiser. Mais il devrait être assez proche. Idéalement, CI devrait également inclure le nombre de points dans ses cellules voisines les plus proches de la surface. Étant donné que la taille de la cellule est R, si le calcul de la distance n'a besoin que de prolonger sa cellule voisine la plus proche.
Une idée que j'ai à l'esprit maintenant est que la création de cellules LXMXN (longueur pour chaque cellule est R). Le nombre de points peut être facilement enregistré pour chaque cellule. Puis un algorithme de cluster peut être utilisé pour trouver les grappes denses. Comme il y a beaucoup trop de points, il est infaisable d'effectuer l'algorithme de clustering pour un point individuel. Cependant, nous pouvons réduire la résolution des comptes dans la cellule LXMXN en divisant les comptes par un nombre arbitraire. Par exemple, CT / (LMN). Et puis l'algorithme gourmand peut être utilisé pour faire la partition. Je ne sais pas si c'est sur la bonne voie.
Je ne suis pas tout à fait sûr de ce que ces deux premiers commentaires faisaient référence à. Cependant, la dernière approche que vous avez décrite est essentiellement exactement ce que je suggérais - une sorte de division spatiale (par exemple de LSH) qui vous permet de compter des points dans des godets pour localiser des solutions plausibles que vous pouvez vérifier (aussi, si votre taille de godet est dans Les termes de r, alors vous pouvez réellement commencer à faire des mesures de distance normales sur des points dans le godet actuel et les godets adjacents).
Les deux premiers commentaires sont liés à la partition des données après les placer dans la grille.
Voici quelques parties possibles d'une solution. Il y a divers choix à chaque étape, qui dépendra de NCluster, sur la rapidité avec laquelle les données changent, et sur ce que vous voulez faire avec les moyens.
3 étapes: quantifier, boîte, k-moyens.
1) Quantifier: Réduisez les coordonnées XYZ d'entrée pour dire 8 bits chacun,
En prenant 2 ^ 8 pour centiles de x, y, z séparément.
Cela accélérera tout le flux sans perte de détail.
Vous pouvez trier tous les points 1G, ou juste un 1m aléatoire,
Pour obtenir 8 bits x0 Ajouté: arbres KD
Split n'importe quel nuage de points dans des boîtes de taille différente, chacune avec ~ points de feuilles -
beaucoup mieux que de diviser x y z comme ci-dessus.
Mais afaik, vous devriez rouler votre propre code d'arbre KD
Pour ne diviser que les premières cases de 16 m 16 m et garder les comptes que, pas les points.
2) Box: Comptez le nombre de points dans chaque boîte 3D,
[XJ .. XJ + 1, YJ .. YJ + 1, ZJ .. ZJ + 1].
La boîte moyenne disposera de 2 ^ (30-3 * 8);
La distribution dépendra de la manière dont les données sont clommées.
Si certaines cases sont trop grosses ou si vous obtenez trop de points, vous pourriez
a) diviser en 8,
b) suivre le centre des points dans chaque case,
autre tout simplement prendre des centres de milieu de la boîte.
3)
K-olth regroupement
sur les centres de boîte 2 ^ (3 * 8).
(Google parallèle "k signifie" -> 121k hits.)
Cela dépend fortement sur K aka ncluster, également sur votre rayon R.
Une approche approche serait de développer un
tas
des boîtes SOIT 27 * NCluster avec le plus de points,
Ensuite, prenez les plus gros sujets à votre contrainte de rayon.
(J'aime commencer par un
Spanning Tree ,
Ensuite, supprimez les liens les plus longs de la K-1 pour obtenir des clusters K.)
Voir également
Quantitation couleur .
Je ferais du nbit, ici 8, un paramètre du début.
Quel est votre nCluster?
ajouté: si vos points bougent à temps, voir
Détection de collision-de-grand nombre de cercles sur Donc.
juste une idée. Créez un graphique avec des points et des bords donnés entre les points lorsque la distance Création de ce type de graphique est similaire à la décomposition spatiale. Vos questions peuvent être répondues avec la recherche locale dans le graphique. Les premiers sont des sommets avec un degré maximum, la seconde est la recherche d'un ensemble maximal non connecté de sommets maximaux.
Je pense que la création de graphique et de recherche peut être faite parallèle. Cette approche peut avoir une grande nécessité de mémoire. Domaine de scission et fonctionnement avec des graphiques pour plus de volumes peuvent réduire les besoins de la mémoire.
Utilisez un Beaucoup de méthodes susmentionnées telles que Localité Sensible Hasphe sont des versions approximatives conçues pour une dimensionnalité plus haut plus élevée où vous ne pouvez plus diviser sensiblement.
fractionnement à chaque niveau en 8 bacs (2 ^ d pour D = 3) fonctionne très bien. Et puisque vous pouvez vous arrêter quand il y a trop de points dans une cellule et construisez un arbre plus profond où il y a beaucoup de points qui doivent bien répondre à vos besoins.
Pour plus de détails, voir Wikipedia:
https://fr.wikipedia.org/wiki/octree
Alternativement, vous pouvez essayer de construire un arbre R. Mais l'arbre R tente d'équilibrer, ce qui rend plus difficile de trouver les zones les plus denses. Pour votre tâche particulière, ceci inconvénient de l'octree est réellement utile! Le R-Tree met beaucoup d'efforts à maintenir la profondeur de l'arbre égale partout, de sorte que chaque point puisse être trouvé à peu près au même moment. Cependant, vous n'êtes pas intéressé par les zones denses, qui se trouveront sur les chemins les plus longs de l'octree sans même avoir à regarder les points actuels!
Je suggérerais également d'utiliser un octree. Le Octomap framework est très bon pour traiter d'énormes nuages de points 3D. Il ne stocke pas tous les points directement, mais met à jour la densité d'occupation de chaque noeud (Boîte 3D AKA). Une fois l'arborescence construite, vous pouvez utiliser un itérateur simple pour trouver le nœud avec la densité la plus élevée. Si vous souhaitez modéliser la densité de points ou la distribution à l'intérieur des nœuds, l'Octomap est très facile à adopter.
ici vous pouvez voir comment c'était étendu pour modéliser la distribution des points à l'aide d'un modèle planar.
Cela ressemble à la variante 3D du problème de couverture de 3-D !! :-)
Votre problème me rappelle "quantification de vecteur" qui peut vous donner quelques idées: Data-Compprimer.com/ vq.shtml . Au regard du regard, le problème ne devrait pas être difficile à résoudre si vous supprimez cette restriction "La distance entre deux points de ces points supérieurs n doit être supérieure à R" - Cette restriction cause un problème majeur, et nécessitera beaucoup de penser à la surmonter.