Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units
Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units
复制标题
DOI：
10.14778/2002974.2002975
复制
发表时间：
2011-05
期刊：
影响因子：
--
通讯作者：
Naiyong Ao;Fan Zhang;Di Wu;Douglas S. Stones;G. Wang;X. Liu;Jing Liu;Sheng Lin
中科院分区：
文献类型：
--
作者：
Naiyong Ao;Fan Zhang;Di Wu;Douglas S. Stones;G. Wang;X. Liu;Jing Liu;Sheng Lin
主要的网络搜索引擎每秒回答数千个查询，请求有关数十亿个网页的信息。数据大小和查询负载正以指数级速度增长。为了管理繁重的工作负载，我们考虑利用图形处理单元（GPU）的技术。我们研究新的方法来改善搜索引擎的两个重要操作-列表交集和索引压缩。对于列表的交集，我们开发了有效实现并行计算的二分查找算法的技术。我们检查了一些有代表性的真实世界的数据集，发现一个足够长的倒排列表具有整体线性增长率。基于这一观察，我们提出了线性回归和哈希分割技术收缩的搜索范围。对于索引压缩，传统的基于d-gap的压缩模式不适合并行计算，所以我们提出了一个线性回归压缩模式，它具有固有的并行结构。我们进一步讨论了如何在GPU上有效地相交压缩列表。我们的实验结果表明，显着的改进，在几个数据集上的查询处理吞吐量。
Major web search engines answer thousands of queries per second requesting information about billions of web pages. The data sizes and query loads are growing at an exponential rate. To manage the heavy workload, we consider techniques for utilizing a Graphics Processing Unit (GPU). We investigate new approaches to improve two important operations of search engines -- lists intersection and index compression. For lists intersection, we develop techniques for efficient implementation of the binary search algorithm for parallel computation. We inspect some representative real-world datasets and find that a sufficiently long inverted list has an overall linear rate of increase. Based on this observation, we propose Linear Regression and Hash Segmentation techniques for contracting the search range. For index compression, the traditional d-gap based compression schemata are not well-suited for parallel computation, so we propose a Linear Regression Compression schema which has an inherent parallel structure. We further discuss how to efficiently intersect the compressed lists on a GPU. Our experimental results show significant improvements in the query processing throughput on several datasets.