Bases de Données / Databases

Site Web de l'équipe BD du LIP6 / LIP6 DB Web Site

Outils pour utilisateurs

Outils du site


site:recherche:axes_de_recherche

Ceci est une ancienne révision du document !


Thèmes de recherche

Positionnement scientifique

Les problèmes actuels de gestion de données se caractérisent par un accroissement constant et considérable des données à traiter et par l’émergence de nouveaux usages de ces données, principalement induits par le développement du web social et du web sémantique. Les systèmes et les technologies classiques de la gestion de données ne sont plus à même de gérer, de traiter, et d’analyser efficacement ces gigantesques masses de données. Les recherches menées dans l’équipe Bases de Données visent à offrir des solutions efficaces et originales pour la gestion de données à large échelle et ses nouveaux usages. Elles se concentrent plus précisément sur l’accès aux données, la qualité et la cohérence des données et la gestion de transactions à large échelle.

Filtrage et Agrégation de Flux d’Informations

Positionnement scientifique

Les utilisateurs du Web 2.0 sont de plus en plus confrontés à une surcharge d’information provoquée par l’apparition de ressources d’informations de plus en plus dynamiques comme les sites d’actualités et les médias sociaux. L’enjeu du thème “Agrégation de flux RSS” est de fournir à ces utilisateurs des outils de personnalisation de flux d’informations sur le Web. L’approche choisie consiste à combiner le standard RSS largement utilisé par les applicationsWeb 2.0 avec des techniques d’interrogation de flux de données. Nous avons en particulier étudié des problèmes posés par le passage à l’échelle en terme de nombre de flux et de requêtes à traiter.

Principaux résultats

Le projet ANR RoSeS (2008-2011) se trouve au coeur de ce thème de recherche. L’objectif de ce projet (coordonné par Bernd Amann) était de réaliser un agrégateur de flux d’informations qui intègre un crawler RSS et un moteur de requêtes continues pour l’interrogation de flux RSS. Le moteur de requêtes RSS développé par Jordi Creus dans le cadre de sa thèse intègre une nouvelle technique d’optimisation multi-requêtes pour des grandes collections de requêtes continues RSS. Cette technique est fondée sur une algèbre d’opérateurs continues (filtrage, union, jointure, transformation) et des règles de normalisation et de factorisation de prédicats. Une contribution importante est la définition d’un algorithme de recherche approximative d’un arbre de Steiner minimal dans un treillis d’inclusion de prédicats logiques exploitant les propriétés particuliers de la distribution des coûts dans le graphe. Ces travaux ont été publiés dans deux conférences internationales[26, 15] et un journal national [39]. La thèse de Roxana Horincar présente une nouvelle stratégie de rafraîchissement de documents RSS qui prend en compte le problème de perte d’information [16] et intègre un modèle d’estimation de divergence dynamique adapté aux flux RSS [23]. Ce travail a adapté des travaux existants sur les stratégies “best-effort” pour le crawling de pages web et inclut des nouvelles techniques d’estimation en-ligne des fréquences de publication de flux RSS. Par ailleurs, nous avons étudié des algorithmes d’estimation de scores dans les réseaux d’annotation collaboratifs (social tagging systems). Nous nous sommes particulièrement intéressés à des problèmes d’optimisation des calculs de scores sociaux en partant des travaux de thèse de Camelia Constantin et des travaux d’Hubert naacke sur la cohérence de données répliquées.

Archivage du Web

Positionnement scientifique

L’archivage duWeb est en pleine expansion depuis une dizaine d’années, dans un nombre grandissant de pays. L’un des enjeux du thème est d’améliorer la qualité (complétude et cohérence temporelles) des archives Web malgré la limitation des ressources (bande passante, politesse, stockage. . .). La complétude reflète la quantité de versions de pages importantes archivées par rapport aux versions générées sur les sites. La cohérence reflète le fait que les versions archivées sont apparues en même temps sur le Web. Pour cela, il faut estimer le comportement des sites pour crawler au bon moment. Une fois l’archive constituée, il est nécessaire de disposer d’outils de recherche d’information (RI) adaptés aux caractéristiques des archives (incomplétude et dimension temporelle)

Principaux résultats

Notre approche, développée dans le cadre du projet ANR Cartec (2008-2011) consiste à fournir un outil très précis de comparaison entre versions successives, afin de mieux quantifier les changements intervenus. Afin de tenir compte de l’aspect visuel des pages (primordial dans le contexte du dépôt légal), nous procédons au préalable à une segmentation de la page en blocs, puis affectons des poids d’importance aux blocs, ce qui permet de quantifier un changement intervenu dans un bloc. Ceci permet, dans une phase d’apprentissage, de définir un pattern de changement quotidien pour chaque page. Ces patterns permettent de mettre en oeuvre des algorithmes optimisant la complétude temporelle, la cohérence temporelle, ou bien les deux à la fois (Thèse de Myriam Ben Saad). Les résultats obtenus sont d’une part un prototype qui inclus la segmentation de versions de page, leur comparaison et le calcul de l’ordonnancement ou de la fréquence optimale, et d’autre part un grand nombre de publications [32, 29, 30, 12, 13, 4]. Il est à noter que l’originalité de notre approche, par rapport aux approches précédentes, a été unanimement reconnue. Elle a valu deux récompenses best student paper à Myriam Ben Saad [29, 12]. Par ailleurs, dans le cadre de la thèse de Zeynep Pehlivan, nous developpons des outils de RI pour les archives. Les travaux portent sur la définition d’un modèle de données [27], d’algorithmes de ranking temporel incluant les blocs des pages segmentés et leur importance, ainsi que, plus récemment, des techniques de compression d’index par élagage (pruning). Enfin, les techniques développées dans le cadre du projet Cartec sont reprises et étendues dans le cadre du projet européen Scape (collaboration avec M. Cord, équipe Malire). La contribution de l’équipe BD est principalement de développer un nouvel outil de segmentation plus précis que les outils actuels [24, 10]. Cet outil se base sur une approche hybride (structurelle et par traitement d’image) développée dans le cadre notamment des thèses de Marc Law et Andrès Sanoja.

Gestion des données et des transactions à large échelle

Positionnement scientifique

Nous étudions les problèmes de gestion de données dans les applications web transactionnelles. Une caractéristique principale de ce type d’application est le nombre important d’utilisateurs qui accèdent concurremment à des données pour les modifier, ce qui génère des lectures/écritures intensives. En présence de millions d’utilisateurs, il s’avère complexe de maintenir la cohérence des données lues ou modifiées simultanément (e.g., enchères en ligne). D’une part, les données doivent être répliquées afin de traiter en parallèle les nombreuses demandes de lecture. D’autre part, la modification d’une donnée répliquée nécessite de synchroniser les répliques pour garantir leur cohérence, ce qui ralentit l’accès aux données. Les travaux effectués par l’équipe BD visent à offrir un compromis cohérence/performance le mieux adapté à la gestion des transactions en fonction du contexte applicatif.

Principaux résultats

Dans le cas où les transactions sont courtes, mais trop nombreuses pour être traitées de manière centralisée, nous avons proposé une solution intergicielle décentralisée pour acheminer (ou router) chaque transaction vers une réplique optimale, de telle sorte que la réplique choisie soit suffisamment cohérente et que le temps de réponse des transactions reste inférieur au plafond toléré par les utilisateurs finaux [35, 50, 40]. La solution repose sur une infrastructure pair-à-pair qui découple les serveurs de données, et les tiers chargés de maintenir la cohérence des répliques et d’équilibrer la charge. Un prototype (TransPeer [17]) a été expérimenté à grande échelle. De plus, une stratégie de routage optimiste permet de paralléliser encore plus largement les transactions. Pour cela, l’indépendance entre les transactions est déterminée dynamiquement pendant leur exécution [31, 40]. Ces travaux se sont déroulés dans le cadre du projet ANR Respire porté par S. Gançarski. Lorsque la charge transactionnelle présente des pics importants (augmentation brusque du nombre d’utilisateurs simultanés voulant modifier la même donnée), nous avons proposé, au sein du projet SyncDB (projet interne au LIP6, en collaboration avec l’équipe Regal), une solution répartie, basée sur un anneau à jeton. La solution est robuste aux pics de transactions, et de plus, tolère les pannes de plusieurs membres consécutifs de l’anneau [25]. Lorsque l’infrastructure sous-jacente doit être louée en fonction de l’usage (modèle dit pay per use), nous avons proposé une solution pour ajuster le nombre de machines qui forment l’intergiciel, au plus près des besoins provenant de la charge applicative qui peut croitre et décroitre [21]. Nous nous sommes également intéressées à des transactions portant sur des données semi-structurées (XML). Sur chaque serveur, nous avons proposé un algorithme de gestion de concurrence optimiste qui autorise les transactions à s’effectuer en parallèle lorsque les données touchées ne sont pas conflictuelles a priori [37, 34].

Qualité de Workflows de Données

Positionnement scientifique

Des nombreuses applications modernes sont définies par des compositions de services web spécialisées pour traiter et pour produire des données complexes. Dans certains domaines comme les chaînes de traitement de données scientifiques ou de données du web, le choix des services (et des paramètres utilisés) peuvent fortement influencer la qualité des resultats obtenus. Dans cette thématique nous nous adressons au problème de l’estimation et l’amélioration de workflows en prenant en compte la provenance et la qualité des données produits par les appels de service. Nous étudions à la fois l’interaction entre les modèles de qualité de services et de qualité de données, leurs mise-en-oeuvre et leur application dans le contexte de la génération d’entrepôts de données web.

site/recherche/axes_de_recherche.1464629200.txt.gz · Dernière modification: 30/05/2016 19:26 par amann