Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 20 Mars 2001

Approximation dans les bases de données contraintes

par David Gross-Amblard

Le modèle des bases de données contraintes, introduit par Kanellakis, Kuper et Revesz permet la prise en compte d'informations géométriques, comme les données cartographiques. Les objets géométriques sont représentés comme la solution d'un système d'équations ou d'inéquations, sans limitation sur leur dimension. La complexité en temps de l'évaluation des requêtes du premier ordre ou du volume est raisonnable lorsque la dimension des objets est fixe. Lorsque la dimension des objets est une variable du problème, cette complexité est prohibitive (globalement exponentielle dans la dimension).

Dans cet expose, nous nous intéressons à l'obtention d'algorithmes d'évaluation en temps polynomial dans la dimension, par des techniques d'approximation probabiliste. En étendant les travaux de Dyer, Frieze et Kannan, nous obtenons :

Sous certaines conditions, le volume peut être estimé sans évaluation préalable de la requête.

Nous présentons un prototype de base de données spatiales mettant en oeuvre certains de ces algorithmes probabilistes sur des données réelles.

Mots clés : bases de données contraintes, approximation, schéma d'approximation, estimateur, générateur, échantillonnage, dimension, volume, erreur relative.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr