Skip to content

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.

17 chapters · 24 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.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.

  2. 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

  1. 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

  1. 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

  1. 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.

  2. 4.2

    Block QR for tall least-squares problems

    Preserve a multivariate least-squares objective while reducing data blocks using orthogonal transformations.

  3. 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.4

    Sparse matrices: storage and matrix–vector products

    Represent sparse records by rows, compute forward and transpose products, and account for their actual costs.

  5. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 20.1

    External merge sort and block I/O

    Derive the pass count, block transfers, and stability of a memory-bounded sort.

  2. 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.

  3. 20.3

    External hash partition joins

    Partition two files by key, preserve duplicate pairs, and account for skew and I/O.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details