1.4. OUTLINE OF THE BOOK
17
1.4
Outline of the Book
This section gives brief summaries of the remaining chapters of the book.
Chapter 2 is not about data mining per se.
Rather, it introduces us to
programming systems that facilitate parallel processing of massive amounts of
data. We discuss the cloud-computing architecture, which uses large numbers
of connected processors. We discuss in detail programming systems based on
MapReduce, and oﬀer MapReduce-based algorithms for a number of common
operations using in processing massive datasets.
Chapter 3 is about ﬁnding similar items. Our starting point is that items
can be represented by sets of elements, and similar sets are those that have a
large fraction of their elements in common. The key techniques of minhashing
and locality-sensitive hashing are explained. These techniques have numerous
applications and often give surprisingly eﬃcient solutions to problems that ap-
pear impossible for massive data sets.
In Chapter 4, we consider data in the form of a stream. The diﬀerence
between a stream and a database is that the data in a stream is lost if you do
not do something about it immediately. Important examples of streams are the
streams of search queries at a search engine or clicks at a popular Web site. In
this chapter, we see several of the surprising applications of hashing that make
management of stream data feasible.
Chapter 5 is devoted to a single application: the computation of PageRank.
This computation is the idea that made Google stand out from other search
engines, and it is still an essential part of how search engines know what pages
the user is likely to want to see. Extensions of PageRank are also essential in the
ﬁght against spam (euphemistically called “search engine optimization”), and
we shall examine the latest extensions of the idea for the purpose of combating
spam.
Then, Chapter 6 introduces the market-basket model of data, and its canon-
ical problems of association rules and ﬁnding frequent itemsets. In the market-
basket model, data consists of a large collection of baskets, each of which con-
tains a small set of items. We give a sequence of algorithms capable of ﬁnding
all frequent pairs of items, that is pairs of items that appear together in many
baskets.
Another sequence of algorithms are useful for ﬁnding most of the
frequent itemsets larger than pairs, with high eﬃciency.
Chapter 7 examines the problem of clustering. We assume a set of items
with a distance measure deﬁning how close or far one item is from another.
The goal is to examine a large amount of data and partition it into subsets
(clusters), each cluster consisting of items that are all close to one another, yet
far from items in the other clusters.
Chapter 8 is devoted to on-line advertising and the computational problems
it engenders. We introduce the notion of an on-line algorithm – one where a
good response must be given immediately, rather than waiting until we have
seen the entire dataset. The idea of competitive ratio is another important
concept covered in this chapter; it is the ratio of the guaranteed performance of
