1
$\begingroup$

I am interested with Map and Reduce operations in computer science. I would like to do analogies with Mathematics and especially with Linear Algebra.

  1. Reduce

First, could we say that "Reduce" operation can be translated as a linear form, ie I start from a vector and I get a scalar from the coordinates of the initial vector ?

But a linear form is by definition linear, is it always the case for Reduction in computer science ?

  1. Map

Secondly, could we say that "Map" can be translated as an endomorphism, i.e we start from an initial vector (like a list in computer science) and we get also a vector as output.

If I take "Map" operation, and f a function, I have :

$f[x_{1}, x_{2} ..., x_{n}] = [ f(x_{1}), f(x_{2}), ..., f(x_{n})]$

I could write it like this :

$f[\vec{X}] = f [\sum_{i=1}^{n}\,x_{i}\,\vec{e_{i}}]= \sum_{i=1}^{n}\,x_{i}\,\vec{f(e_{i})}=\sum_{i=1}^{n}\,x_{i}\,F_{ij}\,\vec{e_{j}}=[f(x_{1}), f(x_{2}), ..., f(x_{n})]$

So I get : $f(x_{j})=\sum_{i=1}^{n}\,F_{ij}\,x_{i}$ with $F_{ij}$ called the matrix of change basis of the endomorphism "f"

But I don't get this relation above, well known between a change of basis (Matrix $F_{ij}$) and coordinates into 2 basis :

$x_{j} = F_{ij}\,x'_{i}$

I don't know how to make correct connections between Linear algebra and "Map,Reduce" operations ?

If someone could help to Conceptualize these operations, this would be nice.

Thanks

PS: don't hesitate to transfer this question to mathematics exchange community if necessary.

$\endgroup$
3
$\begingroup$

There really is no obvious connection between MapReduce and linear algebra. It is true that some linear algebra operations could be written as MapReduce operations, but the converse is not true.

I think it's useful to give an example of what MapReduce is intended to do. Let's assume you are looking for the closest coffee shop and that you have a database of all businesses in your town. Then the "Map" operation would extract from the database all businesses that are coffee shops, extract their location, and compute the distance to your current location. Then, the "Reduce" operation would take the minimum of these to get you the closest coffee shop.

Obviously, the "Map" phase is not a linear transformation from database entries to distances; nor is the "Reduce" operation (taking the minimum) a linear operation.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.