Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > membres

Ghizlane Echbarthi


PhD student

Team Graphes, AlgOrithmes et AppLications
Institution Claude Bernard University of Lyon 1
Location Nautibus (Université Lyon1)
E-mail ghizlane.echbarthi at
Contact details Publications Thesis
Subject Big graph processing : Partitioning and aggregated querying
Abstract The advent of "big data" has tremendous repercussions on a broad range of data related domains, and it has impelled the use of novel techniques that achieve the best tradeoff between computational cost and precision. In the graph theory field, graphs represent a powerful tool for data and problem modeling where all kinds of problems, starting from the very simple to the very complicated, can be effectively formalized. To resolve NP-complete or NP-hard problems in this field, research is being directed to approximation algorithms and heuristic solutions rather than exact solutions, which exhibit a very high computational cost that makes them impossible to use for massive graph datasets. In this thesis, we tackle two main problems: first, the graph partitioning problem is studied in the context of "big data", where the focus is put on large graph streaming partitioning. In fact, the graph partitioning is an important and challenging problem when performing computation tasks over large distributed graphs, the reason is that a good partitioning leads to faster computations. We studied and proposed several streaming partitioning models and heuristics, and we studied their performances theoretically and experimentally as well. The second problem that we tackle in this thesis, is the querying of partitioned/distributed graphs. In fact, querying graph datasets proves to be an important task as most of the real-life datasets are represented by networks of labeled entities. In this context, we study the problem of "aggregated graph search" that aims to answer queries on several graph fragments, and has the task to build a coherent final answer such that it forms an "approximate matching" to the initial query. We proposed a new method for "aggregated graph search", and we studied its performances theoretically and experimentally on different real word graph datasets.
Advisor Hamamache Kheddouci

Last update : 2018-01-16 13:55:50