Syllabus
CS 451/651: Data-Intensive Distributed Computing (Fall 2025)

• What does it mean to be an AI-first or data-driven company?
• What's the data flywheel?
• What's data engineering?
• What are data platforms?
• What are the 4 V's of data?
• What is this course about? And what is it not about?

• Fundamentals of Data Engineering:
  • Chapter 1. Data Engineering Described
• Designing Data-Intensive Applications, 2nd Edition:
  
  • Chapter 1. Trade-offs in Data Systems Architecture — Intro section and "Analytical versus Operational Systems" (stop at "Cloud versus Self-Hosting")

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have go through the library's portal (i.e., search for the book title and follow the appropriate link).

PDF slides for Sept 4 (v1.00)

• What are the main differences between operational and analytical infrastructure?
• What are data warehouses? What problems did they evolve to solve?
• What are data lakes and lakehouses? What problems did they evolve to solve?
• What are the components of modern data platforms?
• How do operational and analytical data models differ?
• What goes on in ETL/ELT?
• How do different physical representations of data affect storage, compute, and other tradeoffs within data platforms?

• Designing Data-Intensive Applications, 2nd Edition:
  
  • Chapter 3. Data Models and Query Languages — Intro section and "Relational Model versus Document Model" (stop at "Graph-Like Data Models")
  • Chapter 4. Storage and Retrieval — Intro section and "Data Storage for Analytics" (i.e., skip "Storage and Indexing for OLTP" and "Multidimensional and Full-Text Indexes")
  • Chapter 5. Encoding and Evolution — Intro section and "Formats for Encoding Data" (stop at "Modes of Dataflow")
• (Optional) Fundamentals of Data Engineering (These readings covers similar content as above, but offer a complementary perspective to enrich your perspective):
  • Chapter 3. Designing Good Data Architecture — Discussion of data warehouses, ETL, etc.
  • Chapter 8. Queries, Modeling, and Transformation — Discussion of data modeling, star and snowflake organizations, etc.

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have go through the library's portal (i.e., search for the book title and follow the appropriate link).

• What Goes Around Comes Around... And Around... by Michael Stonebraker and Andrew Pavlo (2024). Answers the question: Why relational?
• What Goes Around Comes Around by Michael Stonebraker and Joseph M. Hellerstein (2005). Optional reading, but provides nice historical historical perspective, written 20 years ago.
• Introduction to Data Lakes from Databricks.
• What is a Data Lake? from Microsoft. (It's helpful to get multiple perspectives, even if some aspects are repetitive)
• What Is a Lakehouse? from Databricks.
• What is a medallion architecture? from Databricks.

PDF slides for Sept 9 (v1.01) PDF slides for Sept 11 (v1.01)

• What's the difference between scaling up and scaling out?
• What are the implications of distributed processing across many machines?
• What are the challenges for a divide-and-conquer strategy?
• What challenges does partitioning address? What challenges does it exacerbate?
• What challenges does replication address? What challenges does it exacerbate?
• What's MapReduce and how does it work with HDFS?
• What challenges do communication and skew present in scaling out?
• Why is local aggregation important?

• Designing Data-Intensive Applications, 2nd Edition:
  
  • Chapter 2. Defining Nonfunctional Requirements
  • Chapter 5. Encoding and Evolution — Intro section and "Formats for Encoding Data" (ties in with 2nd lecture last week)
  • Chapter 6. Replication — Intro section to (and including) "Problems with Replication Lag" (Hadoop uses single-leader replication)
  • Chapter 7. Sharding — Intro section to (and including) "Request Routing" (Hadoop uses option 2 in Figure 7-7; "Sharding of Key-Value Data" won't be directly relevant until next week, but makes sense to read together)
• Hadoop: The Definitive Guide, 4th Edition:
  
  • Chapter 3. The Hadoop Distributed Filesystem (can safely ignore specific commands, class names, etc.; focus on design)
  • Chapter 7. How MapReduce Works (can safely ignore specific commands, class names, etc.; focus on design)

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have go through the library's portal (i.e., search for the book title and follow the appropriate link).

The following are optional. They comprise some of the primary sources from which lecture content is drawn, and can enrich your understanding to provide broader context.

• The Datacenter as a Computer: Designing Warehouse-Scale Machines, Third Edition by Luiz André Barroso, Urs Hölzle, Parthasarathy Ranganathan. (This is a long book, but worthwhile to flip through and read anything that catches your attention if you want a better understanding of datacenter design.)
• The original GFS paper
• The original MapReduce paper

PDF slides for Sept 16 (v1.01) PDF slides for Sept 18 (v1.01)

Key Questions

• In what ways does Spark improve over MapReduce?
• How is distributed group by implemented efficiently at scale?
• How do commutative and associative operations contribute to efficient distributed execution?
• How does partitioning contribute to efficient distributed execution?
• How do these concepts come together in efficient joins at scale?

Reread the assigned readings from last week (or read for the first time if you haven't yet). The material will make a lot more sense given the lecture material. In addition:

• High Performance Spark:
  
  • Chapter 2. How Spark Works
  • Chapter 4. Joins (SQL and Core)
• Data-Intensive Text Processing with MapReduce:
  
  • Chapter 2. MapReduce Basics
  • Chapter 3. MapReduce Algorithm Design — the Hadoop-specific material is outdated in the Spark context, but associativity and commutativity remain important.

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have go through the library's portal (i.e., search for the book title and follow the appropriate link).

The following are optional. They comprise some of the primary sources from which lecture content is drawn, and can enrich your understanding to provide broader context.

• The original Spark paper
• Paper about Spark SQL

PDF slides for Sept 23 (v1.00) PDF slides for Sept 25 (v1.00)

• Designing Data-Intensive Applications, 2nd Edition:
  
  • Chapter 11. Batch Processing

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have go through the library's portal (i.e., search for the book title and follow the appropriate link).

• Original Airflow blog post (by Airbnb)
• Airflow @ Lyft

PDF slides for Sept 30 (v1.00) PDF slides for Oct 1 (v1.00)

• What are the key components of an ML solution?
• How is the supervised machine learning problem formulated?
• What roles do data platforms and data engineering play?

• Designing Machine Learning Systems:
  
  • Chapter 2. Introduction to Machine Learning Systems Design — read the section on "Iterative Process", which provides a nice overview of the entire "ML process".
  • Chapter 7. Model Deployment and Prediction Service — Intro section, "Machine Learning Deployment Myths", and "Batch Prediction Versus Online Prediction"
  • Editorial note: there's a lot of solid practical advice in this book. If you're interested in machine learning, there are many topics of interest; skim/read at your leisure.
• Jimmy Lin and Dmitriy Ryaboy. Scaling Big Data Mining Infrastructure: The Twitter Experience, SIGKDD Explorations, 14(2):6-19, 2012.

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have go through the library's portal (i.e., search for the book title and follow the appropriate link).

The following are optional. They provide a deeper dive of lecture content that can enrich your understanding and provide broader context.

• Naive Bayes and Logistic Regression, Tom Mitchell
• Deep Learning: Foundations and Concepts, Christopher M. Bishop and Hugh Bishop [alternative source]
  
  • Chapter 7: Gradient Descent
  • Chapter 5.4.3: Logistic Regression

PDF slides for Oct 7 (v1.00) PDF slides for Oct 9 (v1.01)

• How do data products with operational requirements complicate lakehouse architectures?
• Why does retrieval remain important in the era of LLMs?
• How is retrieval formulated as the problem of computing vector similarity?
• What's the intuition behind sparse and dense vector representations?
• For sparse vector representations, how do we assign weights?
• For sparse retrieval, how do we perform top-k retrieval efficiently?

• Data-Intensive Text Processing with MapReduce:
  
  • Chapter 4. Inverted Indexing for Text Retrieval
• Pretrained Transformers for Text Ranking:
  
  • Chapter 1. Introduction
  • Chapter 2. Setting the Stage
• Introduction to Information Retrieval:
  
  • Chapter 1. Boolean retrieval [Direct Link]

Some of the above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have go through the library's portal (i.e., search for the book title and follow the appropriate link).

PDF slides for Oct 28 (v1.02) PDF slides for Oct 30 (v1.02)

• For sparse vector representations, how do we assign weights?
• For sparse retrieval, how do we perform top-k retrieval efficiently?
• For dense vector representations, how do we assign weights?
• For dense retrieval, how do we perform top-k retrieval efficiently?
• Do we need specialized databases for sparse and dense vectors?
• Can we also learn sparse representations from data?
• Why do we need rerankers?
• What's the relationship between RAG and LLM tool use?
• What challenges does MCP solve?

• A proposed conceptual framework for a representational approach to information retrieval
• Pinecone: Hierarchical Navigable Small Worlds (HNSW)

The following are optional. They comprise some of the primary sources from which lecture content is drawn, and can enrich your understanding to provide broader context.

• Pretrained Transformers for Text Ranking:
  
  • Chapter 5. Learned Dense Representations for Ranking (This chapter is a good starting point if you're interested in a deeper dive of how dense retrieval works. The focus is on generating dense vector representations using encoder-only BERT models. Although most work today uses decoder-only transformer models, much of the core ideas remains the same.)
• What is the Model Context Protocol (MCP)?

PDF slides for Nov 4 (v1.01) PDF slides for Nov 6 (v1.00)

• What do hash collisions have to do with finding similar items?
• When do you use minhash? And random projections?
• What are the knobs you control and what do they do?
• What makes certain types of clustering algorithms amenable to scale-out distributed processing?
• What are the parallels between k-means clustering and Gaussian Mixture Models?

• Pinecone: Locality Sensitive Hashing (LSH): The Illustrated Guide
• Pinecone: Random Projection for Locality Sensitive Hashing

The following are from online textbooks that explain what's covered in lecture. They are required to the extent that they help you understand what's covered in class. If you're confused about anything, consult these sources.

• Mining of Massive Datasets: Chapter 3, Finding Similar Items [Direct Link]
• Mathematics for Machine Learning: Chapter 11, Density Estimation with Gaussian Mixture Models

Note, readings refer to "banding" (i.e., b bands of r rows per band): this is the same idea as the slides, which refer to k minhash signatures (= row) n times (= band).

PDF slides for Nov 11 (v1.01) PDF slides for Nov 13 (v1.00)

• What are alternative approaches to representing graphs?
• Why are graph algorithms challenging in MapReduce/Spark?
• What is the general structure of graph traversals in MapReduce/Spark?
• Why (even) MapReduce/Spark (for graph processing)?

• Data-Intensive Text Processing with MapReduce:
  
  • Chapter 5. Graph Algorithms
• Scale Up or Scale Out for Graph Processing?

If you have further interest in the discussion on scale up vs. scale out for graph processing, you might want to read the sources cited in the paper — in particular, the Twitter WTF paper, the survey on graph processing systems, and the paper on COST by McSherry et al.

PDF slides for Nov 18 (v1.00) PDF slides for Nov 20 (v1.00)

• What are the challenges associated with stream processing?
• What are the common patterns in connecting data producers and data consumers?
• What are some common data structures and algorithms for processing unbounded streams?
• What's the distinction between event time and processing time?
• How do stream processing platforms fit into the lakehouse?

• Apache Beam: The world beyond batch: Streaming 101, Streaming 102. (These are long blog posts but they cover a lot of important concepts.)
• Kafka Streams in Action:
  
  • Chapter 1. Welcome to the Kafka event streaming platform (A nice overview of streaming platforms in general.)

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have go through the library's portal (i.e., search for the book title and follow the appropriate link).

The following are optional, primarily provided to enrich your understanding.

• If you're interested, here's my rant about the Lambda and Kappa architectures.
• Kafka Streams in Action:
  
  • Chapter 2. Kafka Brokers (A nice overview of Kafka specifically.)

PDF slides for Nov 25 (v1.00) PDF slides for Nov 27 (v1.00)