<commit_before>h1. ChimpMARK-2010: Big Data Benchmark on Real-World Datasets

The ChimpMARK-2010 is a collection of massive real-world datasets, interesting real-world problems, and simple example code to solve them. Learn Big Data processing, benchmark your cluster, or compete on implementation!

Why?

* Estimate run time for a job by adding runtimes for tasks with similar size, shape and atomic operations.
* With known data and code, you can performance-qualify cluster. How fast should a join run on a 10-machine cluster of m1.large instances?
* Understand what cluster settings should be tuned in response to job characterstics.
* Compare clusters of equivalent nominal power (CPU, cores, memory) across data centers or hardware configs: AWS vs Rackspace vs private cluster: go!
* Different core technologies (pig vs. wukong vs. raw Java) can compete on run time, efficiency, elegance, and size of code. 

Each problem is meant to a) to be a real-world task, b) to nonetheless encapsulate a very small, generic number of operations. For instance, adjacency pairs => adjacency list on the wikipedia link graph is really just a GROUP, but in particular it's a group on very small records with median multiplicity of ~5, maximum in the thousands, and low skew.

**Note: this is a planning document: the repo contains no code yet**. There's a great variety of example code -- the foundations of what will appear here -- in the "wukong repo":http://github.com/infochimps/wukong/tree/master/examples/


h2. Goals:

* Datasets at full size should be about 30-200GB raw size on HDFS (that is, ready to process, not counting replication multiplier)
* Run tasks times on 5%, 20% and 100% samples
* Cluster sizes from 5 to 15 machines m1.small, c1.medium, m2.xl
* Important that all datasets be *completely* unencumbered by copyright issues or controversy
* Exercise CPU-bound, IO-bound and memory-bound operations
* Tasks should be specified so that say Solr or Cassandra can show example code.

h2. Corpora:

h3. Graph: wikidata/wikilinks (1.1G)

* "Wikipedia Page Traffic Statistics":http://developer.amazonwebservices.com/connect/entry.jspa?externalID=2596

h4. Wikipedia pge links dataset

bq. Contains a wikipedia linkgraph dataset provided by <NAME>.
  These files contain all links between proper english language Wikipedia pages, that is pages in "namespace 0". This includes disambiguation pages and redirect pages.
  [ convert this to adj. pairs -- or to be directly loadable in pig ]
  In links-simple-sorted.txt, there is one line for each page that has links from it. The format of the lines is:
<pre><code>
      from1: to11 to12 to13 ...
      from2: to21 to22 to23 ...
      ...
</code></pre>
  where from1 is an integer labelling a page that has links from it, and to11 to12 to13 ... are integers labelling all the pages that the page links to. To find the page title that corresponds to integer n, just look up the n-th line in the file titles-sorted.txt.
  
h3. Short Documents 1: ???

uniform ~150-200 char fields + metadata

h3. Long Documents: Large interesting colxn of web pages

typically 10k - 1M files

h3. Log

h4. Wikipedia Traffic Statistics Dataset

  Contains hourly wikipedia article traffic statistics dataset covering 7 month period from October 01 2008 to April 30 2009, this data is regularly logged from the wikipedia squid proxy by <NAME>.
  Each log file is named with the date and time of collection: pagecounts-20090430-230000.gz
  Each line has 4 fields: projectcode, pagename, pageviews, bytes

<pre><code>
        en Barack_Obama                         997 123091092
	en Barack_Obama%27s_first_100_days        8 850127
	en Barack_Obama,_Jr                       1 144103
	en Barack_Obama,_Sr.                     37 938821
	en Barack_Obama_%22HOPE%22_poster         4 81005
	en Barack_Obama_%22Hope%22_poster         5 102081
</code></pre>

   we should denormalize into 

<pre><code>
        date 	hour	en Barack_Obama                         997 123091092
	date 	hour	en Barack_Obama%27s_first_100_days        8 850127
	date 	hour	en Barack_Obama,_Jr                       1 144103
	date 	hour	en Barack_Obama,_Sr.                     37 938821
	date 	hour	en Barack_Obama_%22HOPE%22_poster         4 81005
	date 	hour	en Barack_Obama_%22Hope%22_poster         5 102081
</code></pre>

h3. Spreadsheet-ish: (Business and Industry Summary Data?)

Choices:
* "Business and Industry Summary Data":http://developer.amazonwebservices.com/connect/entry.jspa?externalID=2342&categoryID=248
* "2003-2006 US Economic Data":http://developer.amazonwebservices.com/connect/entry.jspa?externalID=2341&categoryID=248
  
h2. Tasks:

h3. Cat wrangling

  uniq -c                                       short documents         distinct, count                 
  uniq -c                                       long documents          distinct, count                 

  sort on numeric field, 1k-char records        wp traffic statistics   ORDER
  sort on numeric field, 6 numeric columns      spreadsheet             ORDER
  sort wp by page titles                        wp                      ORDER

  create inverted index                         long documents

  word count

  uniform (x% random sample)                    short documents
  uniform (x% random sample)                    long documents

  make a single .gz file on non-HDFS            human genome?           want higher entropy
  make a single .gz file on non-HDFS            graph                   want very low entropy

  simple filter on 10k files, most smaller than block size
 
h3. Graph

  turn adjacency pairs into adj list
  given adj. pairs get counts of in-links and out-links
  join the counts of in-links and out-links by node                     JOIN that is 1:1
  pagerank
  put page titles and aggregated counts on adjacency list (something)?  JOIN that is huge to big with 100% overlap
  
  breadth first search
  1-clique

  sub-universe                                  graph + short documents
    => get random sample, and corr. records from assoc. datasets
    
h3. Filter  

  filter on numeric criteria                    spreadsheet             FILTER

  split on simple criteria into 5 files, every record to exactly 1 file
  split on simple criteria into 5 files, records could go to some, none or any of the files

  regex search                                  short documents         FILTER, MATCHES

  100 keywords                                  short documents
  100 keywords                                  long documents
  30,000 keywords                               short documents

  1000 keywords + huge inverted index           inverted index          fragment replicate JOIN (JOIN with big and tiny)
  
h3. Parse

  extract title, keyword, desc from HTML head   long documents
  extract all <a> and <img> etc URLs from HTML  long documents
  
h3. OLAP / Stats

  simple statistics: avg, stdev, counts         spreadsheet             GROUP, FOREACH

  top-N: find top 100 pages by views per day    wp traffic statistics

  something very CPU-intensive in foreach       [some bio dataset]

  [LEFT JOIN big on big having ~5% overlap]                             LEFT JOIN with big and big having ~5% overlap
  
h3. Misc

  render as JSON                                spreadsheet?            stream
 
h2. Atomic Operations to be exercised

group all
group by
cogroup A by a0 left, B by b1 left
cogroup A by a0 left, B by b1 right
join big, huge
join A, B, C
join tiny, big
join sorted, sorted

cross A, B

distinct A
filter A by regex
filter A by (a in set_of_100_items)
filter A by (a in set_of_100_000_items)

sort A by number
sort A by character

inverted index: => gutenberg
  tokenize doc:         [word, doc, line]
  group on word:        word => [ [doc,count], [doc,count], [doc,count], ... ] in descending order by count
  group on word+doc:    [word, doc] => [line, line, line, ...]

relative frequency => gutenberg
  group by document. => [doc  tok  doc_tok_count  doc_tok_freq doc_vocab]
  group by token.    => [     tok  all_tok_count  all_tok_freq avg_doc_tok_freq  stdev_doc_tok_freq  tok_dispersion  tok_range ]
  group by 

parse XXX<commit_msg>Formatting all screwy<commit_after>h1. ChimpMARK-2010: Big Data Benchmark on Real-World Datasets

The ChimpMARK-2010 is a collection of massive real-world datasets, interesting real-world problems, and simple example code to solve them. Learn Big Data processing, benchmark your cluster, or compete on implementation!

Why?

* Estimate run time for a job by adding runtimes for tasks with similar size, shape and atomic operations.
* With known data and code, you can performance-qualify cluster. How fast should a join run on a 10-machine cluster of m1.large instances?
* Understand what cluster settings should be tuned in response to job characterstics.
* Compare clusters of equivalent nominal power (CPU, cores, memory) across data centers or hardware configs: AWS vs Rackspace vs private cluster: go!
* Different core technologies (pig vs. wukong vs. raw Java) can compete on run time, efficiency, elegance, and size of code. 

Each problem is meant to a) to be a real-world task, b) to nonetheless encapsulate a very small, generic number of operations. For instance, adjacency pairs => adjacency list on the wikipedia link graph is really just a GROUP, but in particular it's a group on very small records with median multiplicity of ~5, maximum in the thousands, and low skew.

**Note: this is a planning document: the repo contains no code yet**. There's a great variety of example code -- the foundations of what will appear here -- in the "wukong repo":http://github.com/infochimps/wukong/tree/master/examples/


h2. Goals:

* Datasets at full size should be about 30-200GB raw size on HDFS (that is, ready to process, not counting replication multiplier)
* Run tasks times on 5%, 20% and 100% samples
* Cluster sizes from 5 to 15 machines m1.small, c1.medium, m2.xl
* Important that all datasets be *completely* unencumbered by copyright issues or controversy
* Exercise CPU-bound, IO-bound and memory-bound operations
* Tasks should be specified so that say Solr or Cassandra can show example code.

h2. Corpora:

h3. Graph: wikidata/wikilinks (1.1G)

* "Wikipedia Page Traffic Statistics":http://developer.amazonwebservices.com/connect/entry.jspa?externalID=2596

h4. Wikipedia pge links dataset

bq. Contains a wikipedia linkgraph dataset provided by <NAME>.
  These files contain all links between proper english language Wikipedia pages, that is pages in "namespace 0". This includes disambiguation pages and redirect pages.
  [ convert this to adj. pairs -- or to be directly loadable in pig ]
  In links-simple-sorted.txt, there is one line for each page that has links from it. The format of the lines is:
<pre><code>
      from1: to11 to12 to13 ...
      from2: to21 to22 to23 ...
      ...
</code></pre>
  where from1 is an integer labelling a page that has links from it, and to11 to12 to13 ... are integers labelling all the pages that the page links to. To find the page title that corresponds to integer n, just look up the n-th line in the file titles-sorted.txt.
  
h3. Short Documents 1: ???

uniform ~150-200 char fields + metadata

h3. Long Documents: Large interesting colxn of web pages

typically 10k - 1M files

h3. Log

h4. Wikipedia Traffic Statistics Dataset

  Contains hourly wikipedia article traffic statistics dataset covering 7 month period from October 01 2008 to April 30 2009, this data is regularly logged from the wikipedia squid proxy by <NAME>.
  Each log file is named with the date and time of collection: pagecounts-20090430-230000.gz
  Each line has 4 fields: projectcode, pagename, pageviews, bytes

<pre><code>
        en Barack_Obama                         997 123091092
	en Barack_Obama%27s_first_100_days        8 850127
	en Barack_Obama,_Jr                       1 144103
	en Barack_Obama,_Sr.                     37 938821
	en Barack_Obama_%22HOPE%22_poster         4 81005
	en Barack_Obama_%22Hope%22_poster         5 102081
</code></pre>

   we should denormalize into 

<pre><code>
        date 	hour	en Barack_Obama                         997 123091092
	date 	hour	en Barack_Obama%27s_first_100_days        8 850127
	date 	hour	en Barack_Obama,_Jr                       1 144103
	date 	hour	en Barack_Obama,_Sr.                     37 938821
	date 	hour	en Barack_Obama_%22HOPE%22_poster         4 81005
	date 	hour	en Barack_Obama_%22Hope%22_poster         5 102081
</code></pre>

h3. Spreadsheet-ish: (Business and Industry Summary Data?)

Choices:
* "Business and Industry Summary Data":http://developer.amazonwebservices.com/connect/entry.jspa?externalID=2342&categoryID=248
* "2003-2006 US Economic Data":http://developer.amazonwebservices.com/connect/entry.jspa?externalID=2341&categoryID=248
  
h2. Tasks:

|_. Cat wrangling                                |                         |                                                    |
|                                                |                         |                                                    |
|  uniq -c                                       | short documents         | distinct, count                                    |
|  uniq -c                                       | long documents          | distinct, count                                    |
|                                                |                         |                                                    |
|  sort on numeric field, 1k-char records        | wp traffic statistics   | ORDER                                              |
|  sort on numeric field, 6 numeric columns      | spreadsheet             | ORDER                                              |
|  sort wp by page titles                        | wp                      | ORDER                                              |
|                                                |                         |                                                    |
|  create inverted index                         | long documents          |                                                    |
|                                                |                         |                                                    |
|  word count                                    |                         |                                                    |
|                                                |                         |                                                    |
|  uniform (x% random sample)                    | short documents         |                                                    |
|  uniform (x% random sample)                    | long documents          |                                                    |
|                                                |                         |                                                    |
|  make a single .gz file on non-HDFS            | human genome?           | want higher entropy                                |
|  make a single .gz file on non-HDFS            | graph                   | want very low entropy                              |
|                                                |                         |                                                    |
|  simple filter on 10k files, most smaller than | block size              |                                                    |
|                                                |                         |                                                    |
|_. Graph                                        |                         |                                                    |
|                                                |                         |                                                    |
|  turn adjacency pairs into adj list            |                         |                                                    |
|  given adj. pairs get counts of in-links and out-links                   |                                                    |
|  join the counts of in-links and out-links by node                       | JOIN that is 1:1                                   |
|  pagerank                                      |                         |                                                    |
|  put page titles and aggregated counts on adjacency list (something)?    | JOIN that is huge to big with 100% overlap         |
|                                                |                         |                                                    |
|  breadth first search                          |                         |                                                    |
|  1-clique                                      |                         |                                                    |
|                                                |                         |                                                    |
|  sub-universe                                  | graph + short documents |                                                    |
|    => get random sample, and corr. records from assoc. datasets          |                                                    |
|                                                |                         |                                                    |
|_. Filter                                       |                         |                                                    |
|  filter on numeric criteria                    | spreadsheet             | FILTER                                             |
|                                                |                         |                                                    |
|  split on simple criteria into 5 files, every record to exactly 1 file   |                                                    |
|  split on simple criteria into 5 files, records could go to some, none or any of the files                                    |
|  regex search                                  | short documents         | FILTER, MATCHES                                    |
|                                                |                         |                                                    |
| 100 keywords                                   | short documents         |                                                    |
|  100 keywords                                  | long documents          |                                                    |
| 30,000 keywords                                | short documents         |                                                    |
|  1000 keywords + huge inverted index           | inverted index          | fragment replicate JOIN (JOIN with big and tiny)   |
|                                                |                         |                                                    |
|_. Parse                                        |                         |                                                    |
|                                                |                         |                                                    |
|  extract title, keyword, desc from HTML head   | long documents          |                                                    |
|  extract all <a> and <img> etc URLs from HTML  | long documents          |                                                    |
|                                                |                         |                                                    |
|_. OLAP / Stats                                 |                         |                                                    |
|  simple statistics: avg, stdev, counts         | spreadsheet             | GROUP, FOREACH                                     |
|  top-N: find top 100 pages by views per day    | wp traffic statistics   |                                                    |
|  something very CPU-intensive in foreach       | [some bio dataset]      |                                                    |
|  [LEFT JOIN big on big having ~5% overlap]     |                         | LEFT JOIN with big and big having ~5% overlap      |
|_. Misc                                         |                         |                                                    |
|  render as JSON                                | spreadsheet?            | stream                                             |
 
h2. Atomic Operations to be exercised

* group all
* group by
* cogroup A by a0 left, B by b1 left
* cogroup A by a0 left, B by b1 right
* join big, huge
* join A, B, C
* join tiny, big
* join sorted, sorted

* cross A, B

* distinct A
* filter A by regex
* filter A by (a in set_of_100_items)
* filter A by (a in set_of_100_000_items)

* sort A by number
* sort A by character

* inverted index: => gutenberg
*   tokenize doc:         [word, doc, line]
*   group on word:        word => [ [doc,count], [doc,count], [doc,count], ... ] * in descending order by count
*   group on word+doc:    [word, doc] => [line, line, line, ...]

* relative frequency => gutenberg
*   group by document. => [doc  tok  doc_tok_count  doc_tok_freq doc_vocab]
*   group by token.    => [     tok  all_tok_count  all_tok_freq avg_doc_tok_freq  * stdev_doc_tok_freq  tok_dispersion  tok_range ]
*   group by 

* parse XXX
{'fraction_non_alphanumeric': 0.052332354722960064, 'fraction_numerical': 0.027773894403280673, 'mean_word_length': 1.2682591692210126, 'pattern_counts': {'":': 8, '<': 35, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 211, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5153385', 'n_tokens_mistral': 5370, 'n_tokens_neox': 4655, 'n_words': 2069}