\documentclass[12pt,fullpage]{article}  
\usepackage{epsfig}

\newtheorem{principle}{Principle}
\newtheorem{definition}{Definition}
\newcommand{\yy}[1]{{\bf {todo: {#1}}}}
\newcommand{\vek}[1]{{\bf {#1}}}
\newcommand{\icode}[1]{\textsf{\small{#1}}}
\newenvironment{pcode}%
  {\begin{small}\hrule\smallskip}%
  {\smallskip\hrule\end{small}}
\newcommand{\wca}{\textit{wordCounts$_\textsf{aardvark}$}}
\newcommand{\wcw}{\textit{wordCounts$_w$}}

\title{Naive Bayes and Map-Reduce: Part II}

\author{William Cohen}

\begin{document}

\maketitle

\iffalse
outline

0 Background: Python notation for structures (a,b) pair, [a,b,c] a list

I Review - and more detail:

 - looked at small-memory disk-intensive operations

 - we can build up more complex algorithms from streaming and sorting

 - one primitive component is a map-reduce.  

 - two ways of doing a map-reduce: 
 1) cat IN | map | sort | reduce > OUT



 2) hadoop -mapper map -reducer -reduce -input IN -output OUT
 where IN and OUT are sharded, distributed files on HDFS

 For distributed operations, a combiner

II Abstractions.

A. we could program at map-reduce level and sometimes this is correct;
 but we can add some abstractions.  

B. Examples:

1. For training, we could use general streamer: lambda row->sequence of rows (FlatMap)
   ** TODO: alias Flatten as FlatMap ?
   and then a reducer.  We're not really sorting, just collecting together same keys;
   so could use Group(by = lambda row:key, reducingTo=ReduceTo(int, lambda accum,x:accum'))
   ** TODO: alias for Group: ReduceByKey(key = lambda row:key, baseValue=zero, reducer=lambda accum,x:accum')
   
   Special cases of FlatMap: Map (1-1), and Filter(1->0/1)

2. Eg for revising event counts: we extract a key and grouped things by that key, 
   so could use Group(by = lambda row:key, retaining=lambda row:row')
  
   and of course combine them ...

3. Eg for request and answer: two phases, formulating requests - which is a FlatMap - and grouping 
   union of two relations but we want to keep track of source of where they come from. By ordering? better might be

   Join( Jin(x, by=lambda row:key), ...,  Jin(x, by=lambda row:key) ) 

4. Need some I/O: ReadLines, Format.  

III. Implementing the NB train/test like this...

 - abstractly

III. Implementing the NB train/test in GuineaPig 

 - ideas: query plan, translation to steps, ....
 - debugging: ....

IV. Getting more complex

 - side tables for streaming: Augment

V. GuineaPig vs other systems

A. PIG

B. Spark

Notes on GuineaPig abstractions

Flatten lambda row:rowSeq - one-many streaming, spark flatMap
special cases:
  - Map lambda row:row'  aka ReplaceEach - one-one streaming, spark 'map
  - Filter lambda row:bool - one-one/zero streaming, spark filter
    - spark sample

Group(by = lambda row:key,  retaining=lambda row:row', reducingTo=ReduceTo(type, by=lambda accum,x:accum')) - map/reduce
 - spark groupByKey, reduceByKey, aggregateByKey, 


Spark also includes: 
 - UNION, intersection, cogroup, cartesian, 
 - partitioning transformations....
 - actions: reduce, collect, count, first, takeXXX, saveAsXX, foreach, ...

\fi

\end{document}
