L'Agence nationale de la recherche Des projets pour la science

Translate this page in english

Fondements du numérique (DS0705) 2014
Projet Aggreg

Requêtes d'Agrégation

Le projet AGGREG vise prioritairement le développement d’algorithmes efficaces pour évaluer des requêtes d’agrégation relatives à des bases de données et des flux de données.
Ces requêtes sont au centre de calculs de statistiques sur les données: Rdf, bases de données NoSQL, flux d'arbres de données en XML ou JSON, bases de données relationnelles et entrepôts de données.
Sachant que le comptage est à la base des requêtes d'agrégation, l'enjeu est de surmonter la difficulté algorithmique intrinsèque de nombreux problèmes de comptage (beaucoup d'entre eux sont #P-difficiles, c'est-à-dire parmi les plus difficiles des problèmes de comptage associés à la classe NP). Cela exclut des solutions générales et efficaces.
Au lieu de cela, nous proposons :
d'étudier la complexité de fragments expressifs de la classe des requêtes d’agrégation,
de rechercher des algorithmes performants pour les fragments traitables et des algorithmes d'approximation efficaces pour les fragments difficiles,
d'identifier les paramètres qu’il faut fixer pour accéder à un traitement efficace de problèmes réputés difficiles en toute généralité.
Nous appliquerons des méthodes issues de l'algèbre, des automates, des probabilités, de l'algorithmique et de la théorie de la complexité.


Partenaires

IMJ-PRG Institut de Mathématiques de Jussieu-Paris Rive Gauche

INRIA Centre Lille-Nord Europe Institut National de Recherche en Informatique et en Automatique (INRIA) Centre Lille - Nord Europe

LIF Laboratoire d'Informatique Fondamentale

Aide de l'ANR 423 587 euros
Début et durée du projet scientifique octobre 2014 - 48 mois

 

Programme ANR : Fondements du numérique (DS0705) 2014

Référence projet : ANR-14-CE25-0017

Coordinateur du projet :
Monsieur Joachim Niehren (Institut National de Recherche en Informatique et en Automatique (INRIA) Centre Lille - Nord Europe)

 

Revenir à la page précédente

 

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.