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 2018
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.