Comment trouver les plus proches 2 points dans un espace de 100 dimensions avec 500.000 points?

Question

J'ai une base de données avec 500.000 points dans un espace de 100 dimensions, et je veux trouver les plus proches de 2 points. Comment puis-je faire?

Mise à jour: L'espace est euclidien, Désolé. Et merci pour toutes les réponses. BTW ce n'est pas devoirs.

Answer 1

Vous pouvez essayer bibliothèque ANN , mais cela ne donne que des résultats fiables jusqu'à 20 dimensions.

Answer 2

Il y a un chapitre Introduction aux algorithmes consacré à la recherche de deux points les plus proches dans l'espace à deux dimensions en O (n * log n) fois. Vous pouvez le vérifier sur Google Livres . En fait, je suggère pour tout le monde que la façon dont ils appliquent la technique de diviser pour mieux régner à ce problème est très simple, élégant et impressionnant.

Bien qu'il ne peut pas être étendu directement à votre problème (comme 7 constant serait remplacé par 2^101 - 1), il devrait être très bien pour la plupart des ensembles de données. Donc, si vous avez entrée raisonnablement aléatoire, il vous donnera la complexité O(n*logn*m) où n est le nombre de points et m est le nombre de dimensions.

modifier C'est tout ce que vous avez en supposant l'espace euclidien. À savoir, la longueur du vecteur v est sqrt(v0^2 + v1^2 + v2^2 + ...). Si vous pouvez choisir métrique, cependant, il pourrait y avoir d'autres options pour optimiser l'algorithme.

Answer 3

Utilisez un arbre kd. Vous êtes à la recherche à un problème voisin le plus proche et il y a des structures de données hautement optimisées pour le traitement de cette classe exacte des problèmes.

http://en.wikipedia.org/wiki/Kd-tree

P.S. problème Fun!

Answer 4

Exécuter PCA vos données à des vecteurs de convertir de 100 dimensions dire 20 dimensions. Ensuite, créez un K-arbre le plus proche Neighbor (KD-Tree) et d'obtenir les plus proches voisins 2 en fonction de la distance euclidienne.

En général, si non. de dimensions sont très grandes, alors vous devez soit faire une approche de force brute (+ parallèle distribué / carte réduire) ou une approche basée sur le regroupement.

Answer 5

Utilisez la structure de données appelée un arbre kd. Vous aurez besoin d'allouer beaucoup de mémoire, mais vous découvrirez peut-être une optimisation ou deux le long du chemin en fonction de vos données.

http://en.wikipedia.org/wiki/Kd-tree .

Mon ami travaille sur sa thèse il y a quelques années Phd quand il a rencontré un problème similaire. Son travail était de l'ordre de 1M points sur 10 dimensions. Nous avons construit une bibliothèque kd-arbre pour le résoudre. Nous pouvons être en mesure de creuser-le code si vous souhaitez nous contacter hors ligne.

Voici son article publié: http://www.elec.qmul.ac.uk /people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf