Impossible de trouver du papier: Tous les K des voisins les plus proches recherchent dans n * log (n) en utilisant des indices de distance pour les points de support du journal (n)

Question

Je me souviens avoir lu un article sur la recherche de K voisins les plus proches pour tous les n objets multidimensionnels de l'ensemble.

J'essaie de le retrouver plusieurs fois, mais j'ai échoué jusqu'à présent.

L'algorithme était le suivant:

1. Chaque objet se voit attribuer une file d'attente triée de voisins narrés (la taille maximale est k). Supposons que $ k <log (n) $
2. Chaque fois que vous calculez $ Distance (A, B) $, essayez d'ajouter une liste de voisins de B et de vise versa.
3. Choisissez $ log (n) $ Support les objets (disons, d'abord $ log (n) $ objets sur $ n $). (Ou peut-être que c'était $ sqrt (n) $)
4. Pour chaque support, créez l'index basé sur la distance contenant tous les n objets
5. Après la construction d'index, chaque objet a une liste de candidats de K voisins les plus proches. Tous les vrais voisins les plus proches ne sont pas plus loin que le voisin le plus éloigné de la liste des candidats - Radius du voisin candidat.
6. Pour chaque point, nous utilisons l'inégalité du triangle et le rayon actuel du voisin pour contraindre les distances entre un point candidate et les points de support: $ | dist (candidat_i, support_j) - dist (point, support_j) | <= rayon $. Nous extrassons efficacement les candidats qui tombent dans des gammes basées sur le rayon pour tous les points de soutien.
7. Nous calculons les distances de ces candidats et mettons à jour les listes de voisinage les plus proches pour le point actuel et les points candidats.
8. Au fur et à mesure que nous traitons plus de points, les listes de voisins deviennent «plus serrées» - le rayon, la distance du voisin le plus éloigné diminue avec chaque mise à jour de la liste.
9. Des contraintes plus strictes signifient que les listes des candidats deviennent de plus en plus petites après chaque point traité et conduisant à un temps d'exécution total de $ n * log (n) $.

Alors, pourquoi ai-je à nouveau besoin du papier? Tout d'abord, plusieurs personnes m'ont demandé et j'ai été surpris de ne pas le retrouver. Plus important encore, cela ne fonctionnait pas bien pour moi. Cela pourrait être causé par un mauvais choix des objets de support. Je ne me souviens rien du processus de sélection.