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

Lifo > LIFO Research Report for Year 2015

 Site en Français



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 70 11
Fax: +33 (0)2 38 41 71 37



Go to Research Reports of Year : 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017

LIFO Research Report for Year 2015


RR-2015-01 Scalability and Optimisation of GroupBy-Joins in MapReduce
Mohamad Al Hajj Hassan and Mostafa Bamha
Date : 2015-03-18
Abstract Download

RR-2015-02 Over-Approximating Terms Reachable by Context-Sensitive Rewriting
Nirina Andrianarivelo and Pierre Réty
Date : 2015-07-16
Abstract Download

RR-2015-03 Synchronized Tree Languages for Reachability in Non-right-linear Term Rewrite Systems (full version)
Y. Boichut, V. Pelletier and P. Réty
Date : 2015-10-23
Abstract Download


Abstracts of Research Reports


RR-2015-01 Scalability and Optimisation of GroupBy-Joins in MapReduce
Mohamad Al Hajj Hassan and Mostafa Bamha
Abstract : For over a decade, MapReduce has become the leading programming model for parallel and massive processing of large volumes of data. This has been driven by the development of many engines and frameworks such as Spark, Pig, Hive, facilitating data analysis on large-scale systems. However, these frameworks still remain vulnerable to communication costs, data skew and tasks imbalance problems. This can have a devastating effect on the performance and on the scalability of these systems, more particularly when treating GroupBy-Join queries of large datasets. In this paper, we present a new GroupBy-Join algorithm allowing to reduce communication costs considerably while avoiding data skew effects. A cost analysis of this algorithm shows that our approach is insensitive to data skew and ensures perfect balancing properties during all stages of GroupBy-Join computation even for highly skewed data. These performances have been confirmed by a series of experimentations.
Keywords : Join and GroupBy-join operations, Data skew, MapReduce programming model, Distributed file systems, Hadoop framework, Apache Pig Latin

RR-2015-02 Over-Approximating Terms Reachable by Context-Sensitive Rewriting
Nirina Andrianarivelo and Pierre Réty
Abstract : For any left-linear context-sensitive term rewrite system and any regular language of ground terms I, we build a finite tree automaton that recognizes a superset of the descendants of I, i.e. of the terms reachable from I by context-sensitive rewriting.
Keywords : context-sensitive rewriting, reachability, tree automaton.

RR-2015-03 Synchronized Tree Languages for Reachability in Non-right-linear Term Rewrite Systems (full version)
Y. Boichut, V. Pelletier and P. Réty
Abstract : Over-approximating the descendants (successors) of an initial set of terms under a rewrite system is used in reachability analysis. The success of such methods depends on the quality of the approximation. Regular approximations (i.e. those using finite tree automata) have been successfully applied to protocol verification and Java program analysis. In KochemsO11,BoichutRTA13, non-regular approximations have been shown more precise than regular ones. In BoichutRTA13Patch (fixed version of BoichutRTA13), we have shown that non-regular sound over-approximations using synchronized tree languages can be computed for left-and-right-linear term rewriting systems (TRS), and not for left-linear ones as claimed initially in BoichutRTA13. In this paper, we present two new contributions extending BoichutRTA13Patch. Firstly, we show how to compute at least all innermost descendants for any left-linear TRS. Secondly, a procedure is introduced for computing over-approximations independently of the applied rewrite strategy for any left-linear TRS.
Keywords : tree languages, term rewriting, reachability analysis.