倒排索引压缩算法研究综述

• 作者: 姜琨 宋省身 朱磊 杨岳湘
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 搜索引擎 倒排索引压缩算法 字对齐压缩 SIMD指令集 自索引结构
• 年，卷（期）: 2020,（4）
• 所属期刊栏目: 人工智能与算法研究
• 页码范围: 715-723
• 页数: 9页
• 分类号: TP301
• 字数: 10656字
• 语种: 中文

摘要

不断增长的互联网网页信息和成千上万的用户查询请求给搜索引擎的索引更新和查询访问带来了前所未有的实时性挑战.高效的索引压缩算法能够降低索引数据的存储和传输开销,加快处理器对索引数据的处理速度,因此能直接影响搜索引擎系统的查询性能.首先,概述了倒排索引中倒排链表所包含的d-gap和freq整数序列的存储结构,并依据压缩码字的对齐方式对倒排索引压缩算法进行分类;其次,详细阐述了当前流行的字对齐压缩算法,并总结了Simple、Frame of Reference( FOR)、Optimized Chunk Splitting(OCS)等几类典型的倒排索引压缩算法;之后,综述了倒排索引压缩算法的SIMD并行化研究,即采用SIMD指令集中Shuffle数据置换和垂直布局存储来加速算法对d-gap整数序列的并行处理性能.然后,针对压缩倒排索引的随机访问问题,综述了通常采用的自索引技术和原始序列压缩算法两种策略.最后,对倒排索引压缩算法在搜索引擎系统中的应用进行了分析和总结并对未来倒排索引压缩算法可能的研究方向进行了探讨和展望.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨岳湘	国防科技大学计算机学院	41	587	14.0	23.0
2	朱磊	西安理工大学计算机科学与工程学院	16	93	5.0	9.0
3	姜琨	西安理工大学计算机科学与工程学院	2	0	0.0	0.0
7	宋省身	国防科技大学计算机学院	1	0	0.0	0.0