Thèse Storage and query in a massive distributed graph for the web of things F/H

Description de l'offre

about the role

Votre rôle est d'effectuer un travail de thèse sur : « Storage and query in a massive distributed graph for the web of things »

A l'heure actuelle, 15 milliards d'objets sont connectés à Internet et les prévisions indiquent 75 milliards d'objets en 2020. Dans ce cadre Orange veut se positionner comme un acteur incontournable. Pour ce faire, un composant important est le système d'informations référençant la description de tous les objets connectés, leurs interactions et intégrations dans le monde réel.

Orange possède un atout indéniable pour atteindre cet objectif : ses infrastructures de communication. Pour tirer parti de cet atout, le paradigme de Fog Computing[1] semble le plus adapté, le but étant de positionner les calculs et le stockage de données à l'endroit le plus approprié dans l'infrastructure depuis les centres de calcul jusqu'aux objets[2]. Dans le contexte de l'Internet des objets, du fait de la géo-distribution des objets, un tel système permettra d'avoir de meilleures QoS [3].

Dans notre conception d'un référentiel des objets, nous nous appuyons sur une base de données orientée graphe pour maintenir une référence à chaque objet et caractériser les relations/interactions qui les lient. Dans ce champ d'application, plusieurs solutions existent : Neo4J, Janus, OrientDB, G*… Ces bases permettent de parcourir aisément des très grands graphes et donc de faciliter les recherches complexes de relations entre objets. Dans notre contexte Fog, nous prônons une distribution de la gestion de ce graphe au travers de toute l'infrastructure de l'opérateur, ce qui implique un partitionnement du graphe où chaque partie serait gérée indépendamment.

Dans le cadre de l'internet des objets, la taille du graphe à analyser sera grande (plusieurs milliards de sommets et d'arcs) et donc maintenir tout le graphe sur un seul serveur serait voué à l'échec.

Certaines bases orientées graphe proposent un mode clusterisé. Elles cherchent alors à optimiser les performances du système par le biais, par exemple, de l'équilibrage de charge, en répliquant de façon cohérente le graphe sur chacune des machines du cluster (cf Neo4J). D'autres se basent sur un système de stockage distribué, mais perdent en efficacité du fait que le stockage n'a pas la connaissance du graphe et donc ne peut pas optimiser le placement des noeuds et des arcs (eg Titan/Cassandra). Il faudra donc étudier les différentes options et exhiber un système qui sera capable de gérer ce graphe [5].

Au vu de l'étendu de cette base graphe, il devient aussi important de bien penser le système de requêtes afin de prendre en compte les latences et incohérences induites par cette haute distribution et la dynamique du système (ajouts, modifications, suppressions dynamiques des objets). Les idées qui devront être creusées dans cette thèse mettront en avant des solutions de type probabiliste (ou heuristique) et incrémentale. Le temps devient un paramètre de la requête, plus il y a de temps accordé à la requête, meilleur (plus précis) sera son résultat [4,5].

Pour plus de détails sur la mission scientifique et les principales activités associées à la thèse, veuillez consulter la section 3 "Le plus de l'offre".

about you

Vous êtes titulaire d'un Master 2 en informatique avec une forte composante d'algorithmique distribuée.

Une expérience en bases de données et/ou en graphes complexes sera valorisée et grandement appréciée.

Pour l'implémentation des algorithmes conçus et leur validation par des simulations, des compétences en programmation sont absolument nécessaires.

Vous devrez faire preuve de curiosité et d'autonomie.

Vous maîtrisez à minima l'anglais technique (écrit et oral).

additional information

Objectif scientifique - verrous à lever :

L'objectif de la thèse est dans un premier temps de contribuer à définir une solution innovante mettant en oeuvre une base de données graphe distribuée dans l'infrastructure de l'opérateur et ensuite de proposer un langage de requête adapté proposant des réponses probabilistes et incrémentales (plus on attend plus la réponse sera précise et complète).

Ces résultats constitueront la pierre angulaire de la plateforme Thing'in, le référentiel des objets connectés d'Orange.

Les principaux verrous sont :

(1)la spécification et la mise en oeuvre d'un tel graph (unique) complètement distribué sur plusieurs sites. Un graphe qui est en plus dynamique ;

(2)l'étude et la mise en oeuvre de processus distribués sur le graphe qui retourne de façon incrémentale les résultats (de façon probabiliste, et de plus en plus précis). Un langage de requête devra être défini pour prendre en compte ce comportement.

Approche méthodologique-planning :

Etat de l'art

·  Base de données distribuée,
·  Base graphe et les différentes méthodes de distribution,
·  Langage de requêtes dans une base graphe,
·  Requêtes incrémentales, probabiliste et heuristiques dans un graphe.

Proposition d'architecture distribuée pour gérer le graphe

Implémentation d'un prototype sur (X sites)

Proposition d'un système de requêtage (incrémentales, probabiliste et heuristiques) avec son langage

Implémentation du système de requêtage

Rédaction du manuscrit.

department

Vous serez pleinement intégré(e) au sein d'une équipe de recherche Orange Labs, très active au sein de l'écosystème d'innovation (IRT B-Com, pôles de compétitivité Images & Réseaux et Systematic, INRIA, Université de Rennes 1…).

Qu'est ce qui fait la valeur ajoutée de cette offre ?

Vos travaux contribueront directement aux activités d'innovation menées pour le compte du groupe Orange, avec des perspectives de concrétisation rapide, à travers l'implémentation dans les infrastructures exploitées au sein de l'entreprise.

Pour cela, vous aurez accès aux plateformes et outils de laboratoire dimensionnés pour les services grand public et entreprises.

Vos travaux prennent place au sein d'une des plateformes d'intégration de la recherche définies par Orange Labs Recherche. Une trentaine de personnes contribuent actuellement à la construction de la plateforme dont 9 se trouvent à Orange Labs Cessons dans votre équipe d'accueil. Ces personnes font partie de l'équipe DIESE/CES/DDSD experte en stockage et systèmes distribués (20 personnes). Cette équipe est composée d'ingénieurs de recherche, d'architecte, de chef de projets, de développeurs, d'un thésard, d'un post-doc et de stagiaires.

De plus vous serez donc amené(e) à collaborer avec les équipes projets qui utiliseront cette plateforme.

Références :

[1] A. V. Dastjerdi, et al. Fog computing: Principals, architectures, and applications. 2016.

[2] S. Sarkar and al. Assessment of the suitability of fog computing in the context of internet of things. IEEE Tr. on Cloud Computing, 2015.

[3] E. van der Zee and al. Application of geographical concepts and spatial technology to the internet of things, 2013.

[4] Malewicz et al. Pregel: A System for Large-Scale Graph Processing. 2010.

[5] A. Labouseur and al. The G* graph database: efficiently managing large distributed dynamic graphs. 2014.

contract

Thesis