MATH3330
Big Data Computing
Streaming statistics, sketches and sampling, Monte Carlo simulation and variance reduction, large-scale optimization, randomized numerical linear algebra, and distributed and external-memory computation.
Your progress
0/ 24 sections marked complete
Next section: 1.1 Streaming statistics and stable block reduction
Completion marks are saved in this browser.
This course in the web
In the MATH3330 notes
- Theorem cards
- 54
- Definitions
- 45
- Counterexamples
- 26
- Concept lenses
- 19
- Histories of ideas
- 1
- Proof X-rays
- 27
Sections with a history of an idea
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 24 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 54 · Definitions 45 · Counterexamples 26 · Concept lenses 19 · Histories of ideas 1 · Proof X-rays 27
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 24 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 2 sections
Streaming statistics
Derive one-pass and mergeable mean–variance summaries, explain cancellation and reduction order, and audit the cost and correctness of a streaming implementation.
Theorems 4 · Definitions 3Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Streaming statistics and stable block reduction
Derive one-pass and mergeable mean–variance summaries, explain cancellation and reduction order, and audit the cost and correctness of a streaming implementation.
- 1.2
Count–Min sketches: frequency estimates in a stream
Prove a one-sided frequency estimate and a fixed-query error bound, with explicit hash and update assumptions.
Chapter 2 · 1 section
Mathematical simulation
Build unbiased simulation estimators, prove a finite-sample uncertainty bound, compare antithetic sampling fairly, and separate reproducibility from statistical validity.
Theorems 2 · Definitions 5Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Monte Carlo simulation: uncertainty and reproducibility
Build unbiased simulation estimators, prove a finite-sample uncertainty bound, compare antithetic sampling fairly, and separate reproducibility from statistical validity.
Chapter 3 · 1 section
Large-scale optimization
Derive conditional minibatch variance and a smooth stochastic descent bound, then compare batch size, memory, communication and optimization progress under explicit budgets.
Theorems 2 · Definitions 3Counterexamples 2Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Minibatch optimization and resource tradeoffs
Derive conditional minibatch variance and a smooth stochastic descent bound, then compare batch size, memory, communication and optimization progress under explicit budgets.
Chapter 4 · 5 sections
Mathematical data pipelines
Build and run a finite-memory synthetic-data pipeline, prove its centered sufficient-statistic updates, and separate schema validity, numerical accuracy and model fit.
Theorems 10 · Definitions 7Counterexamples 5Lenses 5Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
A streaming data pipeline from records to a fitted model
Build and run a finite-memory synthetic-data pipeline, prove its centered sufficient-statistic updates, and separate schema validity, numerical accuracy and model fit.
- 4.2
Block QR for tall least-squares problems
Preserve a multivariate least-squares objective while reducing data blocks using orthogonal transformations.
- 4.3
SVD least squares and truncated regularization
Use singular directions to understand rank, minimum-norm least squares and the cost of discarding unstable directions.
- 4.4
Sparse matrices: storage and matrix–vector products
Represent sparse records by rows, compute forward and transpose products, and account for their actual costs.
- 4.5
Conjugate gradients for sparse positive-definite systems
Solve a positive-definite quadratic with matrix–vector products, and understand the exact-arithmetic guarantees and practical stopping tests.
Chapter 5 · 1 section
Distributed computation
Implement exact keyed reductions, prove scheduling and floating-sum bounds, and distinguish arithmetic work, communication, skew and deterministic execution.
Theorems 3 · Definitions 3Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Partition, merge and the limits of parallel reduction
Implement exact keyed reductions, prove scheduling and floating-sum bounds, and distinguish arithmetic work, communication, skew and deterministic execution.
Chapter 6 · 1 section
Randomized numerical linear algebra
Implement importance-sampled matrix multiplication, prove its exact mean-square error, and derive a finite-vector random-sign guarantee without confusing unbiased matrices with unbiased solutions.
Theorems 4 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Randomized matrix products and finite sketches
Implement importance-sampled matrix multiplication, prove its exact mean-square error, and derive a finite-vector random-sign guarantee without confusing unbiased matrices with unbiased solutions.
Chapter 7 · 1 section
Variance reduction and geometry
Implement snapshot variance reduction, prove a strongly convex epoch contraction, and derive how a fixed preconditioner changes the geometry and smoothness assumptions.
Theorems 3 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Variance reduction and preconditioned optimization
Implement snapshot variance reduction, prove a strongly convex epoch contraction, and derive how a fixed preconditioner changes the geometry and smoothness assumptions.
Chapter 8 · 1 section
8. Variance reduction
Use control variates and distinguish independent pilots from reused samples.
Theorems 1 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Control variates and independent pilots
Derive a variance-minimizing control coefficient and distinguish fixed, independent-pilot and reused-sample choices.
Chapter 9 · 1 section
Finite Markov computation
Construct finite-target samplers, prove detailed balance and actual convergence, and compute stationary sample-mean variance without treating correlated states as independent.
Theorems 3 · Definitions 4Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Finite Metropolis–Hastings, Gibbs updates and dependent error
Construct finite-target samplers, prove detailed balance and actual convergence, and compute stationary sample-mean variance without treating correlated states as independent.
Chapter 11 · 1 section
Streaming sampling
Prove uniform sampling without replacement in one pass, merge partition reservoirs by a hypergeometric allocation, and implement exact finite-source decisions with explicit memory bounds.
Theorems 4 · Definitions 2Counterexamples 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Reservoir sampling and weighted partition merges
Prove uniform sampling without replacement in one pass, merge partition reservoirs by a hypergeometric allocation, and implement exact finite-source decisions with explicit memory bounds.
Chapter 13 · 1 section
Streaming ranks and quantiles
Use a uniform reservoir to estimate all finite-list ranks simultaneously and interpret quantiles with ties.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 13.1
Streaming ranks from a uniform reservoir
Prove a simultaneous finite-population rank bound and interpret approximate quantiles when values are tied.
Chapter 14 · 1 section
Sketches for signed streams
Prove signed point-query variance and median confidence under explicit random-function assumptions.
Theorems 2 · Definitions 3Counterexamples 1Lenses 1History 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 14.1
CountSketch for signed streams: variance and confidence
Construct signed frequency estimates, prove a tail-energy variance bound, and amplify confidence with independent rows and a median.
Chapter 15 · 1 section
Discovering frequent keys in streams
Discover all strictly frequent keys with a deterministic counter summary and an exact recount.
Theorems 3Counterexamples 2Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 15.1
Deterministic discovery of frequent keys with k counters
Prove the counter-accounting identity and the error bound for the k-counter frequent-items summary, show that every strictly heavy key survives, and use a second pass to remove false positives exactly.
Chapter 16 · 1 section
Probabilistic membership
Understand one-sided membership filters and their finite random-model guarantees.
Theorems 3 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 16.1
Probabilistic membership with Bloom filters
Derive one-sided membership guarantees and exact finite-size false-positive probabilities under an explicit hash model.
Chapter 17 · 1 section
Sliding windows
Analyze bounded-memory summaries for recent streaming data.
Theorems 1 · Definitions 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 17.1
Approximate counting in a sliding window
Bound memory and error for a deterministic bucket summary of recent binary events.
Chapter 18 · 1 section
Weighted stream sampling
Construct and combine fixed-capacity samples with unequal weights.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 18.1
Weighted sampling by exponential races
Derive a fixed-capacity weighted sample without replacement and its exact partition merge rule.
Chapter 20 · 3 sections
External-memory algorithms
Reason about computation when input exceeds working memory.
Theorems 5 · Definitions 4Counterexamples 3Lenses 3Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 20.1
External merge sort and block I/O
Derive the pass count, block transfers, and stability of a memory-bounded sort.
- 20.2
External sort-merge joins with duplicate keys
Merge sorted files, spill equal-key groups, and account for every block transfer under bag semantics.
- 20.3
External hash partition joins
Partition two files by key, preserve duplicate pairs, and account for skew and I/O.