# Questions tagged [mapreduce]

The tag has no usage guidance.

18 questions
Filter by
Sorted by
Tagged with
67 views

### How to find parallel efficiency for word count algorithm?

There're not a lot of books and explanations around this example topic, so I thought asking here would be appropriate for future learners including me as well. Background: Problem: Consider a very ...
61 views

### Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
25 views

### What tools/algorithms should I use to match one record with potentially millions of other records?

I'm designing a system where we'll have potentially millions of records in a database, none with a totally unique identifier. There's about 20 fields that, when combined, could uniquely identify a ...
• 101
47 views

I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable. The proof used following idea: Reduce from the $A_{TM}$ problem ...
1 vote
23 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 ...
• 175
22 views

### Are graphic cards using the Map-Reduce model when performing typical gaming rendering

I know that the Map-Reduce model is a common model of parallel computation, perhaps some sort of standard way(?). I also know that graphic cards are specifically built for parallel computation. ...
1 vote
34 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 ...
• 171
1 vote
28 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 ...
1 vote
1k 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 ...
• 310
45 views

### Global optimization algorithm based on MapReduce

In the field of the intelligent swarm, there are many algorithms can find global optimization, such as Ant Colony Optimization (ACO), particle swarm optimization (PSO). Is there any optimization ...
40 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 ...
• 203
35 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 ...
• 321
2k 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 ...
43 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), ...
732 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 ...
• 131
249 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 ...
• 370
93 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 "...
• 370