基于Bitmap的倒排索引結(jié)構(gòu)的查詢處理研究.pdf

1、近年來，隨著互聯(lián)網(wǎng)的高速發(fā)展，搜索引擎系統(tǒng)得到了廣泛的研究與應(yīng)用。目前主流的搜索引擎系統(tǒng)均采用倒排索引結(jié)構(gòu)來組織索引，該結(jié)構(gòu)中每一個詞項對應(yīng)一條倒排索引，它將含有該詞項的所有網(wǎng)頁文檔組成一個升序列表(Inverted List)的形式。本文在倒排索引結(jié)構(gòu)的基礎(chǔ)上提出一種改進的索引結(jié)構(gòu)——基于Bitmap的倒排索引結(jié)構(gòu)，并設(shè)計了對該索引結(jié)構(gòu)的查詢處理算法。
　　本文的主要內(nèi)容包括:
　　1.設(shè)計了兩種基于Bitmap的倒排索引

2、結(jié)構(gòu)，全局Bitmap和局部Bitmap索引結(jié)構(gòu)，其中全局Bitmap的索引結(jié)構(gòu)中將較長的升序列表用一個Bitmap列表代替，而局部Bitmap的索引結(jié)構(gòu)中，升序列表的某一段或某些段被用作Bitmap表示，使得列表中部分是升序列表形式，部分為Bitmap形式。
　　2.對基于Bitmap的索引結(jié)構(gòu)，提出了相應(yīng)的查詢處理算法。對全局Bitmap索引結(jié)構(gòu)進行處理時，閾值越小，查詢中Bitmap列表平均數(shù)量越多，查詢處理的效率越高。不管

3、是對普通列表求交還是對壓縮后的列表進行求交，相比于升序列表的求交，基于Bitmap的索引列表求交的速度會大幅度提升。對全局Bitmap索引結(jié)構(gòu)中Bitmap列表求交過程使用了CPU SIMD進行優(yōu)化。
　　3.使用了圖形處理器(GPU)來并行處理基于Bitmap的索引結(jié)構(gòu)列表求交，并將若干查詢組裝為一個批次傳輸?shù)紾PU上處理，從而提高查詢處理的吞吐率。由于基于Bitmap的索引結(jié)構(gòu)的列表平均長度較短以及Bitmap列表快速查找特性