隨著互聯(lián)網(wǎng)的發(fā)展,各類信息的體量規(guī)模增長(zhǎng)也越來(lái)越快。日益壯大的數(shù)據(jù)體積和用戶數(shù)量也為各類信息系統(tǒng),尤其是搜索引擎帶來(lái)了嚴(yán)峻的考驗(yàn)。應(yīng)對(duì)這類挑戰(zhàn)的關(guān)鍵措施是提升系統(tǒng)在數(shù)據(jù)爬取收集、整理壓縮以及查詢應(yīng)答的效率,而倒排索引作為信息檢索底層最常用的數(shù)據(jù)結(jié)構(gòu),（負(fù)責(zé)對(duì)信息進(jìn)行組織管理和查詢處理）,對(duì)檢索效率和系統(tǒng)運(yùn)營(yíng)成本有著至關(guān)重要的影響。因此,針對(duì)倒排索引的壓縮和查詢優(yōu)化已經(jīng)成為信息檢索領(lǐng)域一個(gè)重要的研究課題。為此,本文針對(duì)倒排索引的壓縮和查詢效率問(wèn)題,重點(diǎn)研究了設(shè)計(jì)時(shí)空高效的壓縮算法和并行求交算法。本文的主要成果如下:1.為了提升壓縮算法的壓縮速度,本文將面向分塊的壓縮算法所使用的分塊劃分問(wèn)題歸納為了在單源有向無(wú)環(huán)圖上的最短路徑問(wèn)題,并改進(jìn)優(yōu)化了AFOR和VSEncoding壓縮算法所使用的分塊劃分策略,包括為AFOR增加分塊的折疊合并和使用近似算法替代VSEncoding的動(dòng)態(tài)規(guī)劃,提升其壓解速度的同時(shí)維持了相同水平的壓縮率。本文還提出了自啟發(fā)式劃分的Elias-Fano索引壓縮算法,針對(duì)PEF索引使用多個(gè)滑動(dòng)窗口反復(fù)遍歷倒排鏈的缺點(diǎn),該方法根據(jù)分塊的長(zhǎng)度和壓縮代價(jià)增量的變化,僅需一個(gè)滑動(dòng)... 

【文章來(lái)源】：國(guó)防科技大學(xué)湖南省 211工程院校 985工程院校

【文章頁(yè)數(shù)】：131 頁(yè)

【學(xué)位級(jí)別】：博士

【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 引言
    1.2 研究背景和意義
    1.3 研究問(wèn)題與內(nèi)容
    1.4 論文組織結(jié)構(gòu)
第二章 倒排索引壓縮與求交相關(guān)背景知識(shí)
    2.1 現(xiàn)代硬件體系結(jié)構(gòu)
    2.2 倒排索引結(jié)構(gòu)
    2.3 倒排索引的壓縮算法
        2.3.1 面向整數(shù)的壓縮算法
        2.3.2 面向分塊的壓縮算法
        2.3.3 SIMD Compression
    2.4 倒排鏈表的求交算法
        2.4.1 多倒排鏈求交算法
        2.4.2 搜索算法
    2.5 本章小結(jié)
第三章 基于最優(yōu)劃分的倒排索引壓縮算法
    3.1 引言
    3.2 基于近似劃分的分塊壓縮算法
        3.2.1 基于DAG的倒排索鏈表劃分策略
        3.2.2 Extended AFOR壓縮算法
        3.2.3 最優(yōu)劃分的VSEncoding壓縮算法
    3.3 自啟發(fā)式劃分的Elias-Fano索引壓縮算法
        3.3.1 分塊Elias-Fano索引
        3.3.2 線性劃分策略
    3.4 實(shí)驗(yàn)測(cè)試與結(jié)果分析
        3.4.1 基于近似劃分的分塊壓縮算法測(cè)試
        3.4.2 自啟發(fā)式劃分的Elias-Fano索引壓縮算法測(cè)試
    3.5 本章小結(jié)
第四章 混合索引在雙權(quán)重標(biāo)準(zhǔn)下的時(shí)空均衡優(yōu)化算法
    4.1 引言
    4.2 雙權(quán)重標(biāo)準(zhǔn)壓縮
        4.2.1 帕累托最優(yōu)壓縮
        4.2.2 基于雙權(quán)重DAG的混合索引
        4.2.3 雙權(quán)重標(biāo)準(zhǔn)下的混合索引問(wèn)題定義
    4.3 混合式倒排索引壓縮算法
        4.3.1 基于線性規(guī)劃的最優(yōu)壓縮策略
        4.3.2 變長(zhǎng)分塊索引算法設(shè)計(jì)
    4.4 實(shí)驗(yàn)測(cè)試與結(jié)果分析
        4.4.1 壓縮性能
        4.4.2 查詢性能
    4.5 本章小結(jié)
第五章 基于并行指令集的倒排鏈快速求交算法
    5.1 引言
    5.2 并行的多倒排鏈求交算法
        5.2.1 基于SIMD的線性查找算法
        5.2.2 基于SIMD的跳躍式查找算法
    5.3 面向基于SIMD多倒排鏈求交的雙尺度搜索算法
    5.4 實(shí)驗(yàn)測(cè)試和結(jié)果分析
        5.4.1 實(shí)驗(yàn)設(shè)置
        5.4.2 實(shí)驗(yàn)結(jié)果
    5.5 本章小結(jié)
第六章 總結(jié)與展望
    6.1 本文工作總結(jié)
    6.2 未來(lái)研究展望
致謝
參考文獻(xiàn)
作者在學(xué)期間取得的學(xué)術(shù)成果



本文編號(hào)：2943491