Open Problems:17 - Revision history

Krzysztof Onak: updating header

2013-03-07T01:41:54Z

updating header

Krzysztof Onak at 05:11, 16 November 2012

2012-11-16T05:11:36Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 17: The Massive, Unordered, Distributed-Data Model}} {{Infobox |label1 = Proposed by |data1 = S. Muthkrishnan |label2 = Source |data2 = [[Workshops:Kanp..."

2012-10-16T14:58:16Z

Created page with "{{DISPLAYTITLE:Problem 17: The Massive, Unordered, Distributed-Data Model}} {{Infobox |label1 = Proposed by |data1 = S. Muthkrishnan |label2 = Source |data2 = [[Workshops:Kanp..."

New page

{{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 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?

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=S. Muthkrishnan

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 17: The Massive, Unordered, Distributed-Data Model}}
+{{Header
-{{Infobox
+|title=The Massive, Unordered, Distributed-Data Model
-|label1 = Proposed by
+|source=kanpur06
-|data1 = S. Muthkrishnan
+|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 &ldquo;reduced&rdquo;  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?

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)