The French National Research Agency Projects for science

Voir cette page en français

ANR funded project

Fondements du numérique (DS0705) 2014
Projet Aggreg

Aggregation Queries

The main goal of the Aggreg project is to develop efficient algorithms
for answering aggregate queries for databases and data streams of
various kinds. Aggregate queries are central for computing statistics on data
collections: Rdf stores, NoSql databases, streams of data trees in Xml
or Json format, uncertain databases, relational databases, and datawarehouses.

Considering that counting is the basis of aggregate queries the principal difficulty here
is to overcome the inherent computational hardness of many
counting problems, which precludes general and efficient solutions.
Instead, we propose to:
study the complexity of expressive fragments of the class of aggregate queries,
search for efficient algorithms on tractable fragments,
identify which parameters can be fixed in order to obtain tractability,
find general algorithms that are gracefully degrading, and also efficient approximation algorithms.
We apply methods from algebra, automata, probability, algorithmics and complexity theory.

Partners

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

ANR grant: 423 587 euros
Beginning and duration: octobre 2014 - 48 mois

 

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

Project ID: ANR-14-CE25-0017

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

 

Back to the previous page

 

The project coordinator is the author of this abstract and is therefore responsible for the content of the summary. The ANR disclaims all responsibility in connection with its content.