随着互联网的发展,各类信息的体量规模增长也越来越快。日益壮大的数据体积和用户数量也为各类信息系统,尤其是搜索引擎带来了严峻的考验。应对这类挑战的关键措施是提升系统在数据爬取收集、整理压缩以及查询应答的效率,而倒排索引作为信息检索底层最常用的数据结构,(负责对信息进行组织管理和查询处理),对检索效率和系统运营成本有着至关重要的影响。因此,针对倒排索引的压缩和查询优化已经成为信息检索领域一个重要的研究课题。为此,本文针对倒排索引的压缩和查询效率问题,重点研究了设计时空高效的压缩算法和并行求交算法。本文的主要成果如下:1.为了提升压缩算法的压缩速度,本文将面向分块的压缩算法所使用的分块划分问题归纳为了在单源有向无环图上的最短路径问题,并改进优化了AFOR和VSEncoding压缩算法所使用的分块划分策略,包括为AFOR增加分块的折叠合并和使用近似算法替代VSEncoding的动态规划,提升其压解速度的同时维持了相同水平的压缩率。本文还提出了自启发式划分的Elias-Fano索引压缩算法,针对PEF索引使用多个滑动窗口反复遍历倒排链的缺点,该方法根据分块的长度和压缩代价增量的变化,仅需一个滑动窗口探测异常值并完成划分,在损失了轻微的压缩率和解压速度的代价下,极大地提高了压缩速度。实验结果表明,本文提出的压缩算法相比优化前的算法在压缩/解压缩速度-压缩率对应的时空曲线上能达到更优的位置。2.本文提出了双权重标准压缩算法的概念,针对近年来融合多种压缩算法的混合式索引,本文将最优地分配压缩算法到各个分块的问题,归纳为了资源受限的双权重有向无环图的最短路径问题,对应的权重为压缩大小和解压缩时间,并借助于拉格朗日松弛算法寻找压缩算法的最优分配方案。相比于现行的方案,本文的算法仅需要O(n log n)的时间和O(n)空间进行求解,同时结果与最优解之间仅保留加性误差。除此以外,我们还探索了使用动态规划对倒排链进行变长分块,将完成分配的分块按照相似度准则进行合并,进一步提升了查询效率。实验结果表明,本文提出的压缩算法分配算法能够动态地调整倒排索引的时空特性,使之适应实际应用中索引设计者对空间/时间的任一要求。3.针对倒排链的求交算法,本文首先回顾了传统的多倒排链求交算法以及近年来提出的基于SIMD的并行求交算法,归纳分析了影响求交算法的两个因素,即排除项选择方式和倒排链的搜索算法。由于当前基于SIMD的并行求交算法都是针对倒排链两两相交设计的,并未利用到传统的多倒排链求交算法。为此,我们提出了基于SIMD的多倒排链并行求交算法,由于它采用线性搜索,对于长倒排链的效果并不是很好。为了继续提高算法效率,我们首先研究了使用AVX2提供的收集指令同时收集倒排链中离散位置的元素与排除项同时进行比较,用于加速跳查过程;随后提出了基于双尺度自适应变换搜索窗口的搜索算法,相比于先行算法简单地使用经验参数,我们的搜索算法更针对参与倒排链的长度自动匹配最优的搜索参数,极大地提高了倒排链求交的性能。