Introduction to MapReduce

Readings (complete before class)

• Jeffrey Dean and Sanjay Ghemawat. (2004) MapReduce: Simplified Data Processing on Large Clusters. Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI 2004), pages 137-150.
• Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. (2003) The Google File System. Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP-03), pages 29-43.
• Lin & Dyer, Chapter 1, Introduction
• Lin & Dyer, Chapter 2, MapReduce Basics

Topics

• Administrivia
• Overview of cloud computing
• Overview of MapReduce and the distributed file system

Material

• Lecture slides: PowerPoint (9.46 MB), PDF (3.90 MB)

Hadoop: Nuts and Bolts

Readings (complete before class)

• White, Chapter 1, "Meet Hadoop"
• White, Chapter 2, "MapReduce", up until page 32
• White, Chapter 3, "The Hadoop Distributed File System", up until page 63
• White, Chapter 4, "Hadoop I/O", starting from "Serialization" until the end of chapter
• White, Chapter 5, "Developing a MapReduce Application", up until page 144

Note that a lot of chapters are assigned from the White book. However, the purpose is to get you acquainted with Hadoop—we don't expect you to digest all the material the first time through, since no doubt you'll be referring back to the book frequently throughout the semester.

Topics

• Writing, running, debugging Hadoop programs
• Hadoop behind the scenes

Material

• Lecture slides: PowerPoint (2.74 MB), PDF (1.92 MB)

MapReduce: the programming environment

Readings (complete before class)

• Lin & Dyer, Chapter 3, MapReduce Algorithm Design
• White, Chapter 3, "The Hadoop Distributed File System", page 63 until end of chapter
• White, Chapter 6, "How MapReduce Works"
• White, Chapter 7, "MapReduce Types and Formats"
• White, Chapter 8, "MapReduce Features"

Topics

• "Warehouse-size" computers and the datacenter environment
• MapReduce algorithm design and design patterns

Material

• Lecture slides: PowerPoint (6.75 MB), PDF (2.57 MB)

Text retrieval algorithms

Readings (complete before class)

• Lin & Dyer, Chapter 4, Inverted Indexing for Text Retrieval
• Justin Zobel and Alistair Moffat. Inverted files for Text Search Engines. ACM Computing Surveys, 38(2), 2006. (Read through Section 12; no need to read Section 13, the bibliography)

Topics

• Introduction to information retrieval
• Basics of indexing and retrieval
• Inverted indexing in MapReduce
• Retrieval at scale

Material

• Lecture slides: PowerPoint (2.39 MB), PDF (1.27 MB)

Graph algorithms

Readings (complete before class)

• Lin & Dyer, Chapter 5, Graph Algorithms
• Lise Getoor and Christopher P. Diehl. (2005) Link Mining: A Survey. ACM SIGKDD Explorations Newsletter, 7(2):3-12.

Topics

• Graph problems and representations
• Parallel breadth-first search
• PageRank

Material

• Lecture slides: PowerPoint (2.60 MB), PDF (1.69 MB)

MapReduce and databases

Readings (complete before class)

• Michael Stonebraker, Daniel Abadi, David J. DeWitt, Sam Madden, Erik Paulson, Andrew Pavlo, and Alexander Rasin. (2010) MapReduce and Parallel DBMSs: Friends or Foes? Communications of the ACM, 53(1):64-71.
• Jeffrey Dean and Sanjay Ghemawat. (2010) MapReduce: A Flexible Data Processing Tool. Communications of the ACM, 53(1):72-77.

Topics

• Relational databases vs. MapReduce
• MapReduce algorithms for processing relational data
• OLTP vs. OLAP (data warehousing and business intelligence)

Material

• Lecture slides: PowerPoint (2.35 MB), PDF (1.25 MB)

Hidden Markov models

Readings (complete before class)

• Lin & Dyer, Chapter 6, EM Algorithms for Text Processing

Topics

• Hidden Markov models
• Expectation maximization

Material

• Lecture slides: PowerPoint (2.88 MB), PDF (2.76 MB)

Language models

Readings (complete before class)

• Thorsten Brants, Ashok C. Popat, Peng Xu, Franz J. Och, and Jeffrey Dean. (2007) Large Language Models in Machine Translation. Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 858–867.

Topics

• N-gram language models
• Parameter estimation for web-scale language models

Material

• Lecture slides: PowerPoint (3.20 MB), PDF (3.27 MB)

Large-scale graphs

Readings (complete before class)

• Tamer Elsayed, Jimmy Lin, and Douglas Oard. (2008) Pairwise Document Similarity in Large Collections with MapReduce. Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL 2008), Companion Volume, pages 265-268.
• Genome sequence assembly primer

Topics

• Scalable identity resolution in email collections: Slides in PDF (622 KB)
• DNA sequence assembly: Slides in PDF (5.65 MB)

Dryad and DryadLINQ

Readings (complete before class)

• Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. (2007) Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks. Proceedings of the ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 (EuroSys 2007), page 59-72.
• Yuan Yu, Michael Isard, Dennis Fetterly, Mihai Budiu, Ulfar Erlingsson, Pradeep Kumar Gunda, and Jon Currey. (2008) DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. Proceedings of the 8th Symposium on Operating System Design and Implementation (OSDI 2008), pages 1-14.

Topics

• Dryad and DryadLINQ: Guest lecture by Michael Isard.

Bigtable, Hive, and Pig

Readings (complete before class)

• Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Michael Burrows, Tushar Chandra, Andrew Fikes, and Robert Gruber. (2006) Bigtable: A Distributed Storage System for Structured Data. Proceedings of the 7th Symposium on Operating System Design and Implementation (OSDI 2006), pages 205-218.
• Christopher Olston, Benjamin Reed, Utkarsh Srivastava, Ravi Kumar, and Andrew Tomkins. (2008) Pig Latin: A Not-So-Foreign Language for Data Processing. Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pages 1099-1110.

Topics

• Bigtable
• Hive
• Pig

Material

• Lecture slides: PowerPoint (2.68 MB), PDF (1.82 MB)