% A Readymade beamer presentation template
% Version 1.1
% Relase date: May 2, 2010
% Released at http://www.stattler.com
% by Rifat Jahan

\documentclass{beamer}
%\usecolortheme[named=green]{structure}
\mode<presentation> {
%\usetheme{Madrid} % My favorite!
%\usetheme{Boadilla} % Pretty neat, soft color.
%\usetheme{default}
%\usetheme{Warsaw}
%\usetheme{Bergen} % This template has nagivation on the left
\usetheme{Frankfurt} % Similar to the default with an extra region at the top.
%\usecolortheme{seahorse} % Simple and clean template
%\usetheme{Darmstadt} % not so good
% Uncomment the following line if you want page numbers and using Warsaw theme
% \setbeamertemplate{footline}[page number]
%\setbeamercovered{transparent}
\setbeamercovered{invisible}
% To remove the navigation symbols from the bottom of slides%
\setbeamertemplate{navigation symbols}{}
}

\usepackage{xcolor,colortbl}
\definecolor{mycolor1}{RGB}{181,165,243}
\definecolor{mycolor2}{RGB}{105,125,241}
\newcommand{\done}{\cellcolor{teal}done}  %{0.9}
\newcommand{\hcyan}[1]{{\color{teal} #1}}
\usepackage{wrapfig}
\usepackage{subfig}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{etex}
\usepackage[style=numeric-comp]{biblatex}
\usepackage[lined,boxed,commentsnumbered,ruled,vlined,
linesnumbered]{algorithm2e }
\usepackage{slashbox}

\usepackage{graphicx}
%\usepackage{bm} 
% For typesetting bold math (not \mathbold)
%\logo{\includegraphics[height=0.6cm]{yourlogo.eps}}
%
\title[Improving Textual Merge Result]{Improving Textual Merge Result}
%
\author[Mehdi Ahmed-Nacer]{Mehdi Ahmed-Nacer, Pascal Urso
and François Charoy}
\institute[LORIA]
{
University of Lorraine - LORIA Laboratory - France \\
\medskip
{\emph{mehdi.ahmed-nacer@loria.fr}} \\
\medskip
{This work is
partially funded by the french national research programs {\sc ConcoRDanT.}} \\
% \medskip
% {ICDAR 2013}
}
\date{}

% logo of my university
\titlegraphic{
\includegraphics[width=2cm]{images/ul.png}\hspace*{2.2cm}~%
\includegraphics[width=2cm]{images/loria.jpg}\hspace*{2.2cm}~%
\includegraphics[width=2cm]{images/Logo-ANR.jpg}
}

\begin{document}
%
\begin{frame}
\titlepage
\end{frame}

%==================================================================
%==================================================================
%==================================================================
\section{Introduction}

\subsection{Context}
\begin{frame}
\frametitle{Context}

\begin{columns}[t]
  \begin{column}{6cm}

\begin{itemize}
\item Synchronous collaboration mode
\begin{itemize}

\item{GoogleDrive}
\item{Etherpad}  
\item{Coward ...}
\end{itemize}
\end{itemize}
\end{column}
  
\begin{column}{5cm}
\begin{figure}[H]
  \subfloat{
 \includegraphics[width=2.5cm]{images/GoogleDrive.png}}
  \subfloat{
 \includegraphics[width=2.5cm]{images/etherpad.png}}
 \end{figure}
  \end{column}
 \end{columns} 


\begin{columns}[t]
  \begin{column}{7cm}

\begin{itemize}

\item Asynchronous collaboration mode
\begin{itemize}
\item{Git}
\item{SVN}  
\item{Wikipedia ...}
\end{itemize}
\end{itemize}
  \end{column}
  
  \begin{column}{5cm}
\begin{figure}[H]
  \subfloat{
 \includegraphics[width=2.5cm]{images/Git.png}}
  \subfloat{
 \includegraphics[width=2.5cm]{images/wikipedia-logo.jpg}}
 \end{figure}
  \end{column}
 \end{columns} 

\begin{block}{}
 We focused only on asychronous collaboration and textual merge
\end{block}
\end{frame}


%------------------------------------------------
\subsection{Contribution}
\begin{frame}

\begin{enumerate}
 \item Methodology to evaluate the merge quality
 \item Observing different patterns of collaboration
 \item Analyze the common case that creates a conflict
 \item Suggest a solution to solve the conflict 
    \begin{itemize}
     \item Using potential algorithms
    \end{itemize}
  \item Compare our approach with traditional tools used for merging
\end{enumerate}

\begin{block}{Goal}
Improve the merge quality and minimise the user effort. 
\end{block}

\frametitle{Contribution}
\end{frame}

%------------------------------------------------
\subsection{Basic Idea}
\begin{frame}

\begin{itemize}
 \item Replay the same collaboration as git history
 \item Deploy a merge tool
 \item Inspired by algorithms that merge correctly
 \item Avoid conflicts and satisfy users

\end{itemize}

\frametitle{Basic Idea}
\end{frame}
%------------------------------------------------
\section{Merge Management}

\subsection{State-based approach}
 \begin{frame}
 \frametitle{State-based approach}
\begin{itemize}
 \item The usual tool used for synchronization and merging is {\tt diff3}
  \item The document is managed as a \underline{$state$}
\end{itemize}

\begin{columns}[t]
  \begin{column}{7.5cm}
\begin{itemize}
 \item During merge procedure
\begin{enumerate}


\item Find the maximum matchings
\begin{itemize}
\item Origin Vs modified documents
\end{itemize}

\item Examine where the origin differs from the other
\begin{itemize}
\item In the same part of the document ?
\end{itemize}

\item Detect if the document conflicts
\item Return the result to the users with markers
\end{enumerate}
\end{itemize}

  \end{column}
  
  \begin{column}{5cm}
\begin{figure}[H]
 \includegraphics[width=5cm]{images/diff.pdf}
 \end{figure}
  \end{column}
 \end{columns}
 \end{frame}

\subsection{Operation-based approach}
 \begin{frame}
 \frametitle{Operation-based approach}
\begin{itemize}
 \item Operation-based algorithms integrate correctly the operations
: {\tt OT} and {\tt CRDT}
 \item The document is managed as a set of \underline{$operations$}
 \item Operation for each line (granularity = line)
\end{itemize}

\begin{columns}[t]
  \begin{column}{6cm}
\begin{itemize}
 \item During merge procedure in OT
\begin{enumerate}

\item Find the concurrent operations
\item Operation is Transformed according to the concurrent ones
\item Executed on the local copy
\end{enumerate}
\end{itemize}

  \end{column}
  
  \begin{column}{7cm}
\begin{figure}[H]
 \includegraphics[width=6.5cm]{images/OT.pdf}
 \end{figure}
  \end{column}
 \end{columns}



 \end{frame}
%==================================================================
\section{Methodology}

\subsection{Framework}
\begin{frame}
\frametitle{Framework}

\begin{columns}[t]
  \begin{column}{7cm}
\begin{itemize}
\item Replays the history of Git repositories
  \begin{itemize}
  \item By diff3 and op-based algorithms
  \end{itemize}
\item Transforms the state of the document to the set of operations
\item Compares the merge result
\begin{itemize}
  \item Computes the metrics
  \end{itemize}
\end{itemize}
  \end{column}
  
\begin{column}{5cm}
\begin{figure}[H]
\begin{center}
 { \includegraphics[width=5.2cm]{images/merge.png}}
\end{center}


 \end{figure}
  \end{column}
 \end{columns} 

\begin{block}{Metrics}
\begin{enumerate}
 \item{Merge blocks:} Number of different blocks in merged documents
 \item{Merge lines:} Number of lines in the blocks 
\end{enumerate}

\end{block}

\end{frame}
%------------------------------------------------
\subsection{Observing Collaboration}
\begin{frame}
\frametitle{Observing Collaboration \\
1- Concurrent consecutive modifications}
\begin{center}
 { \includegraphics[width=0.95\textwidth]{images/diffVsOp.pdf}}
\end{center}



\end{frame}

\subsection{Observing Collaboration}
\begin{frame}
\frametitle{Observing Collaboration \\
2- Accidental Clean Merge (ACM)}
\begin{center}
 {\includegraphics[width=0.6\textwidth]{images/cleanMerge.pdf}}
\end{center}

\end{frame}


\subsection{Observing Collaboration}
\begin{frame}
\frametitle{Observing Collaboration \\
3- Undo/Redo}
\begin{center}
 { \includegraphics[width=0.7\textwidth]{images/undo_redo.pdf}}
\end{center}
\end{frame}

%------------------------------------------------
\subsection{Adapted Merge}
\begin{frame}
\frametitle{Adapted Merge \\
1- Case of Undo/Redo}
\begin{itemize}
 \item Delete operations are considered as $undo$ of insertions
 \item Deleted elements are marked as Tombstone \footnote{\tiny G. Oster et al.
Tombstone transformation functions for ensuring consistency in
collaborative editing systems. CollaborateCom 2006}

 \item Each operation has a visibility degree
\begin{itemize}
\item Insertion operation increases the visibility degree
\item Delete operation decreases the visibility degree
\item The line is visibile if and only if visibility degree $>$ 0
\end{itemize}
\item Same insertion of deleted element at the same \\
position $\rightarrow$ Redo operation
\end{itemize}

\begin{center}
{
\scalebox{0.55}{
\begin{algorithm}[H]
%\SetLine
\KwIn{The content and the position on the document}
\KwOut{operation}

\eIf{((getDoc(pos).visibility = false) and (getDoc(pos) == content)} {
 return redo(position, content); 
}
{
  return insert(position, content);
}
\caption{Redo Algorithm}
\end{algorithm}}
}
\end{center}

\end{frame}

\subsection{Adapted Merge}
\begin{frame}
\frametitle{Adapted Merge \\
2- Case of Accidental Clean Merge (ACM)}
\begin{itemize}
 \item Detect the ACM case during the transformation procedure
 \item Two concurrent insertions of the same element in the same position
$\rightarrow$ $noop$ operation
\end{itemize}

\begin{center}
{
\scalebox{0.65}{
\begin{algorithm}[H]
\KwIn{operations to transform : op1 and p2}
\KwOut{operation applied on the document : op}
Let $c_1$ and $c_2$ respectively the content of op1 and op2 \\
Let $t_1$ and $t_2$ respectively the type of op1 and op2  \\
Let $p_1$ and $p_2$ respectively the position of op1 and op2 \\

\If{ ($t_1$ $=$ insert) and ($t_2$ = insert)} {
\eIf{(c1$=$c2) and (p1$=$p2)}{
return noop();
}{
\eIf{(p1 $>$ p2) or (p1$=$p2 and \\ HashCode(c1) $>$ HashCode(c2))}{
return insert(c1, p1+1,$Site_i$);
}{ return insert(c1, p1,$Site_i$);}
} 
}
\caption{Transform(op1, op2)}
\end{algorithm}}
}
\end{center}


\end{frame}

%==================================================================
\section{Experiment}

\subsection{Description of Logs}
\begin{frame}
\begin{itemize}
 \item The most popular project from GitHub
 \item The most active project from Gitorious
\end{itemize}

\begin{table}[htb]
\label{table:features}
\centering
 \begin{tabular}{|c|c|c|c|}
  \hline
\backslashbox{Project}{\kern-1em Features} & {\sc ACM}
&{\sc undo} & {\sc redo}\\ 
 \hline
backbone & 271 & 1357 & 1137\\ 
 \hline
bootstrap & 563 & 7210 & 3957\\ 
 \hline
d3 & 7 & 19877 & 218\\ 
 \hline
Git & 1272 & 42734 & 1614\\ 
 \hline
Gitorious & 750 & 932 & 513\\ 
 \hline
jquery & 213 & 1947 & 1432\\ 
 \hline
rails & 426 & 5329 & 16172\\ 
 \hline
status & 2297 & 9060 & 6352\\
 \hline
 \end{tabular}
\caption{ACM and Undo/Redo in git repositories}
\end{table}
\frametitle{Description of Logs}
\end{frame}

\subsection{Evaluated Algorithms}
\begin{frame}
\frametitle{Evaluated Algorithms}

\begin{itemize}
 \item Compute "{\tt merge blocks}" and "{\tt merge lines}"
\begin{enumerate}
 \item State-Based: $Diff3$
 \item Operation-Based
  \begin{itemize}
 \item OT algorithm called $TTF$
 \item Correct CM and Undo/Redo:  $CMUndo$ algorithm
 \item Correct only CM:  $CM$ algorithm
  \end{itemize}
\end{enumerate}

 \item $Diff3$ as reference (=100\%)
\end{itemize}


\end{frame}

\subsection{Results: Merge Blocks}
\begin{frame}
\frametitle{Results: Merge Blocks}
\includegraphics[width=1.1\textwidth]{images/block2.pdf}
\end{frame}

\subsection{Results: Merge Lines}
\begin{frame}
\frametitle{Results: Merge Lines}
\includegraphics[width=1.1\textwidth]{images/line2.pdf}
\end{frame}

\subsection{Statistical significance}
\begin{frame}
\frametitle{Statistical significance}
%\includegraphics[width=1.1\textwidth]{images/total.pdf}
\begin{itemize}
 \item Determined by calculating the probability of error {\tt p-value}
 \item Significance level is often $\alpha=0.05$
 \item Difference is significant if {\tt p-value}$<$ $\alpha$
\end{itemize}

\begin{table}[htb]
\label{table:features}
\centering
 \begin{tabular}{|c|c|c|c|}
  \hline
 {\sc } & {\sc TTF} &{\sc CM} & {\sc CMUndo}\\ 
 \hline
Diff3 &  0.302 &  0.003 & 0.002\\ 
 \hline
TTF & - & 0.005 & 0.004\\ 
 \hline
CM & - & - & 0.004\\ 
 \hline
 \end{tabular}
\caption{One-Way Anova}
\end{table}

\end{frame}

%==================================================================
\section{Conclusion and perspectives}

\subsection{Conclusion and perspectives}
\begin{frame}
\frametitle{Conclusion and perspectives}

\begin{block}{Conclusion}
 \begin{itemize}
 \item Propose a methodology to evaluate merge quality
 \item Observe the collaboration and detect the real conflicts
 \item Suggest a solution to avoid some specific conflicts
 \item Run experiments on real data
 \item Improve text merge results  
\end{itemize}
\end{block}

\begin{block}{Perspectives}
 \begin{itemize}
  \item Extend our tool to capture file system modifications
  \item Run experiment on file systems with different policies.
 \end{itemize}

 
\end{block}




\end{frame}

\subsection{}
\begin{frame}
\frametitle{}
\begin{center}
 {Thank you for your attention}
\end{center}


\end{frame}

% End of slides
\end{document} 
