Thèses de magister soutenues

Thèses de magister en cours

Traitement d’images à base de PBST (Partionned Binary Search Tree)

SUJET	Comparaison entre les B-arbres et le hachage digital pour l'accès multi-multidimensionnel
PRÉSENTÉ PAR	W.K HIDOUCI
Après une étude bibliographique importante et très riche en matière de structuration des données sur les médias, Il est demandé d'abord de faire un état de l'art sur ce domaine, surtout en ce qui concerne l'aspect multidimensionnel puis étudier deux schémas "antagonistes" : un schéma représentatif des B-arbres et un autre représentatif du hachage dynamique pour l'accès multidimensionnel. Le travail consiste dans un premier temps, à retrouver les algorithmes pour les deux méthodes, de les réaliser afin de pouvoir les comparer en procédant essentiellement par simulation. La comparaison portera aussi sur les algorithmes de maintenances et les différents facteurs pouvant affecter une technique d'accès aux fichiers.

SUJET	Description et simulation des architectures parallèles de type SIMD.
PRÉSENTÉ PAR	L. DAHMOUNE
Le travail consiste dans un premier temps à étudier et développer un logiciel ( en C/Unix/Xwindows) permettant de construire une machine parallèle SIMD virtuelle, puis dans un deuxième temps d'évaluer ses performances. Après une étude bibliographique importante sur le parallélisme et notamment sur les machines parallèles du type SIMD, un simulateur a été développé. On a ainsi défini une machine avec ses principaux paramètres puis écrit toutes les procédures de communication associées aux diverses topologies aussi bien statiques que dynamiques telles que les tableaux linéaires, les anneaux, les grilles 2D, les réseaux 'cross bar', etc. Le logiciel est orienté vers la pédagogique et offre les possibilités suivantes : - Présenter des algorithmes parallèles - Modéliser les machines parallèles - Simuler l'exécution et évaluer les performances d'un algorithme parallèle donné sur une machine SIMD donnée. Des outils sont alors offerts pour les mises au point et contrôle.

SUJET	Hachage digital multidimensionnel compact avec expansion partielle.
PRÉSENTÉ PAR	M. ARIDJ
De nos jours, les méthodes pour l'accès multi-attributs n'utilisent plus le concept des listes inversées, longtemps utilisées dans les langages à requêtes multiples, qui consistent à associer à chaque attribut une table d'index secondaire. Les techniques actuelles visent un accès disque, pour une requête à plusieurs attributs. On peut citer les articles de Burkhard, Nievergelt, Otto, et beaucoup d'autres. Le schéma proposé est original. D'une part, on exige que la technique du hachage digital soit utilisée sous sa forme séquentielle ( représentation compacte). D'autres part, les blocs adressés ne sont pas fixes selon l'idée de l'expansion partielle, récemment développée sur les arbres B+ ( Article de Ricardo et Larson ). Le travail consiste dans un premier temps à étudier ce schéma en retrouvant tous les algorithmes qui s'y rattachent, puis dans un deuxième temps, évaluer ses performances principalement par simulation. De plus, il serait souhaitable de réaliser une application ( bibliothèque ) en se servant de ce schéma et montrer l'apport par rapport à ce qui existe.

SUJET

SUJET	Élaboration d'un modèle pour les SGBD Objet parallèles et réalisation de son exécuteur de requêtes.
PRÉSENTÉ PAR	S. DELLYS ( Abandon )
De nos jours, les SGBD objets tendent à remplacer la génération des systèmes relationnels du fait de leur puissance de modélisation. Dans le même temps, les machines à architecture parallèle ainsi que les stations de travail interconnectées en réseaux à grand débit, font l'objet d'intenses recherches. Il serait donc intéressant d'intégrer ces deux concepts (bases de données objet et systèmes parallèles) afin d'aboutir à une nouvelle génération de SGBD à modèle de donnée riche tout en profitant des performances des nouvelles architectures. Le travail demandé consiste à étudier les différents travaux effectués dans ce domaine et de faire une synthèse des différentes approches adoptées dans le but de proposer un modèle de données et de réaliser un prototype d'exécuteur de requêtes pour un sous ensemble de ce modèle.

SUJET	Distribution du ‘Hachage par ‘interpolation’ ( HI ) Conformément aux contraintes des SDDS(Scalable Distributed Data Structures)
PRÉSENTÉ PAR	D. BOUKHLEF
Le Hachage par interpolation ( HI ) est une extension du hachage linéaire conçue principalement pour l’accès multidimensionnel. La technique préserve l’ordre des clés et utilise une fonction de projection particulière ( ‘Shuffle Order’) pour transformer une clé multi-attribut en une adresse. L’objectif de ce travail est d’étendre la technique dans un environnement distribué tout en respectant les contraintes des Sdds Les structures des données distribuées et ‘scalables’ (SDDS) sont une famille des structures de données dédiées spécialement pour les traitements distribués s’effectuant généralement sur une architecture multi-ordinateurs. Les SDDS ont été proposées au début des années 90. Leur principe de base consiste à stocker les données sur des sites désignés Serveurs. D’autres sites appelés Clients y accèdent. Les sites Clients gardent généralement des paramètres pour les opérations sur des fichiers distribués sur les sites Serveurs. Le but de ce travail est multiple : - initiation à la recherche sur les structures de données distribuées - Définition d'un schéma pour distribuer HI - Mise en œuvre d'un protocole de communication ( sous Unix) pour tester le nouveau schéma. - Simulation et comparaison avec les méthodes concurrentes.
		Projet "ACT"

SUJET	Gestion de transactions dans Act21
PRÉSENTÉ PAR	AMROUCHE Hakim
Act21 est un SGBD parallèle basé sur un modèle de données par acteurs en cours de développement à l’INI (Projet de recherche Act21). Ce système intègre les objets actifs (acteurs) et les nouvelles structures de données distribuées (SDDS) dans les bases de données. L’architecture en couches du SGBD est comme suit : - Au niveau le plus interne, on a un gestionnaire de fichiers répartis à base de SDDS. - Au niveau intermédiaire, se trouve un gestionnaire d’acteurs et de catalogues. - Au niveau externe, on trouve un interpréteur de requêtes et un langage de programmation de bases de données par acteurs (PACT). La notion de transaction existe aussi bien dans les SGBD centralisés que dans les SGBD réparti. Une transaction est une suite d’opérations sur la base de données, devant s’exécuter de manière atomique (soit toutes les opérations de la transactions s’exécutent soit aucune), de plus un ensemble de transactions lancées en parallèle doit avoir le même effet qu’une exécution en série de ces même transactions. Le problème majeur de la gestion des transactions est l’interblocage (dead lock) où deux ou plusieurs transactions parallèles sont bloquées en attente de ressources verrouillées par ces même transactions . En général plus le degré du parallélisme entre transactions est grand, plus le risque d’interblocage est important.. Le travail demander est d’abord d’étudier les différentes solutions existantes pour les bases de données réparties dans les modèles relationnels et objet. Ensuite de proposer un modèle de transaction adapté à la programmation par acteurs pour être utilisé dans Act21. Un gestionnaire de transaction par acteurs devra alors être réalisé. Echéancier : - Etude sur la gestion des transactions réparties (relationnel et objet).(3 mois) - Choix et solutions adoptés pour le modèle Act21. (3 mois) - Réalisation d’un prototype de gestionnaire de transaction par acteurs.(4 mois) - Tests et rédaction. (2 mois)
		Projet "ACT"

SUJET	Reprises après pannes dans Act21
PRÉSENTÉ PAR	LOUNES NAIMA
Act21 est un SGBD parallèle basé sur un modèle de données par acteurs en cours de développement à l’INI (Projet de recherche Act21). Ce système intègre les objets actifs (acteurs) et les nouvelles structures de données distribuées (SDDS) dans les bases de données. L’architecture en couches du SGBD est comme suit : - Au niveau le plus interne, on a un gestionnaire de fichiers répartis à base de SDDS. - Au niveau intermédiaire, se trouve un gestionnaire d’acteurs et de catalogues. - Au niveau externe, on trouve un interpréteur de requêtes et un langage de programmation de bases de données par acteurs (PACT). Le travail demander est de réaliser une solution pour la reprise après panne au niveau intermédiaire de l’architecture Act21 (gestionnaires d’acteurs et de catalogues). Une base de données sous Act21 peut être vue comme un ensemble d’acteurs coopératifs dans un réseau d’ordinateurs. Chaque site abrite alors un ensemble d’acteurs résidant en mémoire centrale. En cas de panne d’un ou plusieurs sites (et/ou lignes de communications). Le reste du système distribué doit rester dans la mesure du possible fonctionnel. Lors de la reprise du ou des sites qui étaient en panne, ces derniers doivent se re-synchroniser avec le reste du système soit en continuant soit en annulant leurs tâches interrompues par la panne. La base de données doit rester dans un état cohérent. L’une des techniques de reprise après pannes est l’utilisation de fichiers journaux à écriture directe (sans passer par les buffers systèmes). Echéancier : - Etude théorique sur les techniques de reprises utilisées dans les SGBD répartis (relationnels et objets). (3 mois) - Choix et proposition de solutions adaptés au modèle Act21.(2 mois) - Implémentation des techniques de reprise au niveau du gestionnaire d’acteurs.( 4 mois) - Tests et rédaction du mémoire.(3mois)
		Projet "ACT"

SUJET CTH* avec utilisation massive du multicast.

PRÉSENTÉ PAR K. AIT ALI

Une classe de structures de données appelée SDDS « Scalable Distributed Data Structures » a été conçue cette dernière décennie pour répondre aux besoins d’un environnement distribué.

Plusieurs algorithmes ont été proposés dont LH*, RP*, DRT, etc.

Récemment, une nouvelle famille de SDDS a vu le jour. Les nouveaux algorithmes sont à base de la méthode « Trie Hashing » (TH*).

Plusieurs variantes sont proposées : Hachage digital avec l’arbre décentralisé sans multicast, Hachage digital avec l’arbre centralisé sans multicast, Hachage digital avec Multicast.

Le présent travail a trait à la variante qui utilise intensément le Multicast. Il s’agit d’étudier le schéma afin de déduire les algorithmes et de les réaliser dans un réseau d’ordinateurs.

Une étude comparative avec les méthodes utilisant le Multicast notamment LH* et RP*C est à faire.

Outils de travail : Linux et PVM/

Projet "SDDM"

SUJET Un système à base d'acteurs pour l'interrogation des BDD en langage naturel

PRÉSENTÉ PAR A. BADAOUI

Le travail s'inscrit dans le cadre du projet ACT21 en cours de développement à l'INI. Il consiste à proposer une architecture d'un système autorisant la manipulation d'une BDD en langue naturelle. Ce système recevra en entrée une question en langage naturel, la traduit en une requête SQl et la transmet au module EXEC chargé de l'exécution des requêtes de type SQL.

Projet "ACT"

SUJET Etude comparative des méthodes CTH* et DRT*

PRÉSENTÉ PAR Y. Benmoussa

CTH* et DRT* sont deux structures de données distribuées et scalables (SDDS). Chacune des deux méthodes utilise un arbre particulier pour représenter la fonction d'accès d'un client à un fichier distribué. De plus, chaque méthode a sa politique de distribution des données et de l'arbre sur les serveurs de données.
Il s'agit d'étudier les deux méthodes en détail afin de les comparer.
Actuellement, CTH* est implémenté sur la plateforme LINUX.
Concrètement, il est donc demandé de réaliser DRT* dans les mêmes conditions afin de faire des mesures de performances.

Projet "ACT"

SUJET Adaptation de la méthode CTH (Compact Trie Hashing) à un environnement distribué mobile

PRÉSENTÉ PAR AMAR-KHODJA M.

On assiste cette dernière décennie à l’émergence d’une nouvelle classe de structures de données consacrée à un environnement distribué. L’avantage de cette tendance est de tirer profit des performances affichées par ces structures de données dans un contexte mono ordinateur, tout en profitant des avantages offerts par les réseaux d’ordinateurs (grande capacité de stockage, traitement parallèle, sensibilité aux pannes réduite …).

Les principales structures de données distribuées existantes actuellement sont : LH (Linear Hashing), TH (Trie Hashing) et RP (Rang Partitionning).

Le travail se portera sur l’adaptation d’une variante de TH (CTH : Compact TH) à un environnement distribué et mobile. Dans cette optique, on devra non seulement tenir compte des caractéristiques des systèmes distribués (distribution des données, absence du site maître, scalabilité …), mais en respectant aussi les contraintes liées à l’indépendance des déplacements.

Projet "SD2M"

SUJET Adaptation des SDDS dans les réseaux téléphoniques Ad-hoc

PRÉSENTÉ PAR KHELDOUN A.

Il s’agit dans un premier temps d’étudier les structures de données distribuées et scalables (SDDS) et leur implémentation dans une architecture P2P.

Puis, dans un deuxième temps, faire un état de l’art sur les réseaux téléphoniques mobiles et plus particulièrement sur les réseaux Ad hoc. Cette étude sera orientée principalement dans les transmissions des données.

Le travail demandé consiste à concevoir une plate-forme permettant l’implantation des SDDS dans une architecture mobile P2P Ad hoc.

Nous considérons comme SDDS la méthode CTH* ( Distributed Compact Trie Hashing) et nous nous contentons des outils de simulation existants pour implémenter la méthode, puis procéder à des tests.

Projet "SD2M"

SUJET Adaptation de CTH* aux architectures peer-to-peer

PRÉSENTÉ PAR BENNACEUR Amel

Le hachage digital compact distribué (CTH*) est une structure de données distribuée et scalable qui permet de gérer de grands volumes de données tout en maintenant des performances stables et optimales et en préservant l'ordre des enregistrements.
CTH* a été implémenté sur différents environnements distribués fixes et mobiles et a permis de réaliser des temps d'accès courts et indépendants de la taille du fichier.

L'objectif est d'élaborer une nouvelle plate-forme CTH* basée sur une architecture peer-to-peer et qui permettra, d'une part, de réduire le nombre de messages nécessaires au traitement des requêtes et, d'autre part, de passer facilement à une plate-forme totalement mobile.

Projet "SD2M"

SUJET Distribution des données selon la méthode PBST sur les ‘Grid Computer’

PRÉSENTÉ PAR CHIKHAOUI Amina

On désigne par ‘Grid Computing’ l’utilisation de plusieurs ordinateurs pour résoudre simultanément un problème donné qui consomme généralement beaucoup de temps CPU et /ou de quantité de données.

PBST (Partitioned Binary Search Tree) est une nouvelle structure de données dont le but principal est le partitionnement de données.

Il s’agit de faire une étude bibliographique sur les ‘Grid computing’.

Il serait intéressant de combiner la méthode PBST avec les ‘grid computing’ pour réaliser les traitements parallèles sur les données.

Projet "D3"

SUJET Vers une analyse d’images spatiales par bissections

PRÉSENTÉ PAR GOUGACHE Mohammed

Les applications spatiales sont l'un des domaines qui connaît depuis quelques années un formidable essor. Encore réservée à des spécialistes il y a une dizaine d'années, l'utilisation de données spatiales se répand au sein d'un public de plus en plus large. A l'origine cantonnées dans les applications traditionnelles de cartographie, aujourd'hui les données spatiales sont utilisées dans des domaines très variés, tels que le web-mapping, les entrepôts de données, les systèmes d’informations géographiques, la conception assistée par ordinateur (CAD)…, mais aussi dans la mise en œuvre de stratégies de prévention ou de planification (pour la protection de l'environnement, l'étude de la démographie, etc.).

     Les bases de données spatiales sont caractérisées par leur importante taille. Et par conséquence, les requêtes spatiales prennent un temps considérable dans leur exécution. Afin de résoudre ce problème, les SGBD spatiaux utilisent d’autres méthodes d’indexation plus adaptées à ce type de données.

     Les index spatiaux à base d’arbre R (R trees) sont les plus recommandés à cause de plusieurs avantages qu’ils offrent : l’adaptation aux changement, la non-redondance des données, l’efficacité en temps de réponse.

    Il s’agit de considérer des bases de données spatiales 3D indexées par les R_trees, d’étudier et/ou proposer les algorithmes permettant de réaliser des opérations de bissections (coupes par différent sortes de plan au sens mathématique).

SUJET Traitement d’images à base de PBST (Partionned Binary Search Tree)

PRÉSENTÉ PAR
BOUCIF Mohamed El Amine

Le traitement des images reste toujours l’un des problèmes les plus étudiés. L’efficacité du traitement dépend principalement de la structure de données utilisée pour la représentation des images. Plusieurs structures de données ont été proposées dans ce cadre. Ces dernières sont basées essentiellement sur le partitionnement des images (données). Comme la structure PBST (Partitioned Binary Search Tree) est une nouvelle structure de données dont le rôle principal est le partitionnement de données, il serait donc intéressant de classer cette méthode parmi celles utilisées dans le traitement des images.

Il s’agit dans un premier temps de recenser les principales structures de données utilisées.

Dans un deuxième temps, il est question d’étudier la structure PBST et son adaptation à la représentation et le traitement des images.

La méthode ne peut être validée qu’à travers des tests et de comparaisons avec les méthodes compétitives.

Une plateforme de tests est donc à réaliser.

SUJET	*CTH avec utilisation massive du multicast.**
PRÉSENTÉ PAR	K. AIT ALI
Une classe de structures de données appelée SDDS « Scalable Distributed Data Structures » a été conçue cette dernière décennie pour répondre aux besoins d’un environnement distribué. *Plusieurs algorithmes ont été proposés dont LH, RP, DRT, etc.* *Récemment, une nouvelle famille de SDDS a vu le jour. Les nouveaux algorithmes sont à base de la méthode « Trie Hashing » (TH). Plusieurs variantes sont proposées : Hachage digital avec l’arbre décentralisé sans multicast, Hachage digital avec l’arbre centralisé sans multicast, Hachage digital avec Multicast. Le présent travail a trait à la variante qui utilise intensément le Multicast. Il s’agit d’étudier le schéma afin de déduire les algorithmes et de les réaliser dans un réseau d’ordinateurs. Une étude comparative avec les méthodes utilisant le Multicast notamment LH* et RPC est à faire.* Outils de travail : Linux et PVM/
		Projet "SDDM"

SUJET	Un système à base d'acteurs pour l'interrogation des BDD en langage naturel
PRÉSENTÉ PAR	A. BADAOUI
Le travail s'inscrit dans le cadre du projet ACT21 en cours de développement à l'INI. Il consiste à proposer une architecture d'un système autorisant la manipulation d'une BDD en langue naturelle. Ce système recevra en entrée une question en langage naturel, la traduit en une requête SQl et la transmet au module EXEC chargé de l'exécution des requêtes de type SQL.
		Projet "ACT"

SUJET	Etude comparative des méthodes CTH* et DRT*
PRÉSENTÉ PAR	Y. Benmoussa
CTH* et DRT* sont deux structures de données distribuées et scalables (SDDS). Chacune des deux méthodes utilise un arbre particulier pour représenter la fonction d'accès d'un client à un fichier distribué. De plus, chaque méthode a sa politique de distribution des données et de l'arbre sur les serveurs de données. Il s'agit d'étudier les deux méthodes en détail afin de les comparer. Actuellement, CTH* est implémenté sur la plateforme LINUX. Concrètement, il est donc demandé de réaliser DRT* dans les mêmes conditions afin de faire des mesures de performances.
		Projet "ACT"

SUJET	Adaptation de la méthode CTH (Compact Trie Hashing) à un environnement distribué mobile
PRÉSENTÉ PAR	AMAR-KHODJA M.
On assiste cette dernière décennie à l’émergence d’une nouvelle classe de structures de données consacrée à un environnement distribué. L’avantage de cette tendance est de tirer profit des performances affichées par ces structures de données dans un contexte mono ordinateur, tout en profitant des avantages offerts par les réseaux d’ordinateurs (grande capacité de stockage, traitement parallèle, sensibilité aux pannes réduite …). Les principales structures de données distribuées existantes actuellement sont : LH (Linear Hashing), TH (Trie Hashing) et RP (Rang Partitionning). Le travail se portera sur l’adaptation d’une variante de TH (CTH : Compact TH) à un environnement distribué et mobile. Dans cette optique, on devra non seulement tenir compte des caractéristiques des systèmes distribués (distribution des données, absence du site maître, scalabilité …), mais en respectant aussi les contraintes liées à l’indépendance des déplacements.
		Projet "SD2M"

SUJET	Adaptation des SDDS dans les réseaux téléphoniques Ad-hoc
PRÉSENTÉ PAR	KHELDOUN A.
Il s’agit dans un premier temps d’étudier les structures de données distribuées et scalables (SDDS) et leur implémentation dans une architecture P2P. Puis, dans un deuxième temps, faire un état de l’art sur les réseaux téléphoniques mobiles et plus particulièrement sur les réseaux Ad hoc. Cette étude sera orientée principalement dans les transmissions des données. Le travail demandé consiste à concevoir une plate-forme permettant l’implantation des SDDS dans une architecture mobile P2P Ad hoc. Nous considérons comme SDDS la méthode CTH* ( Distributed Compact Trie Hashing) et nous nous contentons des outils de simulation existants pour implémenter la méthode, puis procéder à des tests.
		Projet "SD2M"

SUJET	*Adaptation de CTH aux architectures peer-to-peer**
PRÉSENTÉ PAR	BENNACEUR Amel
Le hachage digital compact distribué (CTH) est une structure de données distribuée et scalable qui permet de gérer de grands volumes de données tout en maintenant des performances stables et optimales et en préservant l'ordre des enregistrements. CTH a été implémenté sur différents environnements distribués fixes et mobiles et a permis de réaliser des temps d'accès courts et indépendants de la taille du fichier. L'objectif est d'élaborer une nouvelle plate-forme CTH* basée sur une architecture peer-to-peer et qui permettra, d'une part, de réduire le nombre de messages nécessaires au traitement des requêtes et, d'autre part, de passer facilement à une plate-forme totalement mobile.
		Projet "SD2M"

SUJET	Distribution des données selon la méthode PBST sur les ‘Grid Computer’
PRÉSENTÉ PAR	CHIKHAOUI Amina
On désigne par ‘Grid Computing’ l’utilisation de plusieurs ordinateurs pour résoudre simultanément un problème donné qui consomme généralement beaucoup de temps CPU et /ou de quantité de données. PBST (Partitioned Binary Search Tree) est une nouvelle structure de données dont le but principal est le partitionnement de données. Il s’agit de faire une étude bibliographique sur les ‘Grid computing’. Il serait intéressant de combiner la méthode PBST avec les ‘grid computing’ pour réaliser les traitements parallèles sur les données.
		Projet "D3"

SUJET	Vers une analyse d’images spatiales par bissections
PRÉSENTÉ PAR	GOUGACHE Mohammed
Les applications spatiales sont l'un des domaines qui connaît depuis quelques années un formidable essor. Encore réservée à des spécialistes il y a une dizaine d'années, l'utilisation de données spatiales se répand au sein d'un public de plus en plus large. A l'origine cantonnées dans les applications traditionnelles de cartographie, aujourd'hui les données spatiales sont utilisées dans des domaines très variés, tels que le web-mapping, les entrepôts de données, les systèmes d’informations géographiques, la conception assistée par ordinateur (CAD)…, mais aussi dans la mise en œuvre de stratégies de prévention ou de planification (pour la protection de l'environnement, l'étude de la démographie, etc.). Les bases de données spatiales sont caractérisées par leur importante taille. Et par conséquence, les requêtes spatiales prennent un temps considérable dans leur exécution. Afin de résoudre ce problème, les SGBD spatiaux utilisent d’autres méthodes d’indexation plus adaptées à ce type de données. Les index spatiaux à base d’arbre R (R trees) sont les plus recommandés à cause de plusieurs avantages qu’ils offrent : l’adaptation aux changement, la non-redondance des données, l’efficacité en temps de réponse. Il s’agit de considérer des bases de données spatiales 3D indexées par les R_trees, d’étudier et/ou proposer les algorithmes permettant de réaliser des opérations de bissections (coupes par différent sortes de plan au sens mathématique).