Efficient Decoding of Posting Lists with SIMD Instructions
Modern search engines process thousands of queries per second, searching through billions of web documents.With data sizes and query loads growing at an exponential rate, significant performance challenges arise.To achieve fast query processing, search engines generally store their posting lists in main memory in a compressed format.The integer decoding of posting lists must be performed on the fly for every uncached query and consumes considerable CPU time.Therefore, efficient integer decoding algorithms are essential for search engine performance, and have been studied extensively in the literature.Recent research work discovered that byte-aligned and frame-based codecs are particularly amenable to parallel decoding with powerful SSE instructions in modern processors.In this paper, we apply these instructions to bit-and word-aligned codecs and, in particular, we exploit the wider bit width and more powerful instructions of Intel AVX2 to further improve the decoding speed.Our experiments on the TREC GOV2 collection demonstrate significant performance gains from applying the new Intel AVX2 instructions to decoding posting lists.
Inverted Index Integer Decoding SIMD
Naiyong Ao Zhaohua Zhang Benjun Ye Dongdong Wang Xiaoguang Liu Gang Wang
Nankai-Baidu Joint Lab,College of Computer and Control Engineering,Nankai University,Tianjin 300071,China
国内会议
金华
英文
1-12
2015-10-30（万方平台首次上网日期，不代表论文的发表时间）