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 :

  • un algorithme d’échantillonnage de points avec distribution presque uniforme dans l’ensemble défini par une requête du premier ordre ;
  • un algorithme estimant le volume et la forme de cet ensemble.

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.