Approche déclarative pour énumérer des motifs intéressants – DAG

Ce projet a pour objet la fertilisation croisée entre trois domaines de recherche -- l'intelligence artificielle, l'algorithmique combinatoire et les bases de données -- pour apporter des solutions originales à un type fondamental de problèmes en fouille de données. Nous nous concentrons sur les problèmes d'énumération de motifs intéressants dans de larges volumes de données, appelé dans la suite iPeP pour « interesting Patterns enumeration Problems ». Par exemple, les problèmes d'énumération des dépendances d'inclusion dans les bases de données relationnelles ou les sous-arbres fréquents dans les données XML semi-structurées rentrent dans cette catégorie. Ces exemples montrent que les motifs peuvent être complexes et que les données peuvent être volumineuses et fortement hétérogènes. Dans ce contexte, nous visons à définir des langages déclaratifs de haut niveau (logiques ou algébriques) pour exprimer et représenter les problèmes d'énumérations de motifs intéressants. Puis, nous souhaitons mener une étude en vue de caractériser les sous-classes traitables des problèmes d'énumération de motifs intéressants pour lesquels des algorithmes efficaces en pratique pourraient être conçus. Dans ce contexte, notre ambition est d'établir des liens entre la programmation par contraintes, la fouille de donnée à base de contraintes et l'algorithmique sur les structures discrètes et d'opérer des fertilisations croisées entre ces sous-domaines de l'informatique. D'un point de vue théorique, des propriétés que les motifs devraient vérifier dans un langage donné doivent être identifiées et caractérisées (par exemple monotonicité, maximalité). Nous proposons de définir de nouvelles classes de problèmes pour lesquelles les solutions génériques existent. Les points clés à étudier sont les algorithmes d'énumération sur les structures discrètes ainsi que leur complexité, la puissance d'expression des langages utilisés pour définir des motifs, les prédicats définissant ce qu'est un motif intéressent et le problème de transformations (ou plongement) des motifs dans des structures connues. Par exemple, nous explorerons les transformations d'ensemble de motifs vers des treillis booléen afin d'exploiter de bonnes propriétés algorithmiques de ces treillis. Des données réelles issues de benchmarks internationaux seront utilisées pour évaluer la faisabilité pratique des propositions faites dans ce projet. À notre connaissance, seulement un projet récent au niveau européen a le même positionnement scientifique [75]. Par conséquent, notre projet constitue une excellente occasion pour jouer un rôle important au niveau international dans cette nouvelle tendance de recherche en essayant d'appliquer des techniques issues de la programmation par contraintes à la fouille de données basée sur les contraintes.