Les graphes sont omniprésents dans de nombreuses applications, allant du domaine des transports à celui des réseaux sociaux ou de la fouille de données. L’application qui nous motive rentre dans le domaine de l’analyse de la mobilité, bien que l’approche vise à être plus générique. Les applications de mobilité sont clés pour aider des individus, des entreprises et des agences gouvernementales à gérer le trafic des transports publiques, donner les logistiques dans un espace urbain. De telles applications supportent généralement des services pour la planification de route, détection du plus court chemin, les requêtes des plus proches voisins et autres. La caractéristique commune de ces applications est le fait qu’elles reposent sur un réseau routier. En effet, de tels réseaux sont de nature spatio-temporels. Ils ont besoin de représenter l’espace et les contraintes spatiales auxquelles les objets en mouvement sont soumis. Ils doivent aussi considérer que le temps de voyage sur un réseau routier dépend directement du trafic et que les patterns de trafic dépendent à leur tour non seulement de la région en question mais aussi le temps du jour. Par conséquent, le temps qu’un objet en déplacement prend pour traverser un segment de chemin dépend typiquement de son temps de départ. Par exemple sur la même avenue à Fortaleza, Brésil, à 19h30 cet avenue est complètement embouteillée et donc le temps de traversée plus longue qu’à 20h40 lorsque le trafic est moins intense.
(a) Trafic à 19h10 (b) Trafic à 20h40
Cependant, la majorité des solutions proposées pour les requêtes spatiales sur les réseaux routiers échouent dans la représentation de la réalité en ce sens qu’ils ne considèrent pas la dépendance temporelle des réseaux routiers. Ils supposent que ces réseaux sont statiques et le coût de traversée de chaque arête est donné par la longueur de cette arête et donc ne varie pas dans le temps. Cette supposition n’est certainement pas vraie sur un scénario réel qui est mieux représenté par un graphe qui dépend du temps qui prend en considération que le temps que l’on prend pour traverser un segment de route dépend typiquement du temps de départ.
Certaines recherches récentes ont inclu la dépendance temporelle pour résoudre les requêtes spatiales conventionnelles telles que les requêtes des k plus proches voisins et le plus court chemin. Comme dans ces travaux, nous considérons aussi ces dépendances pour répondre aux requêtes. Plus précisément, nous considérons que le réseau est modélisé comme un graphe où le temps de traversée de chaque arête est fonction du temps de départ. Ces fonctions donnent le temps de traversée d’une arête selon l’instant où l’on commence la traversée de cette arête. Cependant, traiter les requêtes dans un graphe qui dépend du temps est un défi dû au fait que l’espace requis pour stocker ces graphes est significativement plus large que l’espace nécessaire pour stocker ceux indépendants du temps, puisqu’il est nécessaire de garder pour chaque arête le coût de la traverser pour chaque intervalle de temps d’un jour. De plus, les solutions pour les requêtes conventionnelles dans des graphes statiques ne peuvent pas être directement appliquées pour les problèmes des graphes qui dépendent du temps. Particulièrement il n’est pas faisable d’appliquer la technique bien connue de speed-up de recherche bidirectionnelle qui commence une recherche simultanément à partir de la source et de la destination pour résoudre le problème du plus court chemin dans un graphe qui dépend du temps puisque le temps d’arrivée devra être connu à l’avance pour une telle procédure. Malgré les efforts faits jusqu’ici, nous savons que certaines applications réelles ont besoin de larges graphes pouvant avoir des millions de nœuds et d’arêtes. Dans le cas des graphes qui dépendent du temps, la taille du graphe peut être augmentée par plusieurs ordres de magnitude dépendant de la granularité du temps. Ainsi à part les défis des requêtes sur les larges graphes qui dépendent du temps, nous envisageons également le problème de stockage, de traitement et d’accès à des graphes à grande échèle de façon efficiente. Dans ce contexte, plusieurs questions de recherche font surface quand on a affaire à de tels larges graphes qui dépendent du temps telles que :
- Comment construire un TD-LSG en utilisant les données spatio-temporelles ou les traces temporelles en général ?
- Comment inter-relier et enrichir le TD-LSG avec des ressources sémantiques ?
- Comment permettre un traitement de requête scalable sur un TD-LSG ?
- Comment organiser et maintenir un TD-LSG dans une architecture distribuée ?
La méthodologie à adopter dans ce projet de recherche consiste à suivrent les étapes suivantes :
- Comprendre et définir le problème de façon précise;
- Evaluer l’état de l’art lié aux problèmes définis;
- Evaluer les méthodes, techniques et outils pour résoudre les problèmes soulignés plus haut;
- Développer de nouvelles méthodes et technique pour résoudre ces problèmes;
- Promouvoir des missions de recherche de France à Rio afin de discuter des problèmes spécifiques et solutions;
- Préparer et publier les premiers résultats sous forme de rapports techniques et plus tard dans des conférences et journaux reconnus par Qualis CAPES et le CNRS;
- Prototyper les outils qui implémentent les techniques et méthodes.
- Réaliser des séminaires pour disséminer les résultats.
