Assignment 3 - MapReduce algorithm design - Revision history

Juliana: /* When and What to submit */

2014-04-06T18:08:10Z

When and What to submit

← Older revision		Revision as of 18:08, 6 April 2014
Line 48:		Line 48:
	b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt		b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt

	''Note that ~~you have to output~~ '''only the top 100 word pairs''' sorted by decreasing order of relative frequency.''		''Note that the results must contain '''only the top 100 word pairs''' sorted by decreasing order of relative frequency.''

	c. A plain-text document named rf.txt that describes		c. A plain-text document named rf.txt that describes

Juliana: /* When and What to submit */

2014-04-06T18:07:39Z

When and What to submit

← Older revision		Revision as of 18:07, 6 April 2014
Line 47:		Line 47:

	b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt		b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt

	''Note that you have to output '''only the top 100 word pairs''' sorted by decreasing order of relative frequency.''		''Note that you have to output '''only the top 100 word pairs''' sorted by decreasing order of relative frequency.''

Juliana: /* When and What to submit */

2014-04-06T18:07:21Z

When and What to submit

← Older revision		Revision as of 18:07, 6 April 2014
Line 46:		Line 46:
	a. Source code and readme.txt (For Java, in addition to the source, you must include the JAR file)		a. Source code and readme.txt (For Java, in addition to the source, you must include the JAR file)

	b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt		b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt
			''Note that you have to output '''only the top 100 word pairs''' sorted by decreasing order of relative frequency.''

	c. A plain-text document named rf.txt that describes		c. A plain-text document named rf.txt that describes

Juliana: /* When and What to submit */

2014-04-06T18:06:17Z

When and What to submit

← Older revision		Revision as of 18:06, 6 April 2014
Line 44:		Line 44:
	Your assignment is due on April 6th, 2014 at 11:59pm. All the required files should be compressed in one ZIP file and submitted to NYU Classes. The ZIP file should contain:		Your assignment is due on April 6th, 2014 at 11:59pm. All the required files should be compressed in one ZIP file and submitted to NYU Classes. The ZIP file should contain:

	a. Source code and ~~run~~.sh (For Java, in addition to the source, you must include the JAR file)		a. Source code and readme.txt (For Java, in addition to the source, you must include the JAR file)

	b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt		b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt
Line 51:		Line 51:

	* the input/output format in each Hadoop task, i.e., the keys for the mappers and reducers		* the input/output format in each Hadoop task, i.e., the keys for the mappers and reducers
	* the Hadoop cluster ~~setting~~ you used, i.e., number of mappers and reducers		* the Hadoop cluster settings you used, i.e., number of mappers and reducers
	* the running time for ~~run.sh~~		* the running time for each approach: pairs and stripes


	''Note: all files must be in the same directory''		''Note: all files must be in the same directory''

Juliana: /* Requirements */

2014-04-06T18:05:00Z

Requirements

← Older revision		Revision as of 18:05, 6 April 2014
Line 31:		Line 31:
	=== Requirements ===		=== Requirements ===

	You can write your program using Java or Python (with Hadoop streaming) and you should run it on AWS. ''It is a good idea to develop and test your program on a local machine before deploying in on ~~the cloud~~.'' In addition to the source code, you will submit a ~~shell script~~ file that ~~could be called as follows:~~ ./run~~.sh input_directory input_filename output_directory~~.		You can write your program using Java or Python (with Hadoop streaming) and you should run it on AWS. ''It is a good idea to develop and test your program on a local machine (or on the NYU Hadoop cluster) before deploying on AWS.'' In addition to the source code, you will submit a text file that contains the commands you used to run each Mapreduce job (i.e., pairs and stripes) -- include the Hadoop streaming commands you used to run your jobs.

	1. ~~run~~.sh must include all the ~~necessary~~ commands to run your code and produce the required results.		1. readme.txt must include all the commands you used to run your code and produce the required results.

	2. All files needed to execute ~~run.sh~~ must be stored in the same directory.		2. All files needed to execute these commands must be stored in the same directory.

	3. ~~You~~ should both read from and write to Amazon S3 directly. In other words, input_directory and output_directory should be in S3.		3. Your code should both read from and write to Amazon S3 directly. In other words, input_directory and output_directory should be in S3.

	4. You must use Hadoop version 1.0.3.		4. You must use Hadoop version 1.0.3.

Juliana: /* Task */

2014-03-24T18:25:07Z

Task

← Older revision		Revision as of 18:25, 24 March 2014
Line 15:		Line 15:
	Recall that the relative frequency (RF) of word B given word A is defined as follows:		Recall that the relative frequency (RF) of word B given word A is defined as follows:

	[[File:relative-frequency.png\|300px~~\|left~~]]		[[File:relative-frequency.png\|300px]]

	<br>		<br>

Juliana: /* Task */

2014-03-24T18:24:52Z

Task

← Older revision		Revision as of 18:24, 24 March 2014
Line 15:		Line 15:
	Recall that the relative frequency (RF) of word B given word A is defined as follows:		Recall that the relative frequency (RF) of word B given word A is defined as follows:

	[[File:relative-frequency.png\|~~200px~~\|left]]		[[File:relative-frequency.png\|300px\|left]]

			<br>

	where count(A,B) is the number of times A and B co-occur in a document and count(A) the number of times A occurs with anything else. Intuitively, given a document collection, the relative frequency captures the proportion of time the word B appears in the same document as A. (See Section 3.3, in Data-Intensive Text Processing with MapReduce).		where count(A,B) is the number of times A and B co-occur in a document and count(A) the number of times A occurs with anything else. Intuitively, given a document collection, the relative frequency captures the proportion of time the word B appears in the same document as A. (See Section 3.3, in Data-Intensive Text Processing with MapReduce).

Juliana: /* Task */

2014-03-24T18:24:35Z

Task

← Older revision		Revision as of 18:24, 24 March 2014
Line 15:		Line 15:
	Recall that the relative frequency (RF) of word B given word A is defined as follows:		Recall that the relative frequency (RF) of word B given word A is defined as follows:

	[[File:relative-frequency.png]]		[[File:relative-frequency.png\|200px\|left]]

Juliana: /* Task */

2014-03-24T18:23:14Z

Task

← Older revision		Revision as of 18:23, 24 March 2014
Line 15:		Line 15:
	Recall that the relative frequency (RF) of word B given word A is defined as follows:		Recall that the relative frequency (RF) of word B given word A is defined as follows:

	[[File:~~Example~~.~~jpg~~]]		[[File:relative-frequency.png]]

Juliana: Created page with '== Assignment 3: Computing Relative Frequencies == === Dataset description === For this assignment you will explore a set of 100,000 Wikipedia documents: * s3://cs9223/wikitext…'

2014-03-24T18:22:44Z

Created page with '== Assignment 3: Computing Relative Frequencies == === Dataset description === For this assignment you will explore a set of 100,000 Wikipedia documents: * s3://cs9223/wikitext…'

New page

== Assignment 3: Computing Relative Frequencies ==

=== Dataset description ===

For this assignment you will explore a set of 100,000 Wikipedia documents:
* s3://cs9223/wikitext_100k.txt, or
* https://s3.amazonaws.com/cs9223/wikitext_100k.txt

Each line in this file consists of the plain text extracted from a Wikipedia document.

=== Task ===

Compute the relative frequencies of each word that occurs in the documents in wikitext_100k.txt and output the top 100 word pairs sorted by decreasing order of relative frequency.

Recall that the relative frequency (RF) of word B given word A is defined as follows:

[[File:Example.jpg]]

where count(A,B) is the number of times A and B co-occur in a document and count(A) the number of times A occurs with anything else. Intuitively, given a document collection, the relative frequency captures the proportion of time the word B appears in the same document as A. (See Section 3.3, in Data-Intensive Text Processing with MapReduce).

In the lecture on March 10th, you learned different approaches to do this, and in this assignment, you will implement them:

a. Write a mapreduce program which uses the Stripes approach and writes its output in a file named rfstripes.txt

b. Write a mapreduce program which uses the Pairs approach and writes its output in a file named rfpairs.txt

c. Compare the performance of the two approaches and output the relative performance to a file named rfcomp.txt. Compute the relative performance as follows: (running time for Pairs/ running time for Stripes). Also include an analysis comparing the communication costs for the two approaches.

=== Requirements ===

You can write your program using Java or Python (with Hadoop streaming) and you should run it on AWS. ''It is a good idea to develop and test your program on a local machine before deploying in on the cloud.'' In addition to the source code, you will submit a shell script file that could be called as follows: ./run.sh input_directory input_filename output_directory.

1. run.sh must include all the necessary commands to run your code and produce the required results.

2. All files needed to execute run.sh must be stored in the same directory.

3. You should both read from and write to Amazon S3 directly. In other words, input_directory and output_directory should be in S3.

4. You must use Hadoop version 1.0.3.

=== When and What to submit ===
Your assignment is due on April 6th, 2014 at 11:59pm. All the required files should be compressed in one ZIP file and submitted to NYU Classes. The ZIP file should contain:

a. Source code and run.sh (For Java, in addition to the source, you must include the JAR file)

b. The result files: rfstripes.txt, rfpairs.txt, rfcomp.txt

c. A plain-text document named rf.txt that describes

* the input/output format in each Hadoop task, i.e., the keys for the mappers and reducers
* the Hadoop cluster setting you used, i.e., number of mappers and reducers
* the running time for run.sh

''Note: all files must be in the same directory''