\documentclass[a4,10pt]{article} 
\usepackage{graphicx}  
\usepackage[a4paper,top=2cm,bottom=2cm,left=2cm,right=2cm]{geometry}
\usepackage{ecmlpkdd2012}

% --Set font to Helvitica
%\usepackage{helvet}
%\renewcommand{\rmdefault}{phv} % alternatively Arial
%\renewcommand{\sfdefault}{phv} % alternatively Arial
% --end of setting to Helvitica


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% this allows commenting out of sections of the file
\newcommand{\comment}[1]{{}}   % don't show comments
%%%% \newcommand{\comment}[1]{{\bf #1}}  % show commented-out text as bold text
\newcommand{\note}[1]{{\bf[#1]}}
\newcommand{\fref}[1]{fig.~\ref{#1}}
\newcommand{\eref}[1]{eq.~(\ref{#1})}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\usepackage{xspace} % for one of the abstracts


\begin{document}
\bibliographystyle{plain}

%\newlength{\squareSize}
%\setlength{\squareSize}{10pt}
%squareSize is \rule{\squareSize}{\squareSize}

\sessionHeader{Association Rules and Frequent Patterns}{John Doe}{2.11 MVB}
\talk{05:00-05:20}{Discovering Descriptive Tile Trees by Mining Optimal Geometric Subtiles}{Nikolaj Tatti and Jilles Vreeken}
\talk{05:20-05:40}{Efficient Discovery of Association Rules and Frequent Itemsets through \hspace{1cm} % hack to split line
                   Sampling with Tight Performance Guarantees}{Matteo Riondato and Eli Upfal}
\sessionend


\marginpar{\Large \vspace*{-2cm}\hspace{-1.2cm}\hfil Monday}

\noindent {\large Association Rules and Frequent Patterns} \hfil Room: XXX
\rule[4mm]{\linewidth}{0.05cm}
%\hrule
\begin{tabular}{l c l}
  05:00-05:20 && Discovering Descriptive Tile Trees by Mining Optimal Geometric Subtiles\\
              && {\em Nikolaj Tatti and Jilles Vreeken} \\\hline
  05:20-05:40 && Efficient Discovery of Association Rules and Frequent Itemsets through\\
              && Sampling with Tight Performance Guarantees\\
              && {\em Matteo Riondato and Eli Upfal}\\\hline
  05:40-06:00 && Smoothing Categorical Data \\
              && {\em Arno Siebes and Ren\'{e} Kersten}\\\hline
\end{tabular}


\vspace{1cm}
\noindent {\large Bayesian Learning and Graphical Models} \hfil Room: XXX
\rule[4mm]{\linewidth}{0.05cm}
%\hrule
\begin{tabular}{l c l}
  05:00-05:20 && Discovering Descriptive Tile Trees by Mining Optimal Geometric Subtiles\\
              && {\em Nikolaj Tatti and Jilles Vreeken} \\\hline
  05:20-05:40 && Efficient Discovery of Association Rules and Frequent Itemsets through\\
              && Sampling with Tight Performance Guarantees\\
              && {\em Matteo Riondato and Eli Upfal}\\\hline
  05:40-06:00 && Smoothing Categorical Data \\
              && {\em Arno Siebes and Ren\'{e} Kersten}\\\hline
\end{tabular}


\vspace{1cm}
\noindent {\large Classification} \hfil Room: XXX
\rule[4mm]{\linewidth}{0.05cm}
%\hrule
\begin{tabular}{l c l}
  05:00-05:20 && Discovering Descriptive Tile Trees by Mining Optimal Geometric Subtiles\\
              && {\em Nikolaj Tatti and Jilles Vreeken} \\\hline
  05:20-05:40 && Efficient Discovery of Association Rules and Frequent Itemsets through\\
              && Sampling with Tight Performance Guarantees\\
              && {\em Matteo Riondato and Eli Upfal}\\\hline
  05:40-06:00 && Smoothing Categorical Data \\
              && {\em Arno Siebes and Ren\'{e} Kersten}\\\hline
\end{tabular}


\vspace{1cm}
\noindent {\large Dimensionality Reduction, Feature Selection and Extraction} \hfil Room: XXX
\rule[4mm]{\linewidth}{0.05cm}
%\hrule
\begin{tabular}{l c l}
  05:00-05:20 && Discovering Descriptive Tile Trees by Mining Optimal Geometric Subtiles\\
              && {\em Nikolaj Tatti and Jilles Vreeken} \\\hline
  05:20-05:40 && Efficient Discovery of Association Rules and Frequent Itemsets through\\
              && Sampling with Tight Performance Guarantees\\
              && {\em Matteo Riondato and Eli Upfal}\\\hline
  05:40-06:00 && Smoothing Categorical Data \\
              && {\em Arno Siebes and Ren\'{e} Kersten}\\\hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\marginpar{\Large \vspace*{-2cm}\hspace{-1.2cm}\hfil Monday}
\newcommand{\numrows}{N}
\newcommand{\numcols}{M}
\newcommand{\Mondrian}{\textsc{Stijl}\xspace}


\vspace{1cm}
\noindent {\large Association Rules and Frequent Patterns} \hfil Room: XXX
\rule[4mm]{\linewidth}{0.05cm}
%\hrule
\begin{tabular}{l c p{12cm}}
  05:00-05:20 && {\bf Discovering Descriptive Tile Trees by Mining Optimal Geometric Subtiles}\\
              && {\em Nikolaj Tatti and Jilles Vreeken} \\
\end{tabular}

\vspace{0.2cm}
\noindent When analysing binary data, the ease at which one can interpret results is very important. Many existing methods, however, discover either models that are difficult to read, or return so many results interpretation becomes impossible. 
Here, we study a fully automated approach for mining easily interpretable models for binary data. We model data hierarchically with noisy tiles---rectangles with significantly different density than their parent tile. To identify good trees, we employ the Minimum Description Length principle. 

We propose \Mondrian, a greedy any-time algorithm for mining good tile trees from binary data. Iteratively, it finds the locally \emph{optimal} addition to the current tree, allowing overlap with tiles of the same parent. A major result of this paper is that we find the optimal tile in only $\Theta(\numrows\numcols\min(\numrows,\numcols))$ time. \Mondrian can either be employed as a top-$k$ miner, or by MDL we can identify the tree that describes the data best.

Experiments show we find succinct models that accurately summarise the data, and, by their hierarchical property are easily interpretable.

\vspace{0.5cm}
\hrule
\vspace{0.4cm}
\noindent \begin{tabular}{l c p{12cm}}
05:20-05:40 && {\bf Efficient Discovery of Association Rules and Frequent Itemsets}\\
              &&   {\bf through Sampling with Tight Performance Guarantees}\\
              && {\em Matteo Riondato and Eli Upfal}
\end{tabular}

\vspace{0.2cm}
\noindent  The tasks of extracting (top-$K$) Frequent Itemsets (FI's) and
  Association Rules (AR's) are fundamental primitives in data mining and
  database applications. Exact algorithms for these problems exist and are
  widely used, but their running time is hindered by the need of scanning the
  entire dataset, possibly multiple times.  High quality approximations of FI's
  and AR's are sufficient for most practical uses, and a number of recent works
  explored the application of sampling for fast discovery of approximate
  solutions to the problems. However, these works do not provide satisfactory
  performance guarantees on the quality of the approximation, due to the
  difficulty of bounding the probability of under- or over-sampling any one of
  an unknown number of frequent itemsets. In this work we circumvent this issue
  by applying the statistical concept of \emph{Vapnik-Chervonenkis (VC)
  dimension} to develop a novel technique for providing tight bounds on the
  sample size that guarantees approximation within user-specified parameters.
  Our technique applies both to absolute and to relative approximations of
  (top-$K$) FI's and AR's. The resulting sample size is linearly dependent on
  the VC-dimension of a range space associated with the dataset to be mined. The
  main theoretical contribution of this work is a characterization of the
  VC-dimension of this range space and a proof that it is upper bounded by an
  easy-to-compute characteristic quantity of the dataset which we call
  \emph{d-index}, namely the maximum integer $d$ such that the dataset contains
  at least $d$ transactions of length at least $d$. We show that this bound is
  strict for a large class of datasets. The resulting sample size for an
  absolute (resp.~relative) $(\varepsilon, \delta)$-approximation of the
  collection of FI's is $O(\frac{1}{\varepsilon^2}(d+\log\frac{1}{\delta}))$
  (resp.
  $O(\frac{2+\varepsilon}{\varepsilon^2(2-\varepsilon)\theta}(d\log\frac{2+\varepsilon}{(2-\varepsilon)\theta}+\log\frac{1}{\delta}))$)
  transactions, which is a significant improvement over previous known
  results. We present an extensive experimental evaluation of our technique on
  real and artificial datasets, demonstrating the practicality of our methods,
  and showing that they achieve even higher quality approximations than what is
  guaranteed by the analysis.

\vspace{0.5cm}
\hrule
\vspace{0.4cm}
\noindent \begin{tabular}{l c p{12cm}}
  05:40-06:00 && {\bf Smoothing Categorical Data} \\
              && {\em Arno Siebes and Ren\'{e} Kersten}\\
\end{tabular}

\vspace{0.2cm}
\noindent Global models of a dataset reflect not only the large scale structure
of the data distribution, they also reflect small(er) scale structure.
Hence, if one wants to see the large
scale structure, one should somehow subtract this smaller scale
structure from the model. 

While for some kinds of model -- such as boosted classifiers -- it is easy to see the ``important" components, for many kind of models this is far harder, if at all possible.
In such cases one might try an implicit approach: simplify the
data distribution without changing the large scale structure. That is,
one might first smooth the local structure out of the dataset. Then
induce a new model from this smoothed dataset. This new model should
now reflect the large scale structure of the original dataset.
In this paper we propose such a smoothing for categorical data and for one particular type of models, viz., code tables.

By experiments we show that our approach preserves the large scale
structure of a dataset well. That is, the smoothed dataset is simpler
while the original and smoothed datasets share the same large scale structure.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
%\marginpar{\Large \vspace*{-2cm}\hspace{-1.2cm}\hfil Monday}

%\vspace{1cm}
%\noindent {\large Association Rules and Frequent Patterns} \hfil Room: XXX
%\rule[4mm]{\linewidth}{0.05cm}
%\hrule
\begin{tabular}{l c p{12cm}}
  05:00-05:20 && {\bf Discovering Descriptive Tile Trees by Mining Optimal Geometric Subtiles}\\
              && {\em Nikolaj Tatti and Jilles Vreeken} \\
              && When analysing binary data, the ease at which one can interpret results is very important. Many existing methods, however, discover either models that are difficult to read, or return so many results interpretation becomes impossible. 
Here, we study a fully automated approach for mining easily interpretable models for binary data. We model data hierarchically with noisy tiles---rectangles with significantly different density than their parent tile. To identify good trees, we employ the Minimum Description Length principle. 

We propose \Mondrian, a greedy any-time algorithm for mining good tile trees from binary data. Iteratively, it finds the locally \emph{optimal} addition to the current tree, allowing overlap with tiles of the same parent. A major result of this paper is that we find the optimal tile in only $\Theta(\numrows\numcols\min(\numrows,\numcols))$ time. \Mondrian can either be employed as a top-$k$ miner, or by MDL we can identify the tree that describes the data best.

Experiments show we find succinct models that accurately summarise the data, and, by their hierarchical property are easily interpretable.\\\hline

  05:20-05:40 && {\bf Efficient Discovery of Association Rules and Frequent Itemsets}\\
              &&   {\bf through Sampling with Tight Performance Guarantees}\\
              && {\em Matteo Riondato and Eli Upfal}\\
              &&   The tasks of extracting (top-$K$) Frequent Itemsets (FI's) and
  Association Rules (AR's) are fundamental primitives in data mining and
  database applications. Exact algorithms for these problems exist and are
  widely used, but their running time is hindered by the need of scanning the
  entire dataset, possibly multiple times.  High quality approximations of FI's
  and AR's are sufficient for most practical uses, and a number of recent works
  explored the application of sampling for fast discovery of approximate
  solutions to the problems. However, these works do not provide satisfactory
  performance guarantees on the quality of the approximation, due to the
  difficulty of bounding the probability of under- or over-sampling any one of
  an unknown number of frequent itemsets. In this work we circumvent this issue
  by applying the statistical concept of \emph{Vapnik-Chervonenkis (VC)
  dimension} to develop a novel technique for providing tight bounds on the
  sample size that guarantees approximation within user-specified parameters.
  Our technique applies both to absolute and to relative approximations of
  (top-$K$) FI's and AR's. The resulting sample size is linearly dependent on
  the VC-dimension of a range space associated with the dataset to be mined. The
  main theoretical contribution of this work is a characterization of the
  VC-dimension of this range space and a proof that it is upper bounded by an
  easy-to-compute characteristic quantity of the dataset which we call
  \emph{d-index}, namely the maximum integer $d$ such that the dataset contains
  at least $d$ transactions of length at least $d$. We show that this bound is
  strict for a large class of datasets. The resulting sample size for an
  absolute (resp.~relative) $(\varepsilon, \delta)$-approximation of the
  collection of FI's is $O(\frac{1}{\varepsilon^2}(d+\log\frac{1}{\delta}))$
  (resp.
  $O(\frac{2+\varepsilon}{\varepsilon^2(2-\varepsilon)\theta}(d\log\frac{2+\varepsilon}{(2-\varepsilon)\theta}+\log\frac{1}{\delta}))$)
  transactions, which is a significant improvement over previous known
  results. We present an extensive experimental evaluation of our technique on
  real and artificial datasets, demonstrating the practicality of our methods,
  and showing that they achieve even higher quality approximations than what is
  guaranteed by the analysis.\\\hline
  05:40-06:00 && {\bf Smoothing Categorical Data} \\
              && {\em Arno Siebes and Ren\'{e} Kersten}\\
              && Global models of a dataset reflect not only the large scale structure
of the data distribution, they also reflect small(er) scale structure.
Hence, if one wants to see the large
scale structure, one should somehow subtract this smaller scale
structure from the model. 

While for some kinds of model -- such as boosted classifiers -- it is easy to see the ``important" components, for many kind of models this is far harder, if at all possible.
In such cases one might try an implicit approach: simplify the
data distribution without changing the large scale structure. That is,
one might first smooth the local structure out of the dataset. Then
induce a new model from this smoothed dataset. This new model should
now reflect the large scale structure of the original dataset.
In this paper we propose such a smoothing for categorical data and for one particular type of models, viz., code tables.

By experiments we show that our approach preserves the large scale
structure of a dataset well. That is, the smoothed dataset is simpler
while the original and smoothed datasets share the same large scale structure.\\\hline
\end{tabular}


%\begin{figure}[htb]
%\begin{center}
%\leavevmode
%%\includegraphics[width=0.8\textwidth]{image.png}
%\end{center}
%\caption{Awesome Image}
%\label{fig:awesome_image}
%\end{figure}


\bibliography{tim}    % use tim.bib file
\end{document}
