GPU accelerated information retrieval using Bloom filters
GPU accelerated information retrieval using Bloom filters
复制标题
DOI：
10.1109/icstcc.2015.7321404
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
Alexandru Iacob;L. Itu;L. Sasu;F. Moldoveanu;C. Suciu
中科院分区：
文献类型：
--
作者：
Alexandru Iacob;L. Itu;L. Sasu;F. Moldoveanu;C. Suciu
信息检索是一种用于搜索引擎，广告位置和认知数据库的技术。随着数据量增加和严格的响应时间要求，改善文档检索的基本实施变得至关重要。为此，我们考虑了一个Bloom滤波器，这是一种简单的随机数据结构，该结构回答成员资格查询，没有假阴性和可自定义的假阳性概率。主要是，我们通过使用基于图形处理单元（GPU）的实现来关注算法的加速。从定期的CPU实现Bloom Filter算法，我们对两个基本的Bloom滤波器操作采用不同的优化技术：映射和查询。这两个操作都可以实现重要的速度：映射超过300倍，查询超过20倍。此外，我们表明，在映射操作过程中使用的哈希功能数量，文件数以及查询单词的数量对执行时间和加速有重大影响。
Information retrieval is a technique used in search engines, advertisement placement and cognitive databases. With increasing amounts of data and stringent response time requirements, improving the underlying implementation of document retrieval becomes critical. To this end, we consider a Bloom filter, a simple randomized data structure that answers membership queries with no false negative and customizable false positive probability. Mainly, we focus on the speed-up of the algorithm by using a Graphics Processing Units (GPU) based implementation. Starting from a regular CPU implementation of the Bloom filter algorithm, we employ different optimization techniques on the two basic Bloom filter operations: mapping and querying. An important speed-up is achieved for both operations: over 300x for mapping, and over 20x for querying. Furthermore, we show that the number of hash functions used during the mapping operation, the number of files, and the number of query words have a significant effect on the execution time and the speed-up.