Algorithms for Data Mining, Web, and Social Networks

Large-data algorithms and approximation

Large datasets change which resources dominate an algorithm. An exact method that fits a mathematical time bound may still need too much memory, too many passes, or too much communication. State the computation model and acceptable error. Streaming algorithms process limited observations with bounded memory; approximate methods trade controlled error for lower resource cost. Distinguish a probabilistic guarantee over an algorithm's random choices from a claim that every real dataset follows a convenient distribution.

References: Mining of Massive Datasets — authors' public textbook site

Similarity, minhash, and locality-sensitive hashing

Similarity requires a representation and metric. Jaccard similarity compares sets through intersection divided by union. Under a uniformly random permutation, the probability that two sets share the same minimum element equals their Jaccard similarity. Repeated minhash values estimate that quantity. Locality-sensitive hashing turns signatures into candidate pairs, reducing exhaustive comparisons. Candidate generation can introduce false positives and false negatives, so verify candidates with the intended similarity measure and choose parameters for the desired tradeoff.

References: Mining of Massive Datasets — authors' public textbook site

Sampling and sketching streams

Reservoir sampling keeps a uniform sample of a stream without knowing its final length. For a reservoir of size k, the i-th item after initialization is admitted with probability k/i, replacing a uniformly selected reservoir entry. Sketches summarize counts or distinctness through randomized structures, with guarantees tied to assumptions and parameters. Repeated items matter differently for sampling events and sampling distinct keys. Specify whether the target population consists of occurrences, users, or unique values.

References: Mining of Massive Datasets — authors' public textbook site

Link analysis and a worked PageRank step

Represent links as a transition matrix and use a damping model to combine following a link with teleportation. For an original three-node graph A->B, B->A,C, and C->A, start with equal rank 1/3 and damping 0.85. A receives 1/6+1/3 of link-following mass, B receives 1/3, and C receives 1/6. Adding teleportation 0.15/3 gives new ranks 0.475, approximately 0.3333, and approximately 0.1917. They sum to one. Dangling nodes require an explicit redistribution rule.

References: Mining of Massive Datasets — authors' public textbook site

Recommendation and dimensionality reduction

Collaborative filtering predicts preferences from interaction patterns; content-based methods use item or user attributes. Missing interactions are not automatically negative preferences because exposure and selection affect what is observed. Matrix factorization represents users and items through lower-dimensional latent vectors, usually optimized against an observed-data objective and regularization. Split evaluation to reflect time and availability at recommendation time. A random row split can leak a user's future preferences into training and overstate deployment quality.

References: Mining of Massive Datasets — authors' public textbook site

Clustering, social graphs, and online decisions

Clustering optimizes a chosen notion of cohesion, so feature scaling and distance choice can dominate the result. Graph communities can reflect dense connectivity, but a detected cluster is not automatically a meaningful social group. Online algorithms make decisions before future inputs arrive and may be assessed by competitive analysis against a stronger offline benchmark. For every result, state the objective, baseline, randomness, and information available. Reproducible experiments need fixed data preprocessing and reported variability, not only a favorable run.

References: Mining of Massive Datasets — authors' public textbook site

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Carleton COMP 4801 — Fall 2026 outline ↗Course scope · Fall 2026
• Mining of Massive Datasets — authors' public textbook site ↗Author textbook; recommended in official outline
• Carleton COMP 4801 — Fall 2026 algorithm topic map and readings ↗Topic map