Après OpenStreetMap, voici le service de géomatique et de cartographie le plus utilisé et le plus connu : Google Maps.
L’outil, racheté par Google en 2004, se base sur un ensemble de couches de données géographiques (carte, vue satellite) mais aussi sur une représentation en immersion via des assemblages de photos en vue à la première personne. Google Maps cartographie aussi les lieux intérieurs et permet de créer des itinéraires , de connaître l’état du trafic et d’obtenir des descriptions et la fréquentation de points d’intérêts géographiques : lieux géographiques, établissements recevant du public… Google Maps est construit à partir de sources variées et les internautes peuvent contribuer et suggérer des modifications.
Google Maps a d’importants défis technologiques à relever : proposer des données à jour, calculer les bons itinéraires, utiliser les données recueillies en temps réel par les téléphones et périphériques connectés pour proposer des estimations de fréquentation justes.
Google communique peu sur la pile technologique utilisée pour son service Maps. On sait que la base de données NoSQL Bigtable est utilisée pour Google Maps. Cette base de données clés-valeurs orientés colonnes à une très faible latence, permet de gérer un nombre très important de requêtes en temps réel et supporte sans problème les accès en écriture et en lecture même dans un déploiement à l’échelle de la planète. Google Code propose par exemple la librairie S2 pour indexer et manipuler les données géographiques. Et pour traiter les très forts volumes et demandes des utilisateurs, Google utilise certainement le design pattern maison nommé MapReduce. On peut imaginer l’utilisation des structures de données et technos suivantes :
- Arbre quaternaire : Un quadtree est une structure de données hiérarchique couramment utilisée dans les applications spatiales. Elle subdivise de manière récursive un espace en quadrants jusqu’à ce que chaque cellule contienne un nombre gérable de points de données. Cette structure est efficace pour l’indexation et la recherche spatiales.
- Graphe : Google Maps utilise probablement des structures de données « graphe » pour représenter les réseaux routiers, les sommets représentant les intersections et les arêtes représentant les routes. L’intérêt est de pouvoir proposer des itinéraires aux utilisateurs. Il faut obligatoirement utiliser les graphes avec des algorithmes dédiés de recherche du chemin le plus efficace (Dijkstra, Prim, Kosaraju, Tarjan). Cela permet aux algorithmes de recherche de chemin efficaces tels que Dijkstra ou A* de calculer les itinéraires entre les emplacements.
- Geohash : Geohash est un moyen d’encoder des coordonnées géographiques dans une courte chaîne de lettres et de chiffres, ce qui peut être utile pour indexer et rechercher efficacement et très rapidement des données spatiales proches. OpenStreetMap s’en sert et la base de données MongoDB en propose une implémentation facile.
- B-trees : Les B-arbres peuvent être utilisés pour indexer et stocker efficacement des données, en particulier pour les requêtes de plage sur de grands ensembles de données, ce qui est le cas avec des données géolocalisées.
- R-trees : Les R-arbres sont une structure de données adaptée à l’exploration spatiale (dans le sens « explorer un espace défini »). Là où les B-trees sont surtout utiles pour les indexes de bases de données et les systèmes de fichier, les R-treees sont parfaits adaptés aux SIG.
- Structure en arbre : Les structures de données « Trie » peuvent être utilisées pour la fonctionnalité de saisie semi-automatique dans les barres de recherche, permettant des suggestions rapides basées sur une saisie partielle.
- Tables de hachage : les tables de hachage peuvent être utilisées pour des recherches rapides de valeurs clés, telles que l’indexation d’emplacements ou d’attributs associés à des éléments de carte. Cette structure de données est très utile lorsque le nombre de clé-valeur est important, ce qui est le cas en géomatique.
Si vous avez déjà essayé de télécharger une portion de carte en mode hors-ligne, vous aurez peut-être constaté que Google génère des tuiles rectangulaires. Ces tuiles contiennent des données vectorisées pour les bâtiments et les routes. Beaucoup plus légères que les données au format image classique, les représentations graphiques sont stockées sous forme d’équations mathématiques. Ce qui permet un usage extrêmement réduit de ressources de stockage.