Jun, 2012

Map-Reduce 计算成本的上下界

PDF
TL;DR本文探讨了在 map-reduce 计算中并行性和通信成本之间的权衡问题，并引入了单轮 map-reduce 计算问题的模型，以发现以分配给一个缩小器的最大输入数为函数的通信成本下界。作者对三个问题进行了分析：找到两个距离为 $d$ 的字符串、在较大的图形中查找三角形和其他模式以及矩阵乘法。
map-reduce computationcommunication costparallelismlower boundsmatrix multiplication
发现论文，激发创造
  • 分布式计算中计算和通信之间的根本权衡

    本论文研究的问题是如何在分布式计算中，通过优化计算负载来降低通信负载，通过研究分布式计算中计算和通信之间的权衡关系，提出一种编码方案，命名为 “编码分布式计算”（CDC），该方案通过增加 Map 函数的计算负载来减少通信负载，实现了计算和通信的最优权衡。同时，将 CDC 的编码技术应用于 Hadoop TeraSort 基准测试中，开发出一种新的编码 TeraSort 算法，对实验中最常用的设置进行了验证，整个作业执行速度提高了 1.97 至 3.39 倍。

    Apr, 2016

  • 在 MapReduce 框架中的排序、搜索和模拟

    本文探讨了 MapReduce 框架的算法方面，并通过设计和分析处理基本的排序、搜索和仿真问题的 MapReduce 算法展示了我们的方法的有效性。

    Jan, 2011

  • 并行查询处理通信步骤

    通过在具有大量服务器的大型输入数据库上计算关系查询来解决分布式计算中通信协议的瓶颈，并且在单个和多个通信步骤中建立了下限，同时其下限证明了任何算法需要 epsilon 大于等于 1-1/tau*，同时结果也蕴含了不能在 O（1）个通信步骤内计算传递闭包。

    Jun, 2013

  • 通过分布式数据处理不等式推导统计估计问题的通信下界

    本文研究了高维分布统计估计问题的统计误差和通信成本之间的权衡，并提供了分布式稀疏高斯均值估计问题的紧密的权衡分析结果，这直接导致了分布式稀疏线性回归问题的下界，并给出了在稠密情况下均值估计的第一个最优同时协议。

    Jun, 2015

  • 多方通信复杂度中，手中数字最小下界简化

    本文利用对称化技术，证明了在黑板模型和消息传递模型中随机多方通信复杂性的下限，并应用该技术证明了关于多方通信的多个直接和结果。

    Jul, 2011

  • 分布式统计估计和维度的通信成本

    探索分布式学习中维度和沟通成本之间的关系，研究估计未知高维高斯分布均值的问题。同时，提出了一个基于阈值的协议，可在保证相同平方损失的前提下节省通信开销。

    May, 2014

  • 并行查询处理中的偏斜

    研究使用 p 个服务器在大型数据库上并行计算简单查询 q 的通信复杂性，特别关注数据倾斜的情况下的情况，建立了查询的分数边覆盖与通信量之间的紧密联系，并提供了查询分数边覆盖的匹配上界和下界，所有下界都以比特通信量的形式表达。

    Jan, 2014

  • 分布式图分析的编码计算

    本文提出了一种基于编码计算的分布式图处理框架，通过结构性冗余注入来在消息交换时实现编码的多播机会，从而大规模减少了通信负载，理论分析证明该方案在两种流行的随机图模型（Erdos-Renyi 模型和幂律模型）中实现了计算负载和平均通信负载之间的（近似）反比例线性折衷，实验结果表明该方案在 PageRank 计算中具有显着提高。

    Jan, 2018

  • Gap-Hamming 距离的通信复杂度的最优下界

    本文通过引入高斯空间相关性的几何性质以及概率投影的方法证明了久负盛名的 Gap-Hamming-Distance 问题的随机通信复杂度的最优下界，并由此得出了在数据流模型中多遍通信所需的空间的最优下界。

    Sep, 2010

  • MapReduce 模型下的子模块最优化

    本文介绍了两种在 MapReduce 模型中的基数约束子模规划的简单算法，第一种算法在 2 个 MapReduce 轮中可以实现 1/2 的近似度，第二种算法可以在 1+o (1)/ε 个 MapReduce 轮中实现 1−1/e−ε 的近似度。

    Oct, 2018