Now let's look at some examples of algorithms implemented in parallel using
map-reduce. For those of you used to relational
databases, here's how one can implement a join using map-reduce.
Suppose we are given two tables, sales by address and cities by address and we are
interested in joining these tables to find the sales by city.
In sequel, this is how you'll do it. You would simply select the sum of sales
from these two tables, where the addresses match, and group them by city.
However in map-reduce, this requires two map-reduce jobs.
In the first case, you join or essentially sort the data by address so that each
reducer is able to emit the city for every sale.
So in other words, the first map-reduced task only joins the sales and city table
but doesn't do the grouping. In the second map produced task we sort on
the city key so that all the records for a particular city comes to the same reducer
where the addition takes place. Notice that we couldn't have used a single
map-reduce raise because at the end of the first phase, it's not possible to
guarantee that all the data for a particular city resides in the same
reducer and so the summation can't be done, at least city-wise in a single
phase. I'll relate to you a real world story that
illustrates the difference between the map-reduce way of thinking and a
traditional database approach. This is a real example where an
organization had lots of data which could be abstracted as data about papers their
authors and their contents. The actual nature of the data is
proprietary so I won't relate that in detail.
But it's pretty much the same problem as this.
There are millions of papers written by many millions of authors containing
millions of possible technical terms, phrases, you know, multi-word terms.
And one of the tasks was to figure out the top ten technical terms used by each
author. The top ten authors that used a particular
term, and so on. And you can see this, problem is quite
close to our word counting example. And possibly indicates a real life,
requirement as well. This is how a database person actually
propose the solution. You start out with a bunch of documents
represented as a table with say a paper ID.
The content of the document itself and its author.
Then you get rid if the actual content and replace it by words.
Notice what has happened over here. Instead of one row per paper, now you only
have a row for a word and answer pair that occurs in a particular paper.
So, one row here will produce many, many rows in the table queue.
No matter, says our database expert. All we need to do is now to group by, so
that we can count how many times a particular word is used by a particular
author. So the resulting table, would let you
answer questions about, which of the top ten technical terms used by a particular
author, by simply, finding all the entries for an author, sorting them by word count,
and you have your answer. Problems start to occur when you try to
consider how large these tables can get. If this P has million or a few million
documents, then let's take a look at this table here.
At worst, you'll have an entry for every word and every author that is if you allow
zero word counts. That works out to million into million or
a trillion entries. Even if you don't have zeros, and you get
rid of them by a suitable modifications to your joining and counting process.
You'll still have many billions of entries in this table merely to solve this kind of
a problem. Now suppose you wanted to find the top ten
authors for two terms. They are a combination of terms or you
wanted to find the top ten terms for two authors who wrote together.
This solution doesn't work anymore. So, we see that the database mindset
doesn't quite work in such high dimensional spaces where you have millions
of terms and millions of authors. And you are trying to find counts of
combinations between them. This is really a case for map-reduce and
it is exactly these types of challenges which lead the web companies to develop
new technologies, and new programming paradigms.
It was not just that the old technologies didn't scale, it's the fact that the
relational paradigm itself needed to be looked at fresh, when dealing with large
volumes of unstructured data. Okay, so lets try doing top key words per
author in map-reduce. Well, suppose we use the map function
where you emit a word and author every time you see it in a document just like we
emitted the word and its counts earlier. And the reduce key is a word author
combination. So that every reducer gets all the records
which have one such combination, and can simply count them.
Well, this doesn't quite solve the problem or does it?
Actually it's the same problem as before, a database mindset being used with map
produce. So it's the, programming paradigm is not a
solution by itself. The, approach really needs to change from
a data base oriented one, to something else.
Let's try it again. Again, we have a map function but this
time instead of emitting the author and the word, we emit the author and the
contents. So essentially all the map phases doing is
extracting the author field, and emitting it along with the contents.
In the reduced phase we group everything by author so that all the documents for a
particular author end up being in the same reducer and in the reduced function is a
custom function which works as follows. For each author, this reduced function
grabs, all the elements in that reducer for that author.
Computes the word counts, inserts into some temporary array W, Sorts it.
There goes out the top K word for that author.
Deletes the W and starts again for the next author.
Essentially, you're computing the top k for each author.
Not storing the combination of each word author.
Because you're only interested in the top K, the top ten, the top five, the top
twenty, whatever. Notice what we've done here.
We are bringing some element of programming back into, the reduced
function. And not relying entirely on the system,
map produced in this case, or the database in the previous case, to do all our work.
Now let's look at some more examples, such as those we've considered in the past few
weeks. Indexing, locality sensitive hashing.
In particular, how to assemble the results from many different hash functions.
How to compute the likelihoods while coming up with a Bayesian classifier.
And, how to evaluate a Bayesian classifier to compute the likelihood ratio?
Do you alctually need parallelism to do this?
How about computing the TF-IDF or the joint probabilities for computing the
information gain or mutual information? I'll leave these last three as homework
for you. And we'll just do the first three right
now. Let's start with indexing.
In the map phase, we produce a partial index for a partial set of documents that
is, we emit for every word, a postings list, out of all the documents that we
see. This is not a full index so we have to
reduce, again by word, and merge the partial indexes.
That is merge these postings list per word into a common postings list.
An interesting question is what if you have to sort either by document ID or by
page rank as we had in our first homework assignment.
What do you think you need to do then? Would you need another map-reduce phase?
Think about it. Now let's consider locality sensitive
hashing. The map phase, you start with documents
and compute K hash values for every document.
These could be the K hashwell use be used for fingerprints, or they could be others,
as I described in the Rodger Almond book for documents.
The reduced key has now the K hash functions.
Each reducer gets all those documents that have the same K hash values.
And figures out all the pairs that they could possibly forms.
So if there are three documents, it emits three pairs.
If there are four documents, it emits six pairs and so on.
As a result, the map-reduce LSH, produces a list of document pairs, which are
potentially similar. An interesting question is, will the
document pair be emitted by more than one reducer?
And suppose we, wanted, each pair to be emitted, only once.
What would we do then? Lastly, let's come to our Bayesian
classifier, where we need to compute the likelihoods, or rather the conditional
probabilities of a yes occurring, or a no occurring, for each possible feature.
So the map phase, merely produces the counts of feature yes or feature no which
are then, grouped, by, features in the reduced phase, so that we get, all the,
counts, that were emitted for a particular feature, in one reducer where we merely
sum up, the respective counts, and divide by the total number of instances that
we've seen, for a particular feature. Finally we emit the log of this
likelihood, so that we get the elements of out beigen classifier.
Notice that once we have the log likelihoods for each feature, do we really
need parallelism for testing new documents or new objects using the naive based
classifier? Think about it.
Is that computation really that large as to require parallel computing?
Well we've seen a number of examples of map-reduce.
Admittedly the last few have been covered rather quickly.
Please review the material so that you understand it and discuss it if you don't
in the forum.