BS Data Science and BSCS students can use this guide to study “Mining of Massive Datasets” by Jure Leskovec, Anand Rajaraman and Jeffrey D. Ullman. This page covers the third edition (the preface is dated July 2019), which the authors share as a free PDF on mmds.org. The book grew out of three Stanford courses and is about mining data so large that it does not fit in main memory, with many examples taken from the web.
It is an algorithms and theory book. Chapters cover MapReduce and Spark, minhashing and locality-sensitive hashing, stream sampling and Bloom filters, PageRank, A-Priori and PCY, large-scale clustering, online advertising, recommendation systems, community finding in social networks, SVD and CUR, and, in the last two chapters, machine learning and neural nets. Expect probability, linear algebra and proofs, with pseudocode and worked examples rather than a coding tutorial. The preface recommends a database course and a data structures and algorithms course first.
Book Overview
| Course | Data Mining / Big Data |
| Degree Programs | BSCS, BS Data Science |
| Level | Advanced undergraduate / graduate |
| Edition | Third edition (preface dated July 2019); the second edition (v2.1) and the first (Version 1.0) are also listed on the book page |
| Authors | Jure Leskovec, Anand Rajaraman and Jeffrey D. Ullman |
| Publisher | Cambridge University Press prints the book; the authors offer the PDF free on their site by agreement with the publisher |
| Total Chapters | 13 chapters, no parts or appendices (the PDF ends with an index) |
| Exercises | Exercises in every chapter, roughly 250 in all, with harder ones marked by one or two exclamation points; no solutions in the PDF |
| Companion Material | Lecture slides for Chapters 1–12 and video lectures for Chapters 2–12 on the book page |
| Language | English |
| Format | PDF — one file of 603 pages (about 3.6 MB) on the authors’ site; chapter-wise PDFs are also available |
Chapter List
The book has 13 chapters and no appendices. The blocks below follow its own chapter order. Each summary is written from the chapter’s text and its own end-of-chapter summary, not from the contents page.
Chapter 1: Data Mining
Difficulty: Easy · Key topics: data mining, modeling, Bonferroni’s Principle, TF.IDF, hash functions, indexes, secondary storage, power laws
The opening chapter defines data mining as building a model or an algorithm from data, and compares the statistical, machine-learning, computational, summarization and feature-extraction views of it. It then warns about over-mining: Bonferroni’s Principle says that if a pattern is expected to appear many times in purely random data, finding it proves nothing, and a counting example about suspicious events makes this concrete. The rest is a toolkit used later in the book: TF.IDF word importance, hash functions and indexes, the cost of disk access, the number e and power laws. It closes with an outline of the remaining chapters.
Key Points:
- A model is a summary of the data; often the hard part is building it and applying it is easy.
- Bonferroni’s Principle: if you look for a feature that random data would also contain in large numbers, the feature is not evidence.
- TF.IDF gives a high score to a word that is frequent in one document but appears in few documents overall.
- A hash function maps a key to a bucket number, and a good one spreads keys roughly evenly.
- Reading from disk is far slower than reading from main memory, so large-data algorithms try to keep what they need in memory.
- A power law has the form
y = c x^a, with a often near -2 (for example, in-links of the x-th most popular page).
Memory Tip: Think of Bonferroni’s Principle as “search enough noise and you will always find a pattern”: before trusting a discovery, ask how many such patterns pure chance would produce.
Common Mistake: Treating every pattern found in a huge dataset as meaningful without estimating how often the same pattern shows up in random data.
Important Questions:
- What is Bonferroni’s Principle? It is a warning that a feature expected to occur many times by chance in random data cannot be taken as a real signal, so mining for it is unreliable.
- What does a high TF.IDF score tell you? The word is rare across the collection but frequent in this document, so it is a good indicator of the document’s topic.
Chapter 2: MapReduce and the New Software Stack
Difficulty: Medium · Key topics: distributed file system, Map and Reduce, combiners, Hadoop, relational algebra, Spark, TensorFlow, communication cost, replication rate, reducer size
The chapter starts with cluster computing: compute nodes in racks, and a distributed file system that stores large chunks of about 64 megabytes, each copied on several nodes. MapReduce is then explained as a user-written Map function, a system-wide grouping by key and a user-written Reduce function, with a Master that reruns tasks on failed nodes. Examples include matrix-vector and matrix multiplication and relational-algebra operations such as join. Later sections cover workflow systems, Spark with resilient distributed datasets, TensorFlow and recursive systems, and then two analytical ideas: the communication-cost model with multiway joins, and the trade-off between reducer size and replication rate.
Key Points:
- Files in a distributed file system are split into chunks of about 64 MB, and each chunk is replicated on different nodes or racks.
- Map turns each input object into zero or more key-value pairs, and keys need not be unique.
- The system sorts and groups all pairs by key, and each Reduce call receives one key with the list of its values.
- A failed Map or Reduce task can simply be rerun because tasks deliver output only after they finish; only a Master failure forces a full restart.
- Spark keeps data as resilient distributed datasets, evaluated lazily, with a recorded lineage so lost data can be rebuilt.
- The communication cost of an algorithm is the sum of the input sizes of all its tasks; replication rate is communication per input.
Practice Tip: Work out word count on paper first: Map emits (word, 1) for every word and Reduce adds up each list. Then ask what a combiner would change on the Map side.
Common Mistake: Assuming every parallel algorithm fits MapReduce; the chapter itself says it is not a solution to every problem.
Important Questions:
- What do the Map and Reduce functions do? Map converts input items to key-value pairs; after grouping by key, Reduce combines the list of values for each key into the output.
- Why is communication cost often the main cost of a MapReduce algorithm? Each task usually does very simple work, so moving data to where it is used dominates the running time.
Chapter 3: Finding Similar Items
Difficulty: Hard · Key topics: Jaccard similarity, shingling, minhashing, signatures, locality-sensitive hashing, distance measures, AND/OR constructions, random hyperplanes
The chapter asks how to find near-duplicate documents or similar customers without comparing every pair. Documents become sets of k-shingles, and the Jaccard similarity of two sets measures how alike they are. Minhashing then compresses each large set into a short signature in which the chance of agreement equals the Jaccard similarity. Locality-sensitive hashing cuts signatures into bands and compares only the pairs that match in at least one band. The chapter then surveys distance measures (Euclidean, Jaccard, cosine, edit, Hamming), the general theory of LSH families, hash families for cosine and Euclidean distance, and string-index methods for very high similarity.
Key Points:
- Jaccard similarity is the size of the intersection divided by the size of the union; Jaccard distance is 1 minus that.
- A k-shingle is any k consecutive characters of a document, so a document becomes a set of shingles.
- The expected fraction of minhash positions on which two signatures agree equals the Jaccard similarity of the sets.
- With banding, a pair becomes a candidate only if its signatures are identical in at least one band; band size tunes false negatives against false positives.
- A distance measure must be symmetric, be 0 only for identical points and satisfy the triangle inequality.
- Random hyperplanes give a sketch of signs whose agreement estimates the angle between two vectors (cosine distance).
Practice Tip: Take three short sentences, build character 3-shingle sets, compute the Jaccard similarity by hand, then compare it with a minhash signature of 100 hash functions in Python. The estimate should land close to the exact value.
Common Mistake: Forgetting that LSH can miss similar pairs (false negatives), or mixing up similarity with distance when setting the threshold.
Important Questions:
- Why does minhashing preserve Jaccard similarity? For a random permutation, the first element of the union that appears lies in the intersection with probability equal to the Jaccard similarity, so two sets agree on a minhash with exactly that probability.
- What does the banding technique do? It splits each signature into bands and treats a pair as a candidate only when some band matches exactly, which avoids comparing all pairs.
Chapter 4: Mining Data Streams
Difficulty: Hard · Key topics: stream model, sampling, Bloom filters, distinct counts, moments, DGIM buckets, decaying windows
This chapter deals with data that arrives so fast it cannot be stored. It describes two strategies, keeping summaries and keeping a sliding window of recent data. It shows how to sample a stream by hashing a key, how a Bloom filter lets members through while rejecting most non-members, and how to estimate the number of distinct elements from the longest run of trailing zeros in hash values. It then estimates second and higher moments from random positions in the stream, counts ones in a window with exponentially sized buckets, and finishes with exponentially decaying windows, including tracking frequent elements.
Key Points:
- Hashing the key of each arriving element decides consistently whether all or none of that key’s elements enter the sample.
- A Bloom filter uses a large bit array and several hash functions; an element passes only if all its hashed bits are 1.
- For distinct counts, 2 raised to the longest run of zeros seen is the estimate, improved by averaging within groups and taking the median across groups.
- The k-th moment is the sum of the k-th powers of element counts; the 0th is the distinct count and the 1st is the stream length.
- With buckets of sizes that are powers of 2, a window of N bits is represented in O(log^2 N) space with error at most 50% in the basic version.
- In an exponentially decaying window, an element that arrived t steps ago has weight e^(-ct).
Memory Tip: A Bloom filter can say yes by mistake but never says no by mistake: members always pass, so the errors are false positives only.
Common Mistake: Expecting the bucket method to give an exact count of ones in a window; it gives an estimate with a stated error bound.
Important Questions:
- How does a Bloom filter work? Each member is hashed by several functions and the matching bits are set; a new element is accepted only if all of its hashed bits are already 1.
- How can you estimate distinct elements in a stream using little memory? Hash each element, track the longest run of trailing zeros, estimate 2 to that power, and combine many hash functions by averaging and then taking the median.
Chapter 5: Link Analysis
Difficulty: Medium · Key topics: PageRank, transition matrix, random surfer, dead ends, spider traps, taxation, topic-sensitive PageRank, link spam, TrustRank, HITS
The chapter explains how early search engines were fooled by term spam and how Google answered with PageRank, which scores a page as important when important pages link to it. PageRank is built as the principal eigenvector of the web’s transition matrix and as the long-run behavior of a random surfer. Dead ends and spider traps break the plain calculation, and a taxation parameter fixes them. The chapter then covers sparse storage and block-wise matrix-vector multiplication for web-sized graphs, topic-sensitive PageRank with teleport sets, spam farms, TrustRank and spam mass, and the hubs-and-authorities (HITS) method.
Key Points:
- Column j of the transition matrix holds 1/k for each of the k pages that page j links to.
- On a strongly connected graph, repeated multiplication of any starting vector by the transition matrix converges to PageRank after about 50 iterations.
- A dead end has no out-links and drains PageRank to 0; a spider trap keeps all the PageRank inside itself.
- Taxation uses a parameter beta, typically about 0.85: the new estimate is beta times the matrix product plus (1 – beta)/n for each page.
- Topic-sensitive PageRank gives the tax only to the pages in a teleport set for the chosen topic.
- A spam farm has a target page and many supporting pages; TrustRank uses trusted pages as the teleport set and spam mass compares PageRank with TrustRank.
Practice Tip: Build the transition matrix of a four-page graph in NumPy, start from a vector of 1/4 and multiply repeatedly. Then add a spider trap and apply taxation with beta = 0.85 to see the difference.
Common Mistake: Ignoring dead ends and spider traps and then wondering why the scores collapse to zero or pile up on a few pages.
Important Questions:
- What is a spider trap and how does taxation help? It is a set of pages with no links leaving it, which absorbs all PageRank; taxation lets surfers leave the trap at each step by teleporting elsewhere.
- What are hubs and authorities? Authorities are pages with valuable information and hubs are pages that link to many authorities; HITS computes both scores from recursive equations.
Chapter 6: Frequent Itemsets
Difficulty: Medium · Key topics: market baskets, support, association rules, confidence, interest, A-Priori, PCY, multistage, multihash, SON, Toivonen
The chapter uses the market-basket model, with items and baskets in a many-to-many relationship, to define frequent itemsets by their support and association rules by their confidence and interest. The main difficulty is memory, since counting pairs of items usually needs the most space, so it compares triangular-matrix and triple storage. The A-Priori algorithm uses monotonicity to count only candidate itemsets, and PCY, multistage and multihash improve it with hash tables on the first pass. The chapter then covers limited-pass methods, namely sampling, the SON algorithm and Toivonen’s algorithm, and frequent items in a decaying stream.
Key Points:
- The support of an itemset is the number of baskets containing it; it is frequent if its support reaches a threshold.
- The confidence of a rule is the probability of item j given a basket containing set I; interest is how far that confidence is from the overall frequency of j.
- Monotonicity: every subset of a frequent itemset is frequent, so a set with an infrequent subset can be skipped.
- A-Priori counts items on pass one and counts only pairs of frequent items on pass two.
- PCY hashes pairs into buckets on pass one and later counts only pairs that fall in frequent buckets.
- The SON algorithm finds frequent itemsets in chunks, then counts all candidates in a second pass, and suits MapReduce well.
Practice Tip: Write the two-pass A-Priori algorithm for pairs in Python on a small basket file. Print how many pairs you counted compared with the naive count of all pairs.
Common Mistake: Mixing up confidence and interest: a rule can have high confidence only because the item is bought in most baskets anyway.
Important Questions:
- Why is counting pairs the bottleneck? The number of possible pairs is huge, so the pair counts typically need more main memory than anything else in the computation.
- How does A-Priori use monotonicity? If an itemset is not frequent then none of its supersets can be, so each pass counts only itemsets whose smaller subsets were all found frequent.
Chapter 7: Clustering
Difficulty: Medium · Key topics: distance measures, hierarchical clustering, k-means, curse of dimensionality, centroid and clustroid, BFR, CURE, GRGPF, stream clustering
Clustering groups points so that distances inside a cluster are small and distances between clusters are large. The chapter separates hierarchical algorithms, which merge nearby clusters step by step, from point-assignment algorithms such as k-means. It explains the curse of dimensionality, where random points in high dimensions are almost equally far apart, and the difference between a centroid in Euclidean space and a clustroid elsewhere. Several choices are discussed: which clusters to merge, when to stop, how to pick initial centroids and the value of k. Then come algorithms for data that does not fit in memory, BFR, CURE and GRGPF, and clustering for streams and parallel systems.
Key Points:
- In high dimensions, random points are almost always at about the same distance and random vectors are almost orthogonal.
- A centroid is the average of points in a Euclidean space; in other spaces a clustroid, an actual member of the cluster, represents it.
- Hierarchical clustering can stop at a fixed number of clusters, at a diameter or radius limit, or at a density limit.
- K-means needs k in advance; if k is unknown, a search over k looks for where the average cluster diameter jumps.
- BFR keeps only a count, a vector sum and a vector of sums of squares for each cluster and assumes normal spread along the axes.
- CURE represents a cluster by several representative points moved part of the way toward the centroid, so clusters can have any shape.
Practice Tip: Run k-means on a small two-dimensional dataset for k = 1 to 8 and plot the average cluster diameter against k. The bend in the curve shows why the book searches for the right k.
Common Mistake: Averaging points to get a centroid in a space where averaging makes no sense, such as strings or sets; use a clustroid there.
Important Questions:
- What is the curse of dimensionality? In very high-dimensional spaces distances between random points become nearly equal, which makes distance-based clustering less informative.
- How does BFR cluster data too big for memory? It reads points in chunks and keeps only a small summary per cluster, plus miniclusters and retained points for points not yet assigned.
Chapter 8: Advertising on the Web
Difficulty: Medium · Key topics: on-line algorithms, competitive ratio, bipartite matching, greedy algorithm, adwords problem, Balance algorithm, bid matching
The chapter starts from the money behind web services: advertising chosen for each individual user. It contrasts off-line algorithms, which see all the data, with on-line algorithms that must answer each element immediately, and it measures them with the competitive ratio. Bipartite matching is the first example, where the simple greedy algorithm is shown to be at least half as good as the best off-line answer. The adwords problem adds bids, budgets and click-through rates, and the Balance algorithm gives better guarantees than greedy. The last section is about implementation, matching a search query or a larger document against stored bids.
Key Points:
- An on-line algorithm must respond to each stream element with knowledge of the past only.
- The competitive ratio compares the on-line result with the best off-line result, taken over the worst possible input.
- Greedy bipartite matching has a competitive ratio of 1/2.
- The Balance algorithm gives the ad to the bidder with the largest remaining budget.
- In the simplified adwords model Balance achieves 3/4 for two advertisers and 1 – 1/e, about 63%, for any number of advertisers.
- For generalized adwords, Balance picks the advertiser with the highest value of x(1 – e^(-f)), where f is the fraction of budget unspent.
Memory Tip: Remember the ladder of guarantees: greedy gives 1/2, Balance gives 3/4 for two advertisers, and Balance tends to 1 – 1/e (about 63%) as advertisers increase.
Common Mistake: Judging an on-line algorithm by how it does on one friendly input instead of by its ratio on the worst case.
Important Questions:
- What is the competitive ratio? It is the minimum, over all inputs, of the on-line algorithm’s result divided by the best possible off-line result.
- Why does Balance beat the simple greedy rule for adwords? It spreads queries over advertisers by giving them to whoever has the most budget left, so budgets are less likely to run out early and waste later queries.
Chapter 9: Recommendation Systems
Difficulty: Medium · Key topics: utility matrix, content-based recommendation, item and user profiles, collaborative filtering, cosine and Jaccard distance, UV-decomposition, RMSE, Netflix Challenge
The chapter models recommendation as a utility matrix of users and items in which most entries are unknown and the task is to predict the blanks. Content-based systems build item profiles from features such as important words, genres or tags, form user profiles from the items a user likes, and can also train a classifier per user. Collaborative filtering instead compares rows or columns of the matrix with Jaccard or cosine distance, usually after normalizing and sometimes after clustering. UV-decomposition estimates the blanks with two thin matrices, scored by root-mean-square error, and the chapter ends with the Netflix Challenge.
Key Points:
- A utility matrix records how much users like items; most entries are blank because most items are never rated.
- Content-based systems compare the profile of an item with the profile of a user; collaborative filtering compares users with users or items with items.
- Jaccard distance suits matrices of only 1s and blanks, while cosine distance handles general ratings.
- Subtracting row or column averages before measuring cosine distance removes rating-habit bias.
- UV-decomposition looks for thin matrices U and V whose product approximates the known entries and predicts the rest.
- RMSE is the square root of the average squared difference over the non-blank entries.
Practice Tip: Make a 5 by 5 ratings table by hand, subtract each user’s average rating and compute cosine similarity between two users. Use it to predict one blank entry.
Common Mistake: Treating blank entries as zero ratings; a blank means “not rated”, not “disliked”.
Important Questions:
- What is the difference between content-based and collaborative-filtering recommendation? Content-based methods use item features, while collaborative filtering uses the similarity of users’ ratings, with no knowledge of item features.
- What does UV-decomposition do? It approximates the utility matrix by the product of two thin matrices, so a few hidden factors explain preferences and blank entries can be predicted from the product.
Chapter 10: Mining Social-Network Graphs
Difficulty: Hard · Key topics: communities, betweenness, Girvan-Newman, complete bipartite subgraphs, normalized cuts, Laplacian matrix, affiliation-graph model, maximum likelihood, simrank, triangles, transitive closure
Social networks are large graphs with locality: small groups of nodes, called communities, have many more edges inside than the graph average. The chapter shows why communities differ from ordinary clusters, since people belong to several of them. It covers edge betweenness and the Girvan-Newman algorithm, communities as dense complete bipartite subgraphs found with frequent-itemset ideas, and graph partitioning with normalized cuts and the spectral method based on the Laplacian matrix. Overlapping communities are modeled with the affiliation-graph model and maximum-likelihood estimation. The chapter ends with simrank, triangle counting, and neighborhoods, diameter and transitive closure.
Key Points:
- The betweenness of an edge is the sum over node pairs of the fraction of shortest paths between them that use the edge.
- Girvan-Newman computes betweenness with a breadth-first search from every node and a labeling pass that shares path counts back along edges.
- A dense community contains a large complete bipartite subgraph, which can be found like a frequent itemset of size t with support s.
- The Laplacian matrix is the degree matrix minus the adjacency matrix; the eigenvector for the second-smallest eigenvalue suggests how to split the graph.
- In the affiliation-graph model, the chance of an edge is 1 minus the product of the chances that each shared community fails to create it.
- Triangles in a graph with m edges can be listed in O(m^(3/2)) time, and MapReduce can find them in one round as a three-way join.
Practice Tip: Build the Laplacian of a small graph in NumPy, find its eigenvectors and split the nodes by the sign of the second-smallest eigenvector. Check that the cut is small and the two sides are balanced.
Common Mistake: Treating communities as clusters: in a social network a node can belong to several communities, so standard clustering with distances works poorly.
Important Questions:
- What is edge betweenness and how is it used? It measures how many shortest paths run through an edge; removing edges of high betweenness separates the graph into communities.
- What is a normalized cut? It divides the size of a cut by the volume of each side and adds the two ratios, so low values mean a small cut between two reasonably large parts.
Chapter 11: Dimensionality Reduction
Difficulty: Hard · Key topics: eigenpairs, power iteration, principal-component analysis, singular-value decomposition, concepts, CUR decomposition
The goal of dimensionality reduction is to replace a large matrix by smaller ones whose product approximates it. The chapter starts with eigenvalues and eigenvectors of symmetric matrices and power iteration, which finds eigenpairs one at a time. Principal-component analysis treats data points as rows of a matrix and finds the directions along which the points line up best. Singular-value decomposition writes a matrix as U, a diagonal matrix of singular values, and V transposed, and reads the singular values as the strengths of hidden concepts such as movie genres. Dropping the smallest ones gives the best approximation, and CUR decomposition keeps real rows and columns so sparse matrices stay sparse.
Key Points:
- An eigenpair satisfies Mv = (lambda)v: multiplying the matrix by the eigenvector gives a multiple of itself.
- Power iteration multiplies a starting vector by the matrix again and again until it settles on the principal eigenvector.
- In PCA, the eigenvectors of the product of the data matrix with its transpose give the directions of greatest variation.
- In SVD, U and V are column-orthonormal and the diagonal matrix holds the singular values.
- Deleting the columns for the smallest singular values minimizes the error in reconstructing the original matrix.
- SVD factors of a sparse matrix are dense; CUR chooses rows and columns with probabilities based on the Frobenius norm to keep them sparse.
Practice Tip: Use numpy.linalg.svd on a small users-by-movies matrix, set the smallest singular values to zero and rebuild the matrix. Compare the error for different numbers of kept values.
Common Mistake: Assuming the SVD of a sparse matrix is also sparse; U and V are normally dense, which is the reason CUR exists.
Important Questions:
- What are the three matrices in SVD? U links rows to concepts, the diagonal matrix of singular values gives each concept’s strength, and V links concepts to columns.
- Why is zeroing the smallest singular values a good approximation? It removes the weakest concepts, and among all choices with the same number of columns it gives the smallest reconstruction error.
Chapter 12: Large-Scale Machine Learning
Difficulty: Hard · Key topics: training and test sets, overfitting, perceptrons, Winnow, support-vector machines, gradient descent, nearest neighbors, decision trees
The chapter begins with the machine-learning setup: training examples as feature vectors with labels, test sets to detect overfitting, batch versus on-line learning and the architecture used for large data. Perceptrons and the Winnow algorithm learn a separating hyperplane, with extensions for varying thresholds, several classes, nonlinear transformations and parallel implementation. Support-vector machines add the idea of maximum margin and are solved by gradient descent, including stochastic and minibatch forms. Nearest-neighbor learning, regression and kernel methods follow. The chapter ends with decision trees, impurity measures, node design, pruning and forests, and a comparison of methods.
Key Points:
- A training example is a feature vector plus a label; a held-out test set shows whether a model has overfit.
- Batch learning can reuse the training set in many passes, while on-line learning sees each example once.
- A perceptron adjusts a hyperplane by a learning-rate fraction of the misclassified points’ direction; it works only if a separating hyperplane exists.
- An SVM maximizes the margin, and the points exactly at the minimum distance are the support vectors.
- Stochastic gradient descent updates after one example, minibatch after a small subset and batch after all of them.
- Decision-tree impurity can be measured by accuracy error, Gini (1 minus the squared class fractions) or entropy.
Practice Tip: Generate two clouds of points in two dimensions, train a perceptron on them and watch the hyperplane move as it fixes mistakes. Then overlap the clouds and see why a plain perceptron cannot converge.
Common Mistake: Judging a classifier on the same data it was trained on; only test-set performance shows whether it generalizes.
Important Questions:
- How does an SVM improve on a perceptron? Instead of any separating hyperplane, it picks the one with the widest margin and can allow a penalized number of points inside the margin.
- What is overfitting and how do you detect it? It is fitting quirks of the training data; the model does clearly worse on a held-out test set than on the training set.
Chapter 13: Neural Nets and Deep Learning
Difficulty: Hard · Key topics: layers, activation functions, loss functions, backpropagation, convolutional networks, recurrent networks, LSTM, regularization
This is the newest chapter, added in the third edition and kept under 50 pages. It introduces a neural net as layers of perceptron-like nodes: fully connected, pooled and convolutional layers. Dense feedforward networks are set out in linear-algebra notation with the common activation functions (sigmoid, hyperbolic tangent, softmax, rectified linear unit) and with regression and classification losses. Backpropagation is explained with compute graphs, Jacobians and the chain rule, followed by gradient-descent iteration and tensors. Convolutional networks, recurrent networks with the vanishing-gradient problem, and LSTM follow, and the chapter ends with regularization.
Key Points:
- A node outputs an activation function applied to the weighted sum of its inputs, and hidden layers learn intermediate concepts.
- Common activation functions are the sigmoid, the hyperbolic tangent, softmax and rectified linear units.
- Backpropagation applies the chain rule layer by layer from the output back to the input to get the derivative of the loss for every weight.
- In a convolutional layer, nodes at different pixel positions share the same weights, so only one set per family is learned.
- An LSTM adds a cell state and learned gate vectors that decide what to keep from the input, the state and the output.
- The text does not cover transformers, attention mechanisms or embeddings.
Practice Tip: Code a two-layer network with sigmoid activations in NumPy, write its backpropagation by hand and check the gradients against a small numerical estimate.
Common Mistake: Confusing the activation function (inside the network) with the loss function (which scores the output); backpropagation needs both to be differentiable.
Important Questions:
- What is backpropagation? It computes the derivative of the loss with respect to every weight by applying the chain rule from the output layer back to the input, so gradient descent knows how to adjust the weights.
- Why do LSTMs help recurrent networks? The extra cell state and gates let useful information about the sequence survive for a long time, which eases the vanishing-gradient problem of plain recurrent networks.
How to Study This Book
The free PDF is the third edition: 603 pages and 13 chapters, with no parts or appendices declared. The preface says the book is about data mining of very large data, meaning data that does not fit in main memory, and that it takes an algorithmic point of view: data mining is applying algorithms to data rather than using data to train a machine-learning engine. It grew out of the Stanford courses CS246, CS345A and CS341. Expect pseudocode, worked examples and analysis, not a programming tutorial. The only code-like material is the short Spark and TensorFlow discussion in Section 2.4, so this is a theory and algorithms book, not a tools book.
Check your background first. The book page calls it undergraduate level with no formal prerequisites, but the preface recommends an introductory database course with SQL, a sophomore course in data structures, algorithms and discrete mathematics, and a sophomore course in software systems or programming languages. In practice you also need probability for Chapters 3, 4 and 8, linear algebra for Chapters 5, 9 and 11 and basic calculus for Chapters 12 and 13. Chapter 1 recaps some of the toolkit, namely hash functions, indexes, secondary storage and power laws, so read it even if it feels easy.
For a first course in data mining or big data, read in order: Chapter 1, then Chapter 2 up to Section 2.3 (distributed file systems, MapReduce and its basic algorithms), Chapter 3 up to Section 3.4 (shingling, minhashing and locality-sensitive hashing), Chapter 4 up to Section 4.4 (sampling, Bloom filters and distinct counts), Chapter 5 up to Section 5.3 (PageRank and topic-sensitive PageRank), Chapter 6 up to Section 6.3 (market baskets, A-Priori and PCY) and Chapter 7 up to Section 7.3 (hierarchical clustering and k-means). These sections are the core of most syllabi built on this book.
Some chapters depend on others. Chapter 3 introduces the distance measures used again in Chapters 7 and 9. Chapter 5 uses the matrix-vector multiplication of Section 2.3 and the principal-eigenvector idea that Chapter 11 develops in full. Chapter 10 reuses frequent itemsets from Chapter 6 for finding bipartite subgraphs, MapReduce from Chapter 2, and the eigenvalue material of Chapter 11 for spectral partitioning. Section 9.4 on UV-decomposition pairs naturally with Chapter 11 on SVD. Chapter 13 builds directly on perceptrons and gradient descent in Chapter 12, so read them in that order if machine learning is your goal.
Leave the heavier theory for a second pass. Sections 2.5 and 2.6 (communication cost and the complexity theory of MapReduce), Sections 3.6, 3.7 and 3.9 (the theory of locality-sensitive functions and methods for high similarity), the moment and counting-ones sections of Chapter 4, the competitive-ratio arguments of Chapter 8, and Sections 10.6 to 10.8 (simrank, triangles and neighborhoods) are aimed at graduate courses. You can follow the main ideas through each chapter’s own summary and come back for the details.
The exercises are the real practice. Almost every section has them, roughly 250 in all, and harder ones are marked with an exclamation point, or two for the hardest. The PDF has no solutions. The official page also offers lecture slides for Chapters 1 to 12 and video lectures for Chapters 2 to 12, and the preface mentions a separate automated homework system. A useful habit is to implement one algorithm per chapter on a small dataset in Python, such as minhash signatures, PageRank with NumPy, A-Priori on baskets, k-means and an SVD of a ratings matrix, and compare the output with the book’s examples.
Know the limits before you rely on it. This is a 2019 edition, and the emphasis on MapReduce and Hadoop reflects that period, although the algorithms themselves (locality-sensitive hashing, stream summaries, PageRank, A-Priori, BFR and CURE, SVD) have not aged. Chapter 13 is a short introduction to feedforward, convolutional and recurrent networks and has no coverage of transformers, attention or embeddings, so pair it with a current deep-learning text. The authors list corrections for the third edition on an errata page linked from the book page.
Used In These Programs
This book is used for Data Mining and Big Data courses in: BS Computer Science · BS Data Science. Browse all Data Mining books or all Computer Science books.
Who Should Read This
This book is for BS Data Science and BSCS students in the upper semesters who are taking a data mining, big data or web mining course, and for MS students who want the algorithms behind search engines, recommendation systems, stream processing and social-network analysis. It suits students who are comfortable with algorithms and proofs and want to know how a method scales to data that does not fit in memory. It is not a first book on data analysis, machine learning or programming, and it will not teach you pandas, scikit-learn or Spark commands. If your algorithms background is thin, Algorithms (DPV) and Mathematics for Computer Science cover the discrete math and probability it assumes. Think Stats is a gentler start for the statistics, and Database Management System covers the SQL and relational background that Chapter 2 builds on. Students preparing for MS entry tests or graduate admissions in data science will find Chapters 3, 5, 6, 7, 9, 11 and 12 the most useful.
Applicable Universities
This book is useful for students at Pakistani universities offering BS Computer Science and BS Data Science with a data mining, big data or web mining course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.
Official Copy of Mining of Massive Datasets
The authors offer the full third edition as a free PDF on their book page, together with slides for most chapters. Click below to open the official page and download the book.
→ Visit Official PageFAQs
Is Mining of Massive Datasets free?
Yes. By agreement with the publisher, the authors let you download the PDF for free from mmds.org. It is not an open-licence book: Cambridge University Press retains copyright, and the authors expect you to get the publisher’s permission and acknowledge them if you republish any part of it. Use the official page rather than reposting the file.
Which edition is this?
This page covers the third edition, a 603-page PDF whose preface is dated July 2019. The book page says it adds material on Spark, TensorFlow, minhashing, community finding, simrank, graph algorithms and decision trees, and a new Chapter 13 on deep learning. The older second edition (511 pages) and Version 1.0 (340 pages) are still listed, and an errata page for the third edition is linked from the book page.
How many chapters and exercises does it have?
There are 13 chapters. Almost every section ends with exercises, roughly 250 numbered ones in total, and harder ones are marked with an exclamation point or two. The PDF contains no solutions. The authors’ page also offers lecture slides for Chapters 1 to 12 and video lectures for Chapters 2 to 12, and the preface mentions a separate automated homework system.
Is it good for complete beginners?
No. The book page describes it as undergraduate level with no formal prerequisites, but the preface recommends an introductory database course with SQL, a sophomore course in data structures, algorithms and discrete mathematics, and a course in software systems. You also need probability, linear algebra and some calculus for the later chapters. Beginners should start with a lighter data analysis or statistics text first.
Does it cover machine learning, Spark and deep learning?
Partly. Chapter 12 covers perceptrons, support-vector machines, nearest neighbors and decision trees, and Chapter 13 introduces feedforward, convolutional and recurrent networks, LSTM and regularization. Spark and TensorFlow appear only briefly in Section 2.4. The book does not teach tools or libraries, and it has no coverage of transformers, attention or embeddings.
Is it still current in 2026?
The core algorithms are: locality-sensitive hashing, stream summaries, PageRank, A-Priori, BFR and CURE clustering, SVD and CUR have not changed in substance. What has aged is the emphasis on MapReduce and Hadoop and the short, introductory neural-network chapter, which predates transformers. The edition dates from 2019, so pair it with a current machine learning text and check the book page for anything newer.
Related Books
- Algorithms (DPV) – Dasgupta, Papadimitriou & Vazirani
- Think Stats: Exploratory Data Analysis in Python – Allen B. Downey
- Mathematics for Computer Science – Lehman, Leighton & Meyer (MIT OCW)
- Database Management System – IT Series (3rd Edition)
This book gives you the algorithms behind search engines, recommendation systems, stream processing and social-network analysis, from MapReduce and locality-sensitive hashing to SVD and neural nets, in one free PDF. Browse more Computer Science books for the rest of your semester.
Mining of Massive Datasets, third edition (preface dated July 2019) by Jure Leskovec, Anand Rajaraman and Jeffrey D. Ullman. The PDF carries a copyright notice in the authors’ names, and the book page states that Cambridge University Press, which publishes the printed book, retains copyright; the authors offer the PDF free on their website by agreement with the publisher. No open licence applies, and the authors ask for the publisher’s permission and an acknowledgement if parts are republished. Official source: http://www.mmds.org/. This page links to the official site and does not host or copy the book.
© Copyright Policy
Freebooks.pk is an educational resource for students in Pakistan. Textbooks and other books belong to their respective boards, authors and publishers, and all rights remain with them. If you are the copyright holder of any material on this page and want it changed or removed, please contact us or file a request under our DMCA policy. We review every request and remove reported content promptly.
