Difference between revisions of "Open Problems:17"
m (1 revision) |
|||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |title=The Massive, Unordered, Distributed-Data Model | |
| − | | | + | |source=kanpur06 |
| − | | | + | |who=S. Muthkrishnan |
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
The Massive, Unordered, Distributed-data (MUD) model was recently introduced by Feldman et al. {{cite|FeldmanMSSS-06}} as an abstraction of part of the infrastructure used at Google. It is related to the MapReduce framework presented in {{cite|DeanG-04}}. In the multi-round, multi-key MUD model, $n$ data records are distributed arbitrarily between $M$ machines. Each machine maps each record to (key, value) pairs. All pairs corresponding to the same key are then “reduced” to a single record. This reduction is performed by an $O(\operatorname{polylog} n)$-space streaming computation. The process repeats for a total of $l$ rounds. | The Massive, Unordered, Distributed-data (MUD) model was recently introduced by Feldman et al. {{cite|FeldmanMSSS-06}} as an abstraction of part of the infrastructure used at Google. It is related to the MapReduce framework presented in {{cite|DeanG-04}}. In the multi-round, multi-key MUD model, $n$ data records are distributed arbitrarily between $M$ machines. Each machine maps each record to (key, value) pairs. All pairs corresponding to the same key are then “reduced” to a single record. This reduction is performed by an $O(\operatorname{polylog} n)$-space streaming computation. The process repeats for a total of $l$ rounds. | ||
The model is very powerful and it was proven that any EREW-PRAM algorithm can be simulated in the multi-round, multi-key MUD model if the number of keys and rounds is sufficiently large {{cite|FeldmanMSSS-06}}. In practice we are primarily interested in computing with a small number of keys and rounds. What can be computed given $k$ keys and $l$ rounds? | The model is very powerful and it was proven that any EREW-PRAM algorithm can be simulated in the multi-round, multi-key MUD model if the number of keys and rounds is sufficiently large {{cite|FeldmanMSSS-06}}. In practice we are primarily interested in computing with a small number of keys and rounds. What can be computed given $k$ keys and $l$ rounds? | ||
Revision as of 05:11, 16 November 2012
| Suggested by | S. Muthkrishnan |
|---|---|
| Source | Kanpur 2006 |
| Short link | https://sublinear.info/17 |
The Massive, Unordered, Distributed-data (MUD) model was recently introduced by Feldman et al. [FeldmanMSSS-06] as an abstraction of part of the infrastructure used at Google. It is related to the MapReduce framework presented in [DeanG-04]. In the multi-round, multi-key MUD model, $n$ data records are distributed arbitrarily between $M$ machines. Each machine maps each record to (key, value) pairs. All pairs corresponding to the same key are then “reduced” to a single record. This reduction is performed by an $O(\operatorname{polylog} n)$-space streaming computation. The process repeats for a total of $l$ rounds.
The model is very powerful and it was proven that any EREW-PRAM algorithm can be simulated in the multi-round, multi-key MUD model if the number of keys and rounds is sufficiently large [FeldmanMSSS-06]. In practice we are primarily interested in computing with a small number of keys and rounds. What can be computed given $k$ keys and $l$ rounds?
