Discussion :

[davidcarlo]

Bonjour,

Je souhaite développer une application mobile de géolocalisation avec des nuages de points cependant j'ai un raisonnement à bien mettre en place et j'ai besoin de votre aide pour ne pas partir du mauvais côté:

Le principe est le suivant : Le but est de faire "matcher" les gens entre eux mais on a une base de données de 100 000 utilisateurs répartis dans toute la France, à Paris, Grenoble, Lyon mais aussi dans les campagnes par ex.
Je souhaite lister les utilisateurs, un par un, du plus proche au moins proche. Bien entendu, je ne souhaite avoir que les utilisateurs qui sont à moins de 20 km de moi (mais mon algorithme doit fonctionner quelque soit la distance).
Il y a plusieurs méthodes, dont la plus simple étant de comparer ma position avec les 100 000 autres utilisateurs et je prend tous ceux qui ont une distance inférieure à 20 km. Seulement, si on passe 1 milliseconde à vérifier la distance avec chaque autre utilisateur, avant de savoir qui est le plus proche de moi, j'aurai attendu 100 secondes.

Pour un utilisateur, on pourrait accepter 100 secondes d'attente. Mais s'il y a 100 utilisateurs qui font la demande, on peut s'attendre (attention, ce calcul est totalement faux, mais c'est pour illustrer mon exemple), on aura 2 cas : soit on traite tout en même temps, et les utilisateurs auront leur réponse dans 100 * 100 secondes, soit le premier à avoir effectué la demande aura sa réponse au bout de 100 secondes, puis on s'occupe du deuxième qui aura sa réponse dans 100 + 100 secondes, etc... le centième attendra 100 * 100 secondes.

Pour accélérer les choses, chaque utilisateur pourrait avoir la base de 100 000 utilisateurs et faire le travail sur son téléphone, mais... 100 000 utilisateurs qui téléchargent les données de 100 000, avec une taille de données de 1ko par utilisateur, ça nous fait 10 000 000 000 de ko soit 9 tera de données à transmettre par internet, c'est un peu énorme.

Pour optimiser, on peut regrouper les utilisateurs par région. On pourrait dire : Les utilisateurs qui sont à Lyon ne vont consulter que les utilisateurs de Lyon et les utilisateurs de paris ne consulteront que les utilisateurs de Paris. Bingo, on ne cherche plus parmi 100 000 utilisateurs, mais parmi 20 000 pour chaque ville. On a optimisé la recherche. mais d'autres problèmes se posent : ceux qui sont pile poil à la frontière de Paris et de Lyon, ils vont interroger quelle base ? Celle de Paris ou celle de Lyon ? Et ce problème se pose à toutes les échelles : Pays, Région, Département, Ville, Quartier. les utilisateurs de deux villes dans deux pays différents mais qui sont à 2 km de distance doivent pouvoir se contacter.

Quelle est la méthode la plus efficace ? sachant que finalement je ne vais pas raisonner en région mais bien par la distance que l'utilisateur aura demandé pour "matcher".

Je crains de réinventer la roue, donc je me pose certaines questions sur ces choix. Si vous pouvez m'orienter dessus, ou me conseiller une documentation spécialiser sur la question, je suis preneur

Merci d'avance

[ed73170]

Bonjour,

Il faut bien évidement ne rien faire sur le téléphone et ne rien stocker dessus.

Pour ce genre d'appli, on met en général un ou plusieurs serveurs suffisamment dimensionnés avec la base de données spatiale qui va bien. Chaque utilisateur envoie périodiquement sa position au serveur, position qui est stockée dans la base. Pour connaître les utilisateurs proches, il suffira d'une requête pour récupérer les utilisateurs éloignés de moins de X mètres de la position du demandeur, et ça tombe bien car les bases de données spatiales ont justement ce genre de fonctionnalité optimisée. Ensuite, toujours sur le serveur, tu tries les données par ordre de proximité et tu les envoies au téléphone qui n'aura plus qu'à les afficher ou les exploiter.

Il est bien évident que les traitements sur le(s) serveur(s) doivent être parallélisés de manière à ce que le temps de réponse dépende le moins possible du nombre d'utilisateurs connectés simultanément.

Parmi les bases de données supportant les fonctions spatiales il y a : Oracle spatial, SQL Serveur spatial, MySql, Sqlite / Spatialite (mono utilisateur).

[davidcarlo]

Merci beaucoup ed73170,

cette réponse correspond parfaitement à ce que je fais, c'est vrai que ce n'est pas mon domaine de prédilection mais là çà me donne les bonnes pistes pour avancer.