Data Manipulation at Scale: Systems and Algorithms

About this course: Data analysis has replaced data acquisition as the bottleneck to evidence-based decision making --- we are drowning in it. Extracting knowledge from large, heterogeneous, and noisy datasets requires not only powerful computing resources, but the programming abstractions to use them effectively. The abstractions that emerged in the last decade blend ideas from parallel databases, distributed systems, and programming languages to create a new class of scalable data analytics platforms that form the foundation for data science at realistic scales. In this course, you will learn the landscape of relevant systems, the principles on which they rely, their tradeoffs, and how to evaluate their utility against your requirements. You will learn how practical systems were derived from the frontier of research in computer science and what systems are coming on the horizon. Cloud computing, SQL and NoSQL databases, MapReduce and the ecosystem it spawned, Spark and its contemporaries, and specialized systems for graphs and arrays will be covered. You will also learn the history and context of data science, the skills, challenges, and methodologies the term implies, and how to structure a data science project. At the end of this course, you will be able to: Learning Goals: 1. Describe common patterns, challenges, and approaches associated with data science projects, and what makes them different from projects in related fields. 2. Identify and use the programming models associated with scalable data manipulation, including relational algebra, mapreduce, and other data flow models. 3. Use database technology adapted for large-scale analytics, including the concepts driving parallel databases, parallel query processing, and in-database analytics 4. Evaluate key-value stores and NoSQL systems, describe their tradeoffs with comparable systems, the details of important examples in the space, and future trends. 5. “Think” in MapReduce to effectively write algorithms for systems including Hadoop and Spark. You will understand their limitations, design details, their relationship to databases, and their associated ecosystem of algorithms, extensions, and languages. write programs in Spark 6. Describe the landscape of specialized Big Data systems for graphs, arrays, and streams

Created by:  University of Washington

• Taught by:  Bill Howe, Director of Research

  Scalable Data Analytics

Basic Info Course 1 of 4 in the Data Science at Scale Specialization Commitment 4 weeks of study, 6-8 hours/week Language English How To Pass Pass all graded assignments to complete the course. User Ratings 4.3 stars Average User Rating 4.3See what learners said Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from your peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

University of Washington Founded in 1861, the University of Washington is one of the oldest state-supported institutions of higher education on the West Coast and is one of the preeminent research universities in the world.

Syllabus


WEEK 1


Data Science Context and Concepts



Understand the terminology and recurring principles associated with data science, and understand the structure of data science projects and emerging methodologies to approach them. Why does this emerging field exist? How does it relate to other fields? How does this course distinguish itself? What do data science projects look like, and how should they be approached? What are some examples of data science projects?


22 videos, 4 readings expand

1. Video: Appetite Whetting: Politics
2. Video: Appetite Whetting: Extreme Weather
3. Video: Appetite Whetting: Digital Humanities
4. Video: Appetite Whetting: Bibliometrics
5. Video: Appetite Whetting: Food, Music, Public Health
6. Video: Appetite Whetting: Public Health cont'd, Earthquakes, Legal
7. Video: Characterizing Data Science
8. Video: Characterizing Data Science, cont'd
9. Video: Distinguishing Data Science from Related Topics
10. Video: Four Dimensions of Data Science
11. Video: Tools vs. Abstractions
12. Video: Desktop Scale vs. Cloud Scale
13. Video: Hackers vs. Analysts
14. Video: Structs vs. Stats
15. Video: Structs vs. Stats cont'd
16. Video: A Fourth Paradigm of Science
17. Video: Data-Intensive Science Examples
18. Video: Big Data and the 3 Vs
19. Video: Big Data Definitions
20. Video: Big Data Sources
21. Reading: Supplementary: Three-Course Reading List
22. Reading: Supplementary: Resources for Learning Python
23. Video: Course Logistics
24. Reading: Supplementary: Class Virtual Machine
25. Reading: Supplementary: Github Instructions
26. Video: Twitter Assignment: Getting Started

Graded: Twitter Sentiment Analysis

WEEK 2


Relational Databases and the Relational Algebra



Relational Databases are the workhouse of large-scale data management. Although originally motivated by problems in enterprise operations, they have proven remarkably capable for analytics as well. But most importantly, the principles underlying relational databases are universal in managing, manipulating, and analyzing data at scale. Even as the landscape of large-scale data systems has expanded dramatically in the last decade, relational models and languages have remained a unifying concept. For working with large-scale data, there is no more important programming model to learn.


24 videos expand

1. Video: Data Models, Terminology
2. Video: From Data Models to Databases
3. Video: Pre-Relational Databases
4. Video: Motivating Relational Databases
5. Video: Relational Databases: Key Ideas
6. Video: Algebraic Optimization Overview
7. Video: Relational Algebra Overview
8. Video: Relational Algebra Operators: Union, Difference, Selection
9. Video: Relational Algebra Operators: Projection, Cross Product
10. Video: Relational Algebra Operators: Cross Product cont'd, Join
11. Video: Relational Algebra Operators: Outer Join
12. Video: Relational Algebra Operators: Theta-Join
13. Video: From SQL to RA
14. Video: Thinking in RA: Logical Query Plans
15. Video: Practical SQL: Binning Timeseries
16. Video: Practical SQL: Genomic Intervals
17. Video: User-Defined Functions
18. Video: Support for User-Defined Functions
19. Video: Optimization: Physical Query Plans
20. Video: Optimization: Choosing Physical Plans
21. Video: Declarative Languages
22. Video: Declarative Languages: Examples
23. Video: Views: Logical Data Independence
24. Video: Indexes

Graded: SQL for Data Science Assignment

WEEK 3


MapReduce and Parallel Dataflow Programming
The MapReduce programming model (as distinct from its implementations) was proposed as a simplifying abstraction for parallel manipulation of massive datasets, and remains an important concept to know when using and evaluating modern big data platforms.


26 videos expand

1. Video: What Does Scalable Mean?
2. Video: A Sketch of Algorithmic Complexity
3. Video: A Sketch of Data-Parallel Algorithms
4. Video: "Pleasingly Parallel" Algorithms
5. Video: General Distributed Algorithms
6. Video: MapReduce Abstraction
7. Video: MapReduce Data Model
8. Video: Map and Reduce Functions
9. Video: MapReduce Simple Example
10. Video: MapReduce Simple Example cont'd
11. Video: MapReduce Example: Word Length Histogram
12. Video: MapReduce Examples: Inverted Index, Join
13. Video: Relational Join: Map Phase
14. Video: Relational Join: Reduce Phase
15. Video: Simple Social Network Analysis: Counting Friends
16. Video: Matrix Multiply Overview
17. Video: Matrix Multiply Illustrated
18. Video: Shared Nothing Computing
19. Video: MapReduce Implementation
20. Video: MapReduce Phases
21. Video: A Design Space for Large-Scale Data Systems
22. Video: Parallel and Distributed Query Processing
23. Video: Teradata Example, MR Extensions
24. Video: RDBMS vs. MapReduce: Features
25. Video: RDBMS vs. Hadoop: Grep
26. Video: RDBMS vs. Hadoop: Select, Aggregate, Join

Graded: Thinking in MapReduce

WEEK 4


NoSQL: Systems and Concepts



NoSQL systems are purely about scale rather than analytics, and are arguably less relevant for the practicing data scientist. However, they occupy an important place in many practical big data platform architectures, and data scientists need to understand their limitations and strengths to use them effectively.


36 videos expand

1. Video: NoSQL Context and Roadmap
2. Video: NoSQL Roundup
3. Video: Relaxing Consistency Guarantees
4. Video: Two-Phase Commit and Consensus Protocols
5. Video: Eventual Consistency
6. Video: CAP Theorem
7. Video: Types of NoSQL Systems
8. Video: ACID, Major Impact Systems
9. Video: Memcached: Consistent Hashing
10. Video: Consistent Hashing, cont'd
11. Video: DynamoDB: Vector Clocks
12. Video: Vector Clocks, cont'd
13. Video: CouchDB Overview
14. Video: CouchB Views
15. Video: BigTable Overview
16. Video: BigTable Implementation
17. Video: HBase, Megastore
18. Video: Spanner
19. Video: Spanner cont'd, Google Systems
20. Video: MapReduce-based Systems
21. Video: Bringing Back Joins
22. Video: NoSQL Rebuttal
23. Video: Almost SQL: Pig
24. Video: Pig Architecture and Performance
25. Video: Data Model
26. Video: Load, Filter, Group
27. Video: Group, Distinct, Foreach, Flatten
28. Video: CoGroup, Join
29. Video: Join Algorithms
30. Video: Skew
31. Video: Other Commands
32. Video: Evaluation Walkthrough
33. Video: Review
34. Video: Context
35. Video: Spark Examples
36. Video: RDDs, Benefits

Graph Analytics



Graph-structured data are increasingly common in data science contexts due to their ubiquity in modeling the communication between entities: people (social networks), computers (Internet communication), cities and countries (transportation networks), or corporations (financial transactions). Learn the common algorithms for extracting information from graph data and how to scale them up.


21 videos expand

1. Video: Graph Overview
2. Video: Structural Analysis
3. Video: Degree Histograms, Structure of the Web
4. Video: Connectivity and Centrality
5. Video: PageRank
6. Video: PageRank in more Detail
7. Video: Traversal Tasks: Spanning Trees and Circuits
8. Video: Traversal Tasks: Maximum Flow
9. Video: Pattern Matching
10. Video: Querying Edge Tables
11. Video: Relational Algebra and Datalog for Graphs
12. Video: Querying Hybrid Graph/Relational Data
13. Video: Graph Query Example: NSA
14. Video: Graph Query Example: Recursion
15. Video: Evaluation of Recursive Programs
16. Video: Recursive Queries in MapReduce
17. Video: The End-Game Problem
18. Video: Representation: Edge Table, Adjacency List
19. Video: Representation: Adjacency Matrix
20. Video: PageRank in MapReduce
21. Video: PageRank in Pregel