wiki:WikiStart

PEPS FaSciDo HYDrATA

Présentation du projet

Le projet HYDrATA s'inscrit dans les axes 4 et 5 de  l'Appel à projets PEPS INS2I/INSMI 2015 : Fondements et Applications de la Science des Données (FaSciDo). Il se situe à l'interface entre de deux domaines de l'Informatique : la fouille de données et l'analyse probabiliste d'algorithmes. D'un côté, l'extraction de connaissances à base de motifs (Pattern Mining) s'appuie sur une grande variété d'algorithmes pour extraire de l'information sous forme de motifs des bases de données. De l'autre côté, l'analyse probabiliste d'algorithmes, centrée sur la combinatoire analytique, est un domaine typique de l'Informatique Mathématique qui met en évidence le comportement générique des algorithmes et non les comportements pathologiques comme le pire des cas. Ces deux domaines collaborent encore peu mais ils partagent un objet essentiel (et très présent), les hypergraphes. L'idée originale du projet est de réunir les deux communautés autour de cet objet commun, de diffuser la culture entre ces domaines et de renforcer les timides collaborations existantes. Le projet se construit autour de quatre axes : (1) identifier les algorithmes et les propriétés des hypergraphes qui interviennent en fouille de données, (2) proposer des modèles aléatoires d'hypergraphes réalistes vis-à-vis des applications identifiées, (3) effectuer des analyses probabilistes en se basant sur les modèles aléatoires, (4) utiliser les résultats obtenus pour améliorer ou concevoir de nouveaux algorithmes adaptés aux problèmes identifiés.

Description précise du projet: HYDrATA-LhoteLoick.pdf

Membres du projet

Nom Titre e-mail Unité de recherche
Alexandre Bazin Post-Doc alexandre.bazin _AT_ isima.fr LIMOS UMR 6158
Olivier Bodini PR olivier.bodini _AT_ lipn.univ-paris13.fr LIPN UMR 7030
Julien Clément CR CNRS julien.clement _AT_ unicaen.fr GREYC UMR 6072
Bruno Crémilleux PR bruno.cremilleux _AT_ unicaen.fr GREYC UMR 6072
Bertrand Cuissart MCF bertrand.cuissart _AT_ unicaen.fr GREYC UMR 6072
Julien David MCF julien.david _AT_ lipn.univ-paris13.fr LIPN UMR 7030
Élie De Panafieu Ingénieur de recherche depanafieuelie _AT_ gmail.com Bell Labs France, Nokia
Richard Emilion PR richard.emilion _AT_ univ-orleans.fr MAPMO UMR 7349
Loïck Lhote MCF loick.lhote _AT_ ensicaen.fr GREYC UMR 6072
Arnaud Mary MCF mary.univ.lyon1 _AT_ gmail.com LBBE UMR 5558
Vlady Ravelomanana PR vlad _AT_ liafa.jussieu.fr LIAFA UMR 7089
François Rioult MCF francois.rioult _AT_ unicaen.fr GREYC UMR 6072
Arnaud Soulet MCF arnaud.soulet _AT_ univ-tours.fr LI, EA 6300,Tours
Brigitte Vallée DR CNRS brigitte.vallee _AT_ unicaen.fr GREYC UMR 6072

Publications 2016 associées au projet

  • Ny Aina Andriambolamalala, Vlady Ravelomanana, An Optimal Randomized Broadcasting Algorithm in Radio Networks with Collision Detection, soumis à  https://arxiv.org/abs/1701.01587
  • Valérie Berthé, Loïck Lhote, Brigitte Vallée, Analysis of the Brun Gcd Algorithm, ISSAC '16, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pages 87-94, ACM New York, NY, USA, 2016.
  • Valérie Berthé, Loïck Lhote, Brigitte Vallée, A probabilistic analysis of the plain multiple gcd algorithm, Journal of Symbolic Computation, Volume 74, May–June 2016, Pages 425–474.
  • Olivier Bodini, Julien David, Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and Applications, Proceedings de Algorithms and Discrete Applied Mathematics - 2nde International Conference, CALDAM’16,Thiruvanthapuram , India, 18-20 février, 2016.
  • Élie de Panafieu, Counting connected graphs with large excess, International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2016
  • Élie de Panafieu, Lander Ramos, Graphs with degree constraints, Proceedings of the Meeting on Analytic Algorithmics and Combinatorics ANALCO’16, pages 34-45
  • Marc Noy, Rasendrahasina Vonjy, Ravelomanana Vlady, Rué Juan José, Isolated cycles of critical random graphs, Proceedings de ANALCO 2017, pages 46-55.
  • Rasendrahasina Vonjy, Rasoanaivo Andry, Ravelomanana Vlady, The Maximum Block Size of Critical Random Graphs, Proceedings de AofA'16, version journal soumise.
  • Arnaud Soulet, François Rioult, Exact and Approximate Minimal Pattern Mining, Advances in Knowledge Discovery and Management, Volume of the series Studies in Computational Intelligence, pages 61-81

Publications 2015 associées au projet

  • Olivier Bodini, Jérémie Lumbroso, Nicolas Rolin, Analytic Samplers and the Combinatorial Rejection Method, Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, San Diego, USA, pp. 40-50, 2015
  • Eda Cesaratto, Brigitte Vallée, Gaussian Distribution of Trie Depth for Strongly Tame Sources. Combinatorics, Probability & Computing 24(1): 54-103 (2015)
  • Julien Clément, Jim Fill, Thu Hien Nguyen Thi and Brigitte Vallée, Towards a realistic analysis of the QuickSelect? algorithm, Theory of Computing Systems, ed. Anca Muscholl and Martin Dietzfelbinger, DOI 10.1007/s00224-015-9633-5
  • Julien Clément, Thu Hien Nguyen Thi, Brigitte Vallée, Towards a Realistic Analysis of Some Popular Sorting Algorithms, Combinatorics, Probability & Computing 24(1): 104-144 (2015)
  • Julien David, Loïck Lhote, Arnaud Mary, François Rioult, An Average Study of Hypergraphs and their minimal transversals, Theoretical Computer Science Volume 596, 6 September 2015, Pages 124–141
  • Élie de Panafieu, Enumeration and structure of inhomogeneous graphs, Proceedings of the International Conference on Formal Power Series and Algebraic Combinatorics FPSAC 2015, 12 pages (presentation d’un poster à FPSAC 2015).

Rencontres organisées

Deux rencontres ont été organisées en 2015 puis en 2016.

Journées du 6 et 7 juin 2016 (à Paris, à l'IRIF)

Lundi 6 juin:

  • 10h00-10h30: accueil et présentation des membres
  • 10h30-12h00: Elie de Panafieu (Bell Labs, Paris) - Counting connected graphs with large excess
  • 14h00-15h30: Vlady Ravelomanana (IRIF, Paris 7) - Autour des hypergraphes
  • 15h45-17h15: Richard Emilion (MAPMO, Orléans) - Contextes aléatoires et nombre moyens de fermés

Mardi 7 juin(Matin commun avec le PEPS Préfute)

  • 09h30-10h30: Alexandre Bazin (LIMOS, ISIMA, Clermont-Ferrand)- Base minimale d'implications et traverses minimales
  • 10h30-11h00: questions et pause
  • 11h00-12h00: Elias Egho (Orange Lab) - Vers une mesure de similarité pour les séquences complexes
  • 14h00- : présentation des membres absents la veille, discussions sur le projet, présentation de problèmes ouverts, …

Journées du 8 et 9 décembre 2016 (à Caen, au GREYC)

Jeudi 8 décembre (salle S3-351, bat. Sciences 3, Campus 2, au GREYC):

  • 10h-11h30 : Alexandre Bazin et Olivier Bodini - Résultats autour des motifs fermées/pseudo-fermés
  • 13h30-15h : Bamba Kane - Classification de règles d'associations
  • 15h30-17h00: Elie de Panafieu - Graphes à sous-graphes marqués.

Vendredi 9 décembre (Salle S3-044, bat. Sciences 3, Campus 2, rez de chaussée):

  • 10h: HDR de Loïck Lhote - Exemples d’analyses d’algorithmes en Arithmétique, Théorie de l’Information et Fouille de Données

Journées du 30 novembre, 1 et 2 décembre (à Paris, au LIPN)

Lundi 30 novembre

  • 12h: Déjeuner
  • 14h- 16h: Olivier Bodini: à propos des DAG
  • 16h- 16h30: Pause
  • 16h30 - 18h30: Elie De Panafieu: Expansion asymptotique des graphes connexes à grand excès
  • 19h30 - Diner

Mardi 1 décembre:

  • 9h30 - 10h: accueil
  • 10h - 12h: François Rioult: Algorithme de Fredman et Kachiyan, motifs, matroides,…
  • 12h: Déjeuner
  • 14h- 16h: Arnaud Mary: Algorithmes d'extraction de traverses
  • 16h- 16h30: Pause
  • 16h30 - 18h: Discussions sur la fin de projet

Mercredi 2 décembre:

  • Groupes de travail

Journées des 29 et 30 juin 2015 (à Caen, au GREYC)

Lundi 29 juin:

  • Déjeuner
  • 14h - 14h30: accueil et présentation des membres
  • 14h30 - 15h : Loïck Lhote - Un point de vue sur le projet
  • 15h - 16h : François Rioult - Hypergraphes et Fouille de Données
  • 16h - 16h30: Pause
  • 16h30 - 17h30: Elie de Panafieu - Hypergraphes inhomogènes et Fouille de données
  • 17h30 - 18h30: Alain Bretto - Problématiques autour des hypergraphes
  • 19h30 Diner

Mardi 30 juin:

  • 9h00 - 10h00: Julien David - Analyse en moyenne sur les traverses minimales d'hypergraphes
  • 10h00 -11h00: Olivier Bodini - Génération aléatoire de Boltzmann et DAG
  • 11h00-11h30: Discussions autour du projet
  • 11h45-12h45: Séminaire Algo avec Elie de Panafieu - énumération des instances satisfaites ou satisfaisables de problèmes de satisfaction de contraintes
  • Repas

Problèmes ouverts

Une page dédiée aux problèmes ouverts se trouve ici