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 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
Abstract Download
RR-2014-02
Towards more Precise Rewriting Approximations (full version)
Yohan Boichut, Jacques Chabin and Pierre Réty
Date : 2014-10-06
Abstract Download
RR-2014-03
Unsupervised Dependency Parsing, a new PCFG
Marie Arcadias, Guillaume Cleuziou, Edmond Lassalle, Christel Vrain
Date : 2014-09-26
Abstract Download
Abstracts of Research Reports
RR-2014-01 Scalable and Skew-insensitive Algorithm for Join Operations using Map/Reduce Model
Mostafa Bamha and Frédéric Loulergue
Abstract : 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.
Keywords : 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
Abstract : 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.
Keywords : term rewriting, tree languages, logic programming, reachability.
RR-2014-03 Unsupervised Dependency Parsing, a new PCFG
Marie Arcadias, Guillaume Cleuziou, Edmond Lassalle, Christel Vrain
Abstract : Dependency learning aims at building a model that allows transforming textual sentences into trees representing a syntactical hierarchy between the words of the sentence. We present an intermediate model between full syntactic parsing of a sentence and bags of words. It is based on a very light probabilistic context free grammar, allowing to express dependencies between the words of a sentence. Our model can be tuned a little depending on the language. Experimentally, we were able to surpass the scores of the DMV reference on attested benchmarks for five over ten languages, such as English, Portuguese or Japanese. We give the first results on French corpora. Learning is very fast and parsing is almost instantaneous.
Keywords : Natural Language Processing, syntactic dependency trees, unsupervised learning of grammars, Inside-Outside, CYK, Context-free grammars