时空高效的倒排索引压缩和求交算法研究

发布时间：2020-12-28 09:10

　　随着互联网的发展,各类信息的体量规模增长也越来越快。日益壮大的数据体积和用户数量也为各类信息系统,尤其是搜索引擎带来了严峻的考验。应对这类挑战的关键措施是提升系统在数据爬取收集、整理压缩以及查询应答的效率,而倒排索引作为信息检索底层最常用的数据结构,（负责对信息进行组织管理和查询处理）,对检索效率和系统运营成本有着至关重要的影响。因此,针对倒排索引的压缩和查询优化已经成为信息检索领域一个重要的研究课题。为此,本文针对倒排索引的压缩和查询效率问题,重点研究了设计时空高效的压缩算法和并行求交算法。本文的主要成果如下:1.为了提升压缩算法的压缩速度,本文将面向分块的压缩算法所使用的分块划分问题归纳为了在单源有向无环图上的最短路径问题,并改进优化了AFOR和VSEncoding压缩算法所使用的分块划分策略,包括为AFOR增加分块的折叠合并和使用近似算法替代VSEncoding的动态规划,提升其压解速度的同时维持了相同水平的压缩率。本文还提出了自启发式划分的Elias-Fano索引压缩算法,针对PEF索引使用多个滑动窗口反复遍历倒排链的缺点,该方法根据分块的长度和压缩代价增量的变化,仅需一个滑动... 

【文章来源】：国防科技大学湖南省 211工程院校 985工程院校

【文章页数】：131 页

【学位级别】：博士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 引言
    1.2 研究背景和意义
    1.3 研究问题与内容
    1.4 论文组织结构
第二章 倒排索引压缩与求交相关背景知识
    2.1 现代硬件体系结构
    2.2 倒排索引结构
    2.3 倒排索引的压缩算法
        2.3.1 面向整数的压缩算法
        2.3.2 面向分块的压缩算法
        2.3.3 SIMD Compression
    2.4 倒排链表的求交算法
        2.4.1 多倒排链求交算法
        2.4.2 搜索算法
    2.5 本章小结
第三章 基于最优划分的倒排索引压缩算法
    3.1 引言
    3.2 基于近似划分的分块压缩算法
        3.2.1 基于DAG的倒排索链表划分策略
        3.2.2 Extended AFOR压缩算法
        3.2.3 最优划分的VSEncoding压缩算法
    3.3 自启发式划分的Elias-Fano索引压缩算法
        3.3.1 分块Elias-Fano索引
        3.3.2 线性划分策略
    3.4 实验测试与结果分析
        3.4.1 基于近似划分的分块压缩算法测试
        3.4.2 自启发式划分的Elias-Fano索引压缩算法测试
    3.5 本章小结
第四章 混合索引在双权重标准下的时空均衡优化算法
    4.1 引言
    4.2 双权重标准压缩
        4.2.1 帕累托最优压缩
        4.2.2 基于双权重DAG的混合索引
        4.2.3 双权重标准下的混合索引问题定义
    4.3 混合式倒排索引压缩算法
        4.3.1 基于线性规划的最优压缩策略
        4.3.2 变长分块索引算法设计
    4.4 实验测试与结果分析
        4.4.1 压缩性能
        4.4.2 查询性能
    4.5 本章小结
第五章 基于并行指令集的倒排链快速求交算法
    5.1 引言
    5.2 并行的多倒排链求交算法
        5.2.1 基于SIMD的线性查找算法
        5.2.2 基于SIMD的跳跃式查找算法
    5.3 面向基于SIMD多倒排链求交的双尺度搜索算法
    5.4 实验测试和结果分析
        5.4.1 实验设置
        5.4.2 实验结果
    5.5 本章小结
第六章 总结与展望
    6.1 本文工作总结
    6.2 未来研究展望
致谢
参考文献
作者在学期间取得的学术成果



本文编号：2943491