Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > Les rapports de recherche du LIFO en 2014

 English Version



Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Email: contact.lifo
Tel: +33 (0)2 38 41 99 29
Fax: +33 (0)2 38 41 71 37



Accéder aux Rapports de l'année : 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018

Les rapports de recherche du LIFO en 2014


RR-2014-01 Scalable and Skew-insensitive Algorithm for Join Operations using Map/Reduce Model
Mostafa Bamha and Frédéric Loulergue
Date : 2014-01-15
Résumé Télécharger

RR-2014-02 Towards more Precise Rewriting Approximations (full version)
Yohan Boichut, Jacques Chabin and Pierre Réty
Date : 2014-10-06
Résumé Télécharger

RR-2014-03 Unsupervised Dependency Parsing, a new PCFG
Marie Arcadias, Guillaume Cleuziou, Edmond Lassalle, Christel Vrain
Date : 2014-09-26
Résumé Télécharger


Résumés des rapports de recherche


RR-2014-01 Scalable and Skew-insensitive Algorithm for Join Operations using Map/Reduce Model
Mostafa Bamha and Frédéric Loulergue
Résumé : For over a decade, Map/Reduce has become a prominent programming model to handle vast amounts of raw data in large scale systems. This model ensures scalability, reliability and availability aspects with reasonable query processing time. However these large scale systems still face some challenges: data skew, task imbalance, high disk i/o and redistribution costs can have disastrous effects on performance. In this paper, we introduce MRFA-Join algorithm: a new Frequency Adaptive algorithm based on Map/Reduce Programming model and distributed histograms for join processing on large-scale datasets. A cost analysis of this algorithm shows that our approach is insensitive to data skew and ensures perfect balancing properties during all stages of join computation. Performances have been experimented on Grid'5000 infrastructure.
Mot(s) Clé(s) : Join operations, Data skew, Map/Reduce model, Hadoop framework

RR-2014-02 Towards more Precise Rewriting Approximations (full version)
Yohan Boichut, Jacques Chabin and Pierre Réty
Résumé : To check a system, some verification techniques consider a set of terms I that represents the initial configurations of the system, and a rewrite system R that represents the system behavior. To check that no undesirable configuration is reached, they compute an over-approximation of the set of descendants (successors) issued from I by R, expressed by a tree language. Their success highly depends on the quality of the approximation. Some techniques have been presented using regular tree languages, and more recently using non-regular languages to get better approximations: using context-free tree languages on the one hand, using synchronized tree languages on the other hand. In this paper, we merge these two approaches to get even better approximations: we compute an over-approximation of the descendants, using synchronized-context-free tree languages expressed by logic programs. We give several examples for which our procedure computes the descendants in an exact way, whereas the former techniques compute a strict over-approximation.
Mot(s) Clé(s) : term rewriting, tree languages, logic programming, reachability.

RR-2014-03 Unsupervised Dependency Parsing, a new PCFG
Marie Arcadias, Guillaume Cleuziou, Edmond Lassalle, Christel Vrain
Résumé : L’apprentissage de dépendances est une tâche consistant à établir, à partir des phrases d’un texte, un modèle de construction d’arbres traduisant une hiérarchie syntaxique entre les mots. Nous proposons un modèle intermédiaire entre l’analyse syntaxique complète de la phrase et les sacs de mots. Il est basé sur une grammaire stochastique hors-contexte se traduisant par des relations de dépendance entre les catégories grammaticales d’une phrase. Les résultats expérimentaux obtenus sur des benchmarks attestés dépassent pour cinq langues sur dix les scores de l’algorithme de référence DMV, et pour la première fois des scores sont obtenus pour le français. La très grande simplicité de la grammaire permet un apprentissage très rapide, et une analyse presque instantanée.
Mot(s) Clé(s) : Natural Language Processing, syntactic dependency trees, unsupervised learning of grammars, Inside-Outside, CYK, Context-free grammars