Recherche des proches voisins en utilisant la hierarchie
Le but de ce module est de récupérer toutes les personnes qui sont plus proches qu'une distance donnée d. L'algorithme glouton consisterait à calculer les distances entre cette personne et toutes les autres, puis de récupérer celles qui sont voisines. En pratique, il y a beaucoup trop de personnes, et l'on va donc se servir de la hierarchie pour ne calculer les distances que pour certaines personnes.
On recherche les voisins à partir du haut de la hierarchie (Monde) en ne descendant la recherche que dans les fils succeptibles de contenir des voisins. Pour cela, nous définissons pour chaque territoire (pays, département, ...) un centre, et un rayon tels que toute personne se trouvant dans ce territoire soit à une distance du centre inférieure au rayon. Un tel territoire est succeptible de contenir des voisins seulement si le centre est à une distance inférieure à (d + rayon).
Si la hierarchie est bien construite (peu de fils pour chaque territoire) et les territoires pas trop étriqués, on obtient le résultat assez rapidement
recherche : 10km autour de Paris
Afrique - Paris : trop loin
Amérique - Paris : trop loin
Asie - Paris : trop loin
Europe - Paris : ok
Allemagne - Paris : trop loin
France - Paris : ok
...
Océanie - Paris : trop loin