Computing marginals using MapReduce

DOI10.1016/J.JCSS.2017.02.007zbMATH Open1390.68194arXiv1509.08855OpenAlexW2963690391MaRDI QIDQ1745720FDOQ1745720

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)

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.

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

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

zbMATH Keywords

marginalsMapReducedata-cube

Mathematics Subject Classification ID

General topics in the theory of data (68P01)

Cites Work

• Expander graphs and their applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymmetric binary covering codes.
• 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

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)