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

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

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

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