并行查询处理通信步骤

Jun, 2013

Communication Steps for Parallel Query Processing

Paul Beame, Paraschos Koutris, Dan Suciu

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

Abstract

We consider the problem of computing a relational query $q$ on a large input database of size $n$, using a large number $p$ of servers. The computation is performed in rounds, and each server can receive only $O(n/p^{1-\varepsilon})$ bits of data, where $\varepsilon \in [0,1]$ is a par

relational query distributed computing global communication steps lower bounds transitive closure

发现论文，激发创造

并行查询处理中的偏斜

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

Jan, 2014

Map-Reduce 计算成本的上下界

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

Jun, 2012

随机组合核心集用于匹配和顶点覆盖

本研究证明，匹配问题和点覆盖问题在同时通信模型中的不可承受性根源于基础图形跨机器的对抗性分区，进而展示这两个问题存在随机组分的可组合核的对数 O (n)。

May, 2017

通信的任意分区模型中的 $l_p$ 回归

本研究探讨了分布式 l_p 回归问题的随机通信复杂度，得到了比以前更好的上下界，并在最小二乘回归和其他一些情况中给出了优化算法。

Jul, 2023

分布式分类与优化的高效协议

本文提出了基于多项式权重更新的两方协议，并且展示了一般的算法设计方法来解决在分布式数据中的高效学习问题。

Apr, 2012

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

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

Jun, 2015

分布式仿真和分布式推断

研究了一个关于 “simulate-and-infer” 的通信受限问题，在只要求每个参与者发送少于 log k 比特给中央仲裁者的情况下，寻找利用最少的参与者，对未知概率分布进行推断的最优策略，表明了 simulate-and-infer 策略是最优采样复杂度的，并提出了一个有效的公共硬币通信协议，可以突破身份测试的通信复杂度下界。

Apr, 2018

通信最优的分布式聚类

本文研究了分布式模式下的图形和几何聚类问题，并给出了两个模型中几乎是最优的协议，突出了广播通道在聚类问题中的惊人能力，我们的算法已在实际数据集上得到了验证。

Feb, 2017

分布式功能监测的严格界限

通过新的直接求和定理，我们解决了数据流模型中估计频率矩阵和其它问题时的基础问题，并通过改进算法显著提高了界限。

Dec, 2011

分布式学习，通信复杂度和隐私

讨论分布式数据的 PAC 学习问题，分析了涉及的基本通信复杂性问题，包括教学维度和错误绑定。针对特定概念类别，如合取、奇偶函数和决策列表等，给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信，以及如何在不确定环境下实现低通信回归。同时，还考虑了隐私性，包括差分隐私和分布式隐私。

Apr, 2012