Editing Open Problems:17
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 1: | Line 1: | ||
| β | {{ | + | {{DISPLAYTITLE:Problem 17: The Massive, Unordered, Distributed-Data Model}} |
| β | | | + | {{Infobox |
| β | | | + | |label1 = Proposed by |
| + | |data1 = S. Muthkrishnan | ||
| + | |label2 = Source | ||
| + | |data2 = [[Workshops:Kanpur_2006|Kanpur 2006]] | ||
| + | |label3 = Short link | ||
| + | |data3 = http://sublinear.info/17 | ||
}} | }} | ||
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? | ||
