Lectures and Readings (Big Data Computing, 2019)

Tuesday, February 26 - Course introduction and overview. The four V's of big data. Volume: how big is "big"? What can we do with big data? How can we program big data systems? Velocity: what can we compute if we cannot even store the input?

Friday, March 1 - Processing data on disk: the external memory model (Aggarwal & Vitter): parameters M and B. Fundamental external memory bounds: scan and sort. Data permutation: I/O-analysis of the naive linear-time algorithm, scan&sort algorithm.

Tuesday, March 5 - Sorting data on disk: 2-way mergesort, I/O analysis. A key inefficiency of 2-way mergesort. k-way mergesort, with full analysis. Hints for an efficient implementation. The 1TB sorting problem: can we do more than one pass? A back of the envelope calculation.

Friday, March 8 - Public transport strike. No class.

Tuesday, March 12 - MapReduce: stable storage, distributed file system, programming model (data as key-value pairs, map/reduce functions, wordcount example).

Friday, March 15 - MapReduce runtime system: distributed execution overview, master, workers, key partitioning, local storage vs. distributed file system, task coordination, failures.

  • MapReduce runtime system: slides

Tuesday, March 19 - Hands-on class. Introduction to Hadoop, configuration, context, mapper and reducer classes, basic writable types (Text, IntWritable, LongWritable). Implementing WordCount. Running WordCount: main HDFS commands.

Friday, March 22 - Good coding practices: examples of simple MapReduce algorithms (matrix transpose, sum of n values). Towards a theoretical cost model.

  • Computational model, examples: slides
  • A model of computation for MapReduce, by H. Karloff, S. Suri & S. Vassilvitskii, appeared in Proceedings of the ACM SIAM Symposium on Discrete Algorithms, SODA 2010 (Sections 1, 2, 3, only definitions covered in class).

-- Irene Finocchi - March 2019

Edit | Attach | Watch | Print version | History: r103 < r102 < r101 < r100 < r99 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r103 - 2019-03-22 - IreneFinocchi





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback