TODO

big-data-course-ex-p38.tex

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}

\title{}
\author{Luca Parolari\footnote{[email protected]}}

\begin{document}
\maketitle

Exercises page 38, slides ``MapReduce''. (Big Data Computing course at University of Padua, Italy, AY 2019-2020).

\section{Exercise}
Given a set $S$ of $N$ points and a distance metric, determine the maximum distance between two points. The problem can be summarized as follows.
\begin{itemize}
  \item \textbf{Input}: Set $S$ of $N$ points represented by pairs $(i, x_i)$
  \item \textbf{Output}: $(0, \max_{0 \leq i,j < N} \text{d}(x_i,x_j))$ 
\end{itemize}

\subsection{Part 1}

Design an MR algorithm for the problem which requires.
\[
R = O(1), M_L = O(\sqrt{N}), M_A = O(N^2)
\]

\begin{proof} 
We have to design an algorithm with a fixed number of rounds
\begin{itemize}
  \item \textsc{Round 1} 
  \begin{itemize}
    \item \emph{Map phase}: $\forall (i,x) \in S$ produce the pair $(i \mod \sqrt{N}, x)$
    \item \emph{Reduce phase}: for each $0 \leq j < \sqrt{N}$ gather the all pairs with key $j$ (call it $S^{(j)}$) and produce the pair $(0, \max_{0 \leq i,j < \sqrt{N}} \text{d}(x_i,x_j))$.
  \end{itemize}
  \item \textsc{Round 2}
  \begin{itemize}
    \item \emph{Map phase}: $\emptyset$
    \item \emph{Reduce phase}: Get all pairs with key 0 (we have at least $\sqrt{N}$ pairs) and produce the pair $(0, \max_{0 \leq i,j < \sqrt{N}} \text{d}(x_i,x_j))$
  \end{itemize}
\end{itemize}
\end{proof}

\subsection{Part 2}

Design an MR algorithm for the problem which requires.
\[
R = O(\sqrt{N}), M_L = O(\sqrt{N}), M_A = O(N)
\]

\begin{proof} 
We have to design an algorithm with $O(\sqrt{N})$ number of rounds


???
\end{proof}

\end{document}