基于Bloom Filter的GPU求交算法

摘要：

　　索引表求交是搜索引擎中一个重要的操作，先前的研完工作主要集中在单核心或者多核心的CPU上。这篇文章提出了一种新颖的利用Bloom Filter的近似索引表求交算法。尽管Bloom Filter会返回误称结果，发现错误的结果数相对求交结果非常少，并不会影响结果质量。本文的方法是基于一种批次的GPU处理框架，在这种框架中，查询在CPU端组织成为一个批次，并在GPU端进行处理，这个框架有效地利用了GPU的大规模并行运算能力，可以有效地提升系统的吞吐率；实验显示，本文提出的Bloom Filter求交算法相比基准的二分搜索方法的性能有了显著的提升，且结果的冗余率非常低。

关键词： 图像处理器 索引表 求交算法 图形显卡

作者: Fan Zhang 张帆 Di Wu 吴迪 Kebin Wang 王克宾 Gang Wang 王刚 Xiaoguang Liu 刘晓光

作者单位: College of Information Technical Science,Nankai University,Tianjin 300071,China 南开大学,信息技术科学学院,天津市,300071

会议类型: 国内会议

会议名称: 2012全国高性能计算学术年会

会议地点: 张家界

会议语种:中文

页码: 1-4

在线出版日期: 2012-10-29（万方平台首次上网日期，不代表论文的发表时间）