首页> 外文期刊>ACM transactions on database systems >Output-Optimal Massively Parallel Algorithms for Similarity Joins
【24h】

Output-Optimal Massively Parallel Algorithms for Similarity Joins

机译:相似联接的输出最优大规模并行算法

获取原文
获取原文并翻译 | 示例

摘要

Parallel join algorithms have received much attention in recent years due to the rapid development of massively parallel systems such as MapReduce and Spark. In the database theory community, most efforts have been focused on studying worst-case optimal algorithms. However, the worst-case optimality of these join algorithms relies on the hard instances having very large output sizes. In the case of a two-relation join, the hard instance is just a Cartesian product, with an output size that is quadratic in the input size.In practice, however, the output size is usually much smaller. One recent parallel join algorithm by Beame et al. has achieved output-optimality (i.e., its cost is optimal in terms of both the input size and the output size), but their algorithm only works for a 2-relation equi-join and has some imperfections. In this article, we first improve their algorithm to true optimality. Then we design output-optimal algorithms for a large class of similarity joins. Finally, we present a lower bound, which essentially eliminates the possibility of having output-optimal algorithms for any join on more than two relations.
机译:近年来,由于大规模并行系统(如MapReduce和Spark)的快速发展,并行连接算法已引起了广泛关注。在数据库理论界,大多数努力都集中在研究最坏情况的最佳算法上。但是,这些连接算法的最坏情况下的最优性取决于具有非常大的输出大小的硬实例。在两个关系联接的情况下,硬实例只是笛卡尔乘积,输出大小是输入大小的二次方,但实际上输出大小通常要小得多。 Beame等人最近提出了一种并行连接算法。已经实现了输出优化(即,其成本在输入大小和输出大小方面都是最佳的),但是他们的算法仅适用于2关系等联接,并且存在一些缺陷。在本文中,我们首先将其算法提高到真正的最优性。然后,我们为一大类相似联接设计输出最优算法。最后,我们提出了一个下限,从根本上消除了对两个以上关系上的任何连接使用输出最优算法的可能性。

著录项

  • 来源
    《ACM transactions on database systems》 |2019年第2期|6.1-6.36|共36页
  • 作者

    Hu Xiao; Yi Ke; Tao Yufei;

  • 作者单位

    Hong Kong Univ Sci & Technol, Dept Comp Sci & Engn, Clear Water Bay, Hong Kong, Peoples R China;

    Hong Kong Univ Sci & Technol, Dept Comp Sci & Engn, Clear Water Bay, Hong Kong, Peoples R China;

    Chinese Univ Hong Kong, Dept Comp Sci & Engn, Shatin, Hong Kong, Peoples R China;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Parallel computation; similarity joins; output-sensitive algorithms;

    机译:并行计算;相似联接;输出敏感算法;

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号