Computing marginals using MapReduce

DOI10.1016/J.JCSS.2017.02.007MaRDI QIDQ1745720zbMATHOpenAlexFDO

Authors Foto N. Afrati, Shantanu Sharma, Jonathan Ullman, Jeffrey D. Ullman

Publication date 18 April 2018

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.08855

zbMATH Keywords

marginalsMapReducedata-cube

Mathematics Subject Classification ID

General topics in the theory of data (68P01)

Abstract: We consider the problem of computing the data-cube marginals of a fixed order $k$ (i.e., all marginals that aggregate over $k$ dimensions), using a single round of MapReduce. The focus is on the relationship between the reducer size (number of inputs allowed at a single reducer) and the replication rate (number of reducers to which an input is sent). We show that the replication rate is minimized when the reducers receive all the inputs necessary to compute one marginal of higher order. That observation lets us view the problem as one of covering sets of $k$ dimensions with sets of a larger size $m$, a problem that has been studied under the name "covering numbers." We offer a number of constructions that, for different values of $k$ and $m$ meet or come close to yielding the minimum possible replication rate for a given reducer size.

Recommendations

• scientific article; zbMATH DE number 6297759
• On the computational complexity of MapReduce
• Sorting, searching, and simulation in the MapReduce framework
• On distributing symmetric streaming computations
• Sharing across multiple MapReduce jobs

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 1016456 (Why is no real title available?)
• Asymmetric binary covering codes.
• Expander graphs and their applications
• On asymmetric coverings and covering numbers

Cited in

(2)

• Security and privacy aspects in MapReduce on clouds: a survey
• Formalizing compute-aggregate problems in cloud computing

Describes a project that uses

Uses Software

• MapReduce

This page was built for publication: Computing marginals using MapReduce

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1745720)