What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Questions tagged [mapreduce]

The tag has no usage guidance.

14 questions
Filter by
Sorted by
Tagged with
228 views

### Are there any non-naive parallel sparse matrix multiplication algorithms?

I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on ...
38 views

### Is there a name for “yield first result parallel map”?

Context In randomized algorithms two schemes of computation are common: Las Vegas algorithms with random running time Randomized algorithms that have a probability of success, and have to be ...
1k views

### Decidability of Unary Languages / One-to-One Mapping

I'm trying to prove that there exists an undecidable subset of {1}* by showing a one-to-one correspondence between it and {0, 1}* (which would imply a one-to-one correspondence between their power ...
684 views

### Implement K-means clustering with Map-Reduce

Recently in an interview I was asked to implement k-means clustering using the Map Reduce architecture. I know how to implement a simple k-means clustering algorithm but couldn't wrap my head around ...
32 views

### numeric stability of map reduce operations

I am building a small library for computing information retrieval metrics for classifiers (precision, recall, f1, accuracy, whatever). Typically each metric is built by calculating a single value for ...
29 views

### Partitioning millions of items into groups based upon a network of set similarities

So I'm working on a problem at work related to the matching of authors of millions of documents. I currently have minhash sets for each document's syntax (sets of 10 numbers with 8-10 digits each), ...
636 views

### How does this reduction to prove undecidability account for epsilon?

I have the following proof that the Empty String problem: ES = {M | M accepts $\epsilon$} is undecidable: $f<M,w>$ = Construct a new machine $M_2$ such that: $M_2$ = given input x erase x ...
14 views

### N-dimensional generalization of map and reduce?

Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)? For mapping, I guess it would be a point-wise ...
33 views

### Why in the Map Reduce Implementation, why not stream the records to the reducer (via TCP) as they are being produced by the mappers?

In the Map-Reduce implementation, the reducers start when all mappers finish their jobs. Why don't we stream the records from mappers to reducers while they are being processed instead? I think there ...
25 views

### Clarification on MapReduce description in textbook

I am reading through chapter 2 of of the free textbook "Mining of Massive Datasets" (http://www.mmds.org/). On page 28 the following is stated: "It is reasonable to create one Map task for every ...
155 views

### Can map-reduce speed up the count-min-sketch algorithm?

Is there any possibility of improvement in the result of count-min-sketch algorithm if we will use Map Reduce approach? Improvement in performance can be in terms of accuracy, time complexity or the ...
89 views

### Karloff's algorithm applied to sparse graphs

I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph. Karloff [1, p.6] has given a map-reduce algorithm called "...