\documentclass[
  semhelv    Helvetica
,  a4           A4 paper
]{seminar}

\def\printlandscape{}  % pour sortir en portrait
\slidesmag{1} 
\usepackage{fullpage}

\def\printlandscape{\special{landscape}}     % pour sortir en landscape
\slidesmag{5}

\usepackage{color}

\usepackage[dvips]{graphicx}

\articlemag{1}

%\rotateheaderstrue       % si tu combines slide et slide*

\newcommand{\heading}[1]{%
{\color{blue}\bf\large #1}{\color{yellow}\\\rule{\textwidth}{2pt}}
}

\definecolor{mauve}{rgb}{1,0,1}
\definecolor{cyanp}{rgb}{0,1,1}
\definecolor{new}{rgb}{0.8,0.3,0.4}
\newcommand{\new}[1]{\textcolor{new}{#1}}
\newcommand{\cyanp}[1]{\textcolor{cyanp}{#1}}
\newcommand{\mauve}[1]{\textcolor{mauve}{#1}}
\newcommand{\rouge}[1]{{\color{red}#1}}
\newcommand{\VERT}[1]{{\color{green}#1}}
\newcommand{\bleu}[1]{\textcolor{blue}{$#1$}}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}



\title{
\bl{
Tree pattern matching and subset matching in deterministic
$\mathcal{O}(nlog^3n)$}
}


\author{
Emmanuel Filiot
}


\begin{document}

%------------------------------------------------

\begin{slide}

\maketitle

\hfill
\end{slide}

%---------------------------------------------------

\begin{slide}

\heading{Plan}
1.Definitions \\
2.Overview of the algorithm \\
3.Superimposed code \\
4.Minimum weight problem
\vfill 

\end{slide}

%----------------------------------------------------

\begin{slide}

\heading{Definitions (1)}
\VERT{Tree pattern matching problem} : Given two ordered trees, called the \cyanp{\textit{text}}
and the \cyanp{\textit{pattern}}, find all occurences of the pattern in the text. \\
The pattern is said to occurs at a particular position if placing the pattern
with root at that text position leads to a situation in which each pattern nod
overlaps some text node.
\vfill
\end{slide}
%---------------------------------------------------

\begin{slide}
\heading{Definitions (2)}

\begin{figure}
\begin{center}
\includegraphics[angle=0, width=7cm, height=4cm]{tree.eps}
\end{center}
\end{figure}
\vfill

\end{slide}


%-----------------------------------------------------

\begin{slide}
\heading{Definitions (3)}

\VERT{Subset matching problem} : Given an alphabet $\sum  =[0,\ldots,k-1]$, a
\cyanp{text string} t[0\ldots n-1] and a \cyanp{pattern string} p[0\ldots m-1] such
that $t[i] \subseteq \sum$, $p[j] \subseteq \sum, \forall i=0\ldots n-1, \forall
j=0\ldots m-1$, output a binary array $\mathcal{T}[0\ldots n-m]$ such that
$\mathcal{T}[i]=1$ iff \new{$p[j]\subseteq t[i+j] \forall j=0\ldots m-1$}.
\linebreak

\rouge{Lemma 1} : Tree pattern matching problem can be reduce to Subset
matching problem in $\mathcal{O}(n)$.[CH97]

\vfill

\end{slide}

 %---------------------------------------------

\begin{slide}
\heading{Subset matching problem}
\vfill
\begin{figure}
\begin{center}
\includegraphics[angle=0, width=8cm, height=4cm]{subset.eps}
\end{center}
\end{figure}

\end{slide}

%----------------------------------------------

\begin{slide}
\heading{Overview of the algorithm (1)}
\bl{Notations} : $s=\sum_i |t[i]|+\sum_j |p[j]|$ where $|.|$ denotes the
cardinality. \\
\bl{Hypothesis} : $\bigcup_i t[i]=\bigcup_j p[j]$, $m\leq n\leq 2m$, $s\leq
6m,$ i.e. $s=\mathcal{O}(n)$. \footnote{As pointed out in [CH97], that can be assumed without loss of
  generality (otherwise the problem can be linearly reduced to several subset
  matching subproblems satisfying these properties)}\\
\vfill
\end{slide}

%-----------------------------------------------

\begin{slide}
\heading{Overview of the algorithm (2)}
\rouge{1.} The maximum size of each set of t are minimized by shifting the elements
of sets of both t and p in $\mathcal{O}(nlog^3n)$-time $\rightarrow$
\VERT{Minimum Weight Problem}. \\
\rouge{2.} The sets of t and p are coded, in $\mathcal{O}(nlog^2n)$-time,  into binary vectors of length $\mathcal{O}(log^2n)$
which permit to see if a set is included in another one quickly.
\\ $\rightarrow$ \VERT{Superimposed Codes Problem}.\\
\rouge{3.}The string matching problem is the solved by standard methods based
on convolutions in $\mathcal{O}(nlog^3n)-time$.
\vfill

\end{slide}

%-----------------------------------------------

\begin{slide}
\heading{Superimposed Codes (1)}
\VERT{Data}: $S=S_0,...,S_p \subseteq \mathcal{U}$ .\\
\VERT{Problem}: find \rouge{equal length binary codes} for the elements of each $S_i$ such
that $code(S_i)$, defined as the 'or' of the codes of its elements, does not
contain any code of elements not in $S_i$, i.e. :\\
$\forall e\in \mathcal{U}, \forall S_i\in S$, $e\notin S_i$ implies
that there is at least one 1 in $code(e)$ such that the bit in $code(S_i)$ in
the same position is a zero.\\
\vfill
\end{slide}  

%------------------------------------------------

\begin{slide}
\heading{Superimposed Codes : example}
$S_1=\lbrace a,b,c\rbrace$ \\
$S_2=\lbrace a,b\rbrace$ \\
$S_3=\lbrace b,c\rbrace$ \\
$code(a)\, \,=1\, 1\, 0 $\\
$code(b)\, \,=0\, 0\, 0 $\\
$code(c)\, \,=0\, 1\, 1 $\\
$code(S_1)=1\, 1\, 1 $\\
$code(S_2)=1\, 1\, 0 $\\
$code(S_3)=0\, 1\, 1 $\\

\vfill
\end{slide}

%-------------------------------------------------

\begin{slide} 
\heading{Superimposed Codes (3)}
It can be noticed that $S_i \subseteq S_j$ iff $code(S_i)\leq code(S_j)$, i.e.
$\forall p, code(S_i)_p\leq code(S_j)_p$.\\
\linebreak
So the problem is to build short codes in a fast time. As the length of
the codes is proportional to the set size, the goal of the second problem is
to minimize the sizes of the sets.  \\
\vfill
\end{slide}
%-------------------------------------------------

\begin{slide}
\heading{Minimum Weigth Problem(1)}
\VERT{Motivations} : generate string $t''$ and $p''$ such that all sets in
both $t''$ and $p''$ have \cyanp{small cardinality}, and $p''$ matches $t''$ at
position $i$ iff $p$ matches $t$ at the same position.\\
\VERT{Notation} : $T[a,i]=1$ where $  a=\lbrace a_1,...,a_q\rbrace \subseteq
\mathcal{K}$ and $k\in \lbrace 0,1\rbrace$ iff $T[j,i]=1$ if $j=a_l$ and 0
otherwise.\\
\linebreak As the alphabet $\mathcal{K}$ is finite, it is possible to work
with natural integers, instead of characters.\\

\vfill
\end{slide}

%-------------------------------------------------
\begin{slide}
\heading{Minimum Weigth Problem(2)}
The binary matrix $T[0...k-1,0...n-1]$ and $P[0...k-1,0...m-1]$ are defined as follow :\\
\rouge{$T[a, i]=1$ iff $t[i]=a$} \\
\rouge{$P[a, i]=1$ iff $p[i]=a$} \\

\VERT{Condition 1} : p matches t at position i iff : $\forall j=0...m-1, P[.,j]\leq
T[.,i+j]$
\vfill
\end{slide} 
%-------------------------------------------------
\begin{slide}
\heading{Minimum Weigth Problem(3) : Example}
$k=4$, i.e. $\mathcal{K}=\lbrace 0, ..., 3\rbrace$ \\
$n=5$, $m=3$\\
$t=\lbrace \VERT{1, 2, 3} \rbrace, \lbrace \rouge{1} \rbrace, \lbrace \cyanp{0, 3} \rbrace, \lbrace
\rbrace, \lbrace \bl{0, 2, 3} \rbrace$ \\
$p=\lbrace \VERT{2, 3} \rbrace, \lbrace \rouge{1} \rbrace, \lbrace \cyanp{3} \rbrace$\\
\linebreak
\mbox{
\begin{displaymath}
\textit{T}=
\left( \begin{array}{ccccc}
0 & 0 & \cyanp{1} & 0 & \bl{1} \\  
\VERT{1} & \rouge{1} & 0 & 0 & 0 \\
\VERT{1} & 0 & 0 & 0 & \bl{1} \\
\VERT{1} & 0 & \cyanp{1} & 0 & \bl{1} \\
\end{array} \right)
\end{displaymath}
\begin{displaymath} ,
\textit{P}=
\left( \begin{array}{ccccc}
0 & 0 & 0   \\  
0 & \rouge{1} & 0   \\
\VERT{1} & 0 & 0   \\
\VERT{1} & 0 & \cyanp{1}   \\
\end{array} \right)
\end{displaymath}
}
\\ \linebreak $p$ matches $t$ at position 0 .
\vfill

\end{slide}


%-------------------------------------------------
\begin{slide}
\heading{Minimum Weigth Problem (4)}
The \rouge{weight} of a column is the sum of its elements. \\
So the weights of both $T$ and $P$ correspond to the set sizes of both $T$ and
$P$.\\
\VERT{Fact} : Condition 1 remains invariant when the corresponding rows of
both $T$ and $P$ are shifted by the same number of positions.\\

So it is possible to reduce the number of ones in each column of $T$, i.e. the set sizes.

\end{slide}

\vfill

%-------------------------------------------------------

\begin{slide}
\heading{Minimum Weight Problem (5)}
\mbox{
\begin{displaymath}
\textit{T} =
\left( \begin{array}{ccccc}
0 & 0 & \cyanp{1} & 0 & \bl{1} \\  
\VERT{1} & \rouge{1} & 0 & 0 & 0 \\
\VERT{1} & 0 & 0 & 0 & \bl{1} \\
\VERT{1} & 0 & \cyanp{1} & 0 & \bl{1} \\
\end{array} \right)
\end{displaymath}
\begin{displaymath} ,
 \textit{P} =
\left( \begin{array}{ccccc}
0 & 0 & 0   \\  
0 & \rouge{1} & 0   \\
\VERT{1} & 0 & 0   \\
\VERT{1} & 0 & \cyanp{1}   \\
\end{array} \right)
\end{displaymath}
} \\

\mbox{
\begin{displaymath}
\textit{T''}=
\left( \begin{array}{ccccc}
0 & \cyanp{1}& 0 &  \bl{1} & 0 \\  
0 & \VERT{1} & \rouge{1} & 0 & 0  \\
\VERT{1} & 0 & 0 & 0 & \bl{1} \\
\VERT{1} & 0 & \cyanp{1} & 0 & \bl{1} \\
\end{array} \right)
\end{displaymath}
\begin{displaymath} ,
\textit{P''}=
\left( \begin{array}{ccccc}
0 & 0 & 0   \\  
0 & 0 & \rouge{1}    \\
\VERT{1} & 0 & 0   \\
\VERT{1} & 0 & \cyanp{1}   \\
\end{array} \right)
\end{displaymath} 
}
\mbox{
$t''=\lbrace \VERT{2, 3} \rbrace, \lbrace \cyanp{0}, \VERT{1} \rbrace, \lbrace
\rouge{1},\cyanp{3} \rbrace, \lbrace \bl{0} \rbrace, \lbrace \bl{2, 3} \rbrace$ 
$p''=\lbrace \VERT{2,3} \rbrace, \lbrace \rbrace, \lbrace \rouge{1},\cyanp{3} \rbrace$
}
\vfill

\end{slide}

%-----------------------------------------------------------------------------
\begin{slide}

\heading{Minimum Weight Problem : Definition}

\VERT{Definition} : Given positive integers $b$,$d$ and a binary matrix
$T[0...k-1,0...n-1]$ containing at most $b$ ones, find (if possible) $k$ positive
integers $l_0,\ldots,l_{k-1} \in \lbrace 0,\ldots,n-1\rbrace$ such that the matrix
$T''$ obtained by shifting the ith row of $T$ by $l_i$ positions has the property
that each of its columns contained at most $d$ ones.

\\ \linebreak
\VERT{Theorem} : Minimum Weight Problem with $b=n$, and $d=\mathcal{O}(n)$ can
be solved in deterministic $\mathcal{O}(nlog^3n)$-time.

\vfill
\end{slide}

%--------------------------------------------------------------------------
\begin{slide}
\heading{Conclusion}
\begin{itemize}

\item a fast algorithm to solve Tree Pattern Matching Problem
\item application in each field which uses tree structures, for example Web
  information extraction

\end{itemize} 
\vfill
\end{slide}

%----------------------------------------------------------------------
\begin{slide}
\heading{Bibliography}
\begin{itemize}

\item R.Cole, R.Hariharan, P.Indyk, "Tree Pattern Matching and Subset Matching
  in Deterministic $\mathcal{O}(nlog^3m)$-Time". \textit{In SODA: ACM
  Symposium on Discrete Algorithms}. 
\item $[$CH97$]$ R.Cole, R.Hariharan, "Tree Pattern Matching and Subset Matching in
Randomized $\mathcal{O}(nlog^3m)$ Time", \textit{Proc. STOC'97}, to appear. 
\item P.Indyk, "Deterministic Superimposed Coding with Application to Pattern
  Matching", \textit{Proc. FOCS'97}.
\end{itemize} 
\vfill

\end{slide}

\end{document}
