Course: Big Data Analysis

Fall 2013

This schedule is tentative and subject to change

Make sure to check my.poly.edu for course announcements

Week 1: Monday Sept. 9th - Course Overview

• Course overview and introduction to Big Data Analysis
• Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/intro.pdf
• Student survey -- to be filled out today!

Required Reading

• Mining of Massive Datasets, Chapter 1
• Data-Intensive Text Processing with MapReduce, Chapter1

Additional References

• Dilbert's BigData
• New York Time's "How BigData Became so Big"
• World Economic Forum: Big Data, Big Impact
• The Analytics Journey
• BigData Analytics Usecases

Week 2: Monday Sept. 16th - Map-Reduce/Hadoop

• Introduction to Map-Reduce and high-level data processing languages
• Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/Hadoop.pdf
• Hand out AWS tokens. Notes on using AWS.
• Introduction to Hadoop
• The Map-Reduce ecosystem: Pig, Hive, Jaql, Mahout, BigInsights

Required Reading

• Mining of Massive Datasets, Chapter 2
• Data-Intensive Text Processing with MapReduce, Chapter 2 and Chapter 3
• original google map-reduce paper

Additional References

• Pig Latin: A Not-So-Foreign Language for Data Processing
• Jaql: A Scripting Language for Large Scale Semistructured Data Analysis
• Hive - A Warehousing Solution Over a Map-Reduce Framework

Week 3: Monday Sept. 23rd - Data Management for Big Data

• Databases and Big Data: Persistence, Querying, Indexing, Transactions
• Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/paralleldb-vs-hadoop.pdf
• In-class exercise on Map-Reduce (to be distributed in class)

Related Topics

• BigTables and NoSQL stores. Tuple store vs. column stores: HBase, MongoDB, Cassandra
• Transactions in NoSQL stores. Google's percolator, [1].
• "NewSQL" stores: more on Hive, VoltDB, HadoopDB,
• Beyond MapReduce: Berkeley's Spark, UC Irvine's Asterix, Google's Dremel

Required Reading

• PDMBS vs. MapReduce
• http://cacm.acm.org/magazines/2010/1/55744-mapreduce-a-flexible-data-processing-tool/fulltext
• Parallel data processing with MapReduce: a survey. Lee et al, SIGMOD Record 2011
• Benchmark DBMS vs MapReduce (2009)

Additional Readings

• http://www.computerworld.com/s/article/9224180/What_s_the_big_deal_about_Hadoop_
• Bigtable: A Distributed Storage System for Structured Data
• HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads
• Low Overhead Concurrency Control for Partitioned Main Memory Databases
• ASTERIX: Towards a Scalable, Semistructured Data Platform for Evolving-World Models.
• Dremel: Interactive Analysis of Web-Scale Datasets
• Large-scale Incremental Processing Using Distributed Transactions and Notifications

Week 4: Monday Sept 30th - Statistics is easy - Invited Speaker: Dennis Shasha

• Guest lecture by Dennis Shasha: Statistics is Easy
• Pig Latin and Query Processing:
  • Relational query processing: Review
  • Query Processing in Pig

Required Reading

• http://www.morganclaypool.com/doi/abs/10.2200/S00142ED1V01Y200807MAS001 -- book is available for free for NYU students
• Second edition of the book: http://www.morganclaypool.com/doi/pdf/10.2200/S00295ED1V01Y201009MAS008

Homework Assignment

Due October 9th BigDataHW1

Week 5: Monday Oct. 8st - Finding Similar Items

• Similarity: Applications, Measures and Efficiency considerations
  • Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/similarity.pdf
• Similarity application: Information integration on the Web:
  • Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/web-info-integration.pdf
• Homework presentation and demo

Required Reading

• Mining of Massive Datasets, chapter 3; information integration; entity resolution

Homework Assignment

Due October 15th at noon Your assignment is in http://www.newgradiance.com/services. Please see http://vgc.poly.edu/~juliana/courses/cs9223 for instructions on how to access this service.

Week 6: Wednesday Oct. 17th - Invited Speaker: Torsten Suel

Note this class will be held on Wednesday!

• Big Data and Information Retrieval. Invited lecture by Torsten Suel.
  • Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/search-data.pdf

Readings

• 1998 PageRank Paper
• Data-Intensive Text Processing with MapReduce, Chapter 4 (Inverted Indexing for Text Retrieval) and 5(Graph Algorithms)
• Mining of Massive Datasets, Chapter 5 (Link Analysis)

Week 7: Monday Oct. 22st - Invited lecture by and Lauro Lins

• Introduction to Visualization
  • Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/intro-to-visualization.pdf

Readings

The Value of Visualization. IEEE Visualization 2005. Jarke J. van Wijk. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.1138

Visualization Analysis and Design: Principles, Methods, and Practice. Tamara Munzner (Book Draft 2 from Sep. 2012). http://www.cs.ubc.ca/~tmm/courses/533-11/book/vispmp-draft.pdf

Week 9: Monday Nov 5th- Data infrastructure and information integration

• Big Table, HadoopDB.
• Similarity application: Information integration on the Web:
  • Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/web-info-integration.pdf

Readings

• HBase book HBase: The Definitive Guide. Random Access to Your Planet-Size Data: http://shop.oreilly.com/product/0636920014348.do
• HBase book. Chapter 8 Architecture for information about transactional processing, WriteAhead Log notably, and how consistency is being maintained.

Week 10: Monday Nov. 12th - Frequent Itemsets

• • Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/assoc-rules1.pdf, http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/assoc-rules1.pdf

Readings

• Mining of Massive Datasets, Chapter 4

Additional Reading

• Mining association rules between sets of items in large databases. Agrawal et al., SIGMOD 1993. http://delivery.acm.org/10.1145/180000/170072/p207-agrawal.pdf?ip=128.238.251.32&acc=ACTIVE%20SERVICE&CFID=198467341&CFTOKEN=23537886&__acm__=1352747519_b80a516e0f5e294b36dc021f13f55bbb
• Fast algorithms for mining association rules. Agrawal and Srikant, VLDB 1994. https://www.seas.upenn.edu/~jstoy/cis650/papers/Apriori.pdf
• An effective hash-based algorithm for mining association rules. Park et al., SIGMOD 1995. http://dl.acm.org/citation.cfm?id=223813

Week 11: Monday Nov 19th- Algorithms on MapReduce: text processing

• Algorithms, link analysis, social networks
  • Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/mapreduce-indexing-graph.pdf
• Discussion on the project

Readings

• Data-Intensive Text Processing with MapReduce, Chapter 4

Week 12: Monday Nov. 26th - Graph Algorithms and Phase-I project presentations

• • Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/mapreduce-indexing-graph.pdf

Readings

• Data-Intensive Text Processing with MapReduce, Chapter 4
• Pregel: A System for Large-Scale Graph Processing. Google. [2]

Week 13: Monday Dec. 3rd - Clustering

• Lecture notes:
  • Graph algorithms: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/mapreduce-graph.pdf
  • Clustering: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/clustering.pdf, http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/form-clustering-icde2007.pdf

Readings

• Mining of Massive Datasets, Chapter 7
• See readings for previous class
• Web Mining, by Bing Liu. http://www.cs.uic.edu/~liub/WebMiningBook.html
• Information Retrieval. http://nlp.stanford.edu/IR-book/pdf/irbookprint.pdf

Week 14: Monday Dec. 10th - EM algorithms for text processing

Readings

• Data-Intensive Text Processing with MapReduce, Chapter 6

Further Readings

• Anomaly Detection: A Survey

Other topics

Provenance

• Making Computations and Publications Reproducible with VisTrails

Juliana Freire and Claudio Silva. In Computing in Science and Engineering 14(4): 18-25, 2012.

• Provenance for Computational Tasks: A Survey

Juliana Freire, David Koop, Emanuele Santos, and Claudio T. Silva. In IEEE Computing in Science & Engineering, 2008.