• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >The Communication Complexity of Distributed epsilon-Approximations
【24h】

The Communication Complexity of Distributed epsilon-Approximations

机译：分布epsilon近似的通信复杂度

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Data summarization is an effective approach to dealing with the "big data" problem. While data summarization problems traditionally have been studied is the streaming model, the focus is starting to shift to distributed models, as distributed/parallel computation seems to be the only viable way to handle today's massive data sets. In this paper, we study ε-approximations, a classical data summary that, intuitively speaking, preserves approximately the density of the underlying data set over a certain range space. We consider the problem of computing ε-approximations for a data set which is held jointly by k players, and give general communication upper and lower bounds that hold for any range space whose discrepancy is known.
机译：数据汇总是处理“大数据”问题的有效方法。尽管传统上研究的数据汇总问题是流模型，但焦点已开始转移到分布式模型，因为分布式/并行计算似乎是处理当今海量数据集的唯一可行方法。在本文中，我们研究了-近似值，这是一种经典的数据摘要，从直觉上讲，它可以在一定范围内大致保留基础数据集的密度。我们考虑计算由k个播放器共同持有的数据集的近似值的问题，并给出适用于已知差异的任何范围空间的一般通信上下限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号