[LiOXCH09]Yu Li, Sai Tung On, Jianliang Xu, Byron Choi, Haibo Hu: DigestJoin: Exploiting Fast Random Reads for Flash-Based Joins. Mobile Data Management 2009:152-161
温馨提示：“论文导读”旨在推荐他人发表的本领域相关论文。本论文摘要由厦门大学计算机系林子雨老师(http://www.cs.xmu.edu.cn/linziyu)翻译，如果您对该论文细节感兴趣，可以阅读英文原文（全文PDF版权归出版商所有，因此需要到出版商网站下载该论文PDF）。
【摘要】本文提出了DigestJoin，这个算法可以充分利用闪存快速的随机读能力。DigestJoin包括两个阶段，在第一个阶段，DigestJoin把元组ID和那些与连接操作相关的属性投影出来，投影得到的表称为摘要表（digest table）。这里的主要意图是，闪存通常安装在移动设备内部，具有有限的内存。获得摘要表后，可以减少后续的IO开销。然后，就可以在更小的摘要表上运行传统的连接算法，来生成摘要连接结果. 摘要连接结果只包含了来自两个连接关系的元组ID和连接属性，可以最小化中间连接结果。在第二个阶段，基于摘要连接结果，算法会从原始表中加载完整的元组来生成最终的结果。
【林子雨推荐理由】这篇文章用巧妙的思路，把DigestJoin的第二个阶段的页抓取问题转换成一个联接图的顶点遍历问题，并用启发式算法解决该问题。