• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于指令级并行的倒排索引压缩算法

闫宏飞, 旭东, 单栋栋, 毛先领, 赵鑫

闫宏飞, 旭东, 单栋栋, 毛先领, 赵鑫. 基于指令级并行的倒排索引压缩算法[J]. 计算机研究与发展, 2015, 52(5): 995-1004. DOI: 10.7544/issn1000-1239.2015.20131548
引用本文: 闫宏飞, 旭东, 单栋栋, 毛先领, 赵鑫. 基于指令级并行的倒排索引压缩算法[J]. 计算机研究与发展, 2015, 52(5): 995-1004. DOI: 10.7544/issn1000-1239.2015.20131548
shu
Yan Hongfei, Zhang Xudong, Shan Dongdong, Mao Xianling, Zhao Xin. SIMD-Based Inverted Index Compression Algorithms[J]. Journal of Computer Research and Development, 2015, 52(5): 995-1004. DOI: 10.7544/issn1000-1239.2015.20131548
Citation: Yan Hongfei, Zhang Xudong, Shan Dongdong, Mao Xianling, Zhao Xin. SIMD-Based Inverted Index Compression Algorithms[J]. Journal of Computer Research and Development, 2015, 52(5): 995-1004. DOI: 10.7544/issn1000-1239.2015.20131548
shu
闫宏飞, 旭东, 单栋栋, 毛先领, 赵鑫. 基于指令级并行的倒排索引压缩算法[J]. 计算机研究与发展, 2015, 52(5): 995-1004. CSTR: 32373.14.issn1000-1239.2015.20131548
引用本文: 闫宏飞, 旭东, 单栋栋, 毛先领, 赵鑫. 基于指令级并行的倒排索引压缩算法[J]. 计算机研究与发展, 2015, 52(5): 995-1004. CSTR: 32373.14.issn1000-1239.2015.20131548
shu
Yan Hongfei, Zhang Xudong, Shan Dongdong, Mao Xianling, Zhao Xin. SIMD-Based Inverted Index Compression Algorithms[J]. Journal of Computer Research and Development, 2015, 52(5): 995-1004. CSTR: 32373.14.issn1000-1239.2015.20131548
Citation: Yan Hongfei, Zhang Xudong, Shan Dongdong, Mao Xianling, Zhao Xin. SIMD-Based Inverted Index Compression Algorithms[J]. Journal of Computer Research and Development, 2015, 52(5): 995-1004. CSTR: 32373.14.issn1000-1239.2015.20131548
shu

基于指令级并行的倒排索引压缩算法

  • 1(北京大学网络与信息系统研究所 北京 100871)

  • 2(淘宝(中国)软件有限公司 杭州 312000)

  • 3(北京理工大学 北京 100081) (yhf@net.pku.edu.cn)

基金项目: 国家“九七三”重点基础研究发展计划基金项目(2014CB340400)；国家自然科学基金项目(61272340)；江苏未来网络创新研究院项目-云服务数字资源搜索(BY2013095-4-02)
详细信息

  • 中图分类号: TP301.6

SIMD-Based Inverted Index Compression Algorithms

  • 1(Institute of Network Computing and Information Systems, Peking University, Beijing 100871)

  • 2(Taobao (China) Software Co., Ltd, Hangzhou 312000)

  • 3(Beijing Institute of Technology, Beijing 100081)

摘要

    摘要
  • 摘要: 文本信息数量的快速增长给传统的信息检索技术带来了新的挑战.搜索引擎通常使用倒排索引来高效地处理查询.为了减少存储开销和加快访问速度，倒排索引通常被压缩存储.因此，如何选择一个高性能的压缩算法对高效查询处理是非常有必要的.在已有倒排链压缩算法PackedBinary和PForDelta的基础上，利用CPU的超标量特性和SIMD向量指令集，将其压缩和解压缩中的关键步骤并行化，提出了2种指令级并行压缩算法SIMD-PB和SIMD-PFD.基于GOV2和ClueWeb09B两个公开数据集的实验表明，SIMD-PB和SIMD-PFD算法在压缩率不变的情况下，压缩和解压缩速度比现有的压缩算法均有非常明显的提升.其中解压缩速度比起目前最好的倒排链压缩算法，最高能提升17%.此外，实验表明算法在较长的倒排链、较大的压缩块单位上有更好的解压缩性能.
    Abstract: The rapid growth of text information has brought about new challenges to traditional information retrieval. In large search engines, indexing is required to help users acquire important data they need, and techniques of inverted index have great influence on the efficiency of query processing in such systems. The data in inverted index is stored in the form of arrays of integers, and techniques of compression are required to reduce the cost of storing such data in disks and memory, as well as to boost the hit rate of CPU cache and speed up transferring data. Therefore, it is necessary to choose a highly efficient compression algorithm to process query effectively. In this paper, we propose two instruction-level-parallelized algorithms, i.e. SIMD-PB and SIMD-PFD, which improve two competitive compression algorithms respectively, i.e. PackedBinary and PForDelta, and exploit SIMD instructions to accelerate the Pack and Unpack procedure in the algorithms. Experiments based on public datasets of GOV2 and ClueWeb09B show that our novel algorithms have good performance on encoding and decoding speed without impairing the compression ratio, and outperform the former fastest inverted list compression algorithms by at most 17%, with respect to decompression speed. Furthermore, experiments indicate that our novel algorithms have better performance on longer posting list and larger block size w.r.t. decoding speed.
    • HTML全文
    • 参考文献(0)
    • 相关文章
    • 施引文献(51)

  • 期刊类型引用(20)

    1. 韩溥. 一种安全可靠的虚拟化智能弹性架构IRF教育网络设计. 网络安全技术与应用. 2025(03): 15-18 . 百度学术
    2. 蒋燕，周彬彬，姚文才，王有香，陈凯，马玮骏，李胜，殷峻暹. 接收方发起的电站数据上报控制方法研究. 中国农村水利水电. 2024(03): 238-243+249 . 百度学术
    3. 梅道光，王丽. 数据中心综合监控系统延迟问题分析及应对策略研究. 信息技术与信息化. 2024(04): 71-76 . 百度学术
    4. 李仁刚，王彦伟，郝锐，肖麟阁，杨乐，杨广文，阚宏伟. Direct xPU：一种新型节点间通信优化的分布式异构计算架构. 计算机研究与发展. 2024(06): 1388-1400 . 本站查看
    5. 蒋万春，李昊阳，陈晗瑜，王洁，王建新，阮昌. 网络拥塞控制方法综述. 软件学报. 2024(08): 3952-3979 . 百度学术
    6. 农佳明，陈孟臻. 基于流量延时调度的无线传感网数据传输拥塞控制方法. 传感技术学报. 2024(08): 1441-1447 . 百度学术
    7. 关世杰，王国靖. 基于状态确认的卫星链路拥塞控制算法研究. 沈阳理工大学学报. 2023(04): 15-18+25 . 百度学术
    8. 高凯辉，李丹. 数据中心网络性能保障研究综述. 电信科学. 2023(06): 1-21 . 百度学术
    9. 胡晋彬，罗望卿，王进. 基于NS-3的计算机网络传输实验教学方案设计. 软件导刊. 2023(06): 187-190 . 百度学术
    10. 张磊，袁鉴辞，李静. 基于物联网技术的医学装备质控管理平台设计. 电子设计工程. 2023(17): 164-168 . 百度学术
    11. 胡晋彬，黄家玮，王建新，王进. 基于直接拥塞通告的数据中心无损网络传输控制机制. 电子学报. 2023(09): 2355-2365 . 百度学术
    12. 李佳琦，周书杰，曹成茂. 面粉存储智能仓库控制系统设计与试验. 中国农机装备. 2023(09): 29-35 . 百度学术
    13. 马力文，周颖. 改善STARTUP阶段空窗现象的BBR单边适应算法. 计算机科学. 2022(02): 321-328 . 百度学术
    14. 孙华宝. 基于SDN的云计算网络模型设计. 信息与电脑(理论版). 2022(07): 50-52 . 百度学术
    15. 涂聪，陈庆奎. 面向AI数据流处理的边缘GPU集群通信系统. 小型微型计算机系统. 2022(06): 1147-1153 . 百度学术
    16. 包红林，李敏，邵志东，张代兰. 面向大规模地震数据并行处理高速可扩展通信技术应用研究. 石油物探. 2022(05): 793-800 . 百度学术
    17. 黄端琼. 福建省海洋与渔业大数据中心建设初探. 海洋信息技术与应用. 2022(04): 32-37 . 百度学术
    18. 林霄，姬硕，岳胜男，孙卫强，胡卫生. 面向跨数据中心网络的节点约束存储转发调度方法. 计算机研究与发展. 2021(02): 319-337 . 本站查看
    19. 张媛媛，姚晋. 一种高可靠网络的设计与实现. 数字通信世界. 2021(04): 15-18 . 百度学术
    20. 管春泓. 云计算背景下数据中心网络架构设计研究. 信息系统工程. 2021(12): 97-100 . 百度学术

    其他类型引用(31)

    • 资源附件(0)
计量
  • 文章访问数:  1770
  • HTML全文浏览量:  0
  • PDF下载量:  588
  • 被引次数: 51
出版历程
  • 发布日期:  2015-04-30

目录

摘要
HTML全文
    参考文献(0)
    相关文章
    施引文献(51)
    资源附件(0)

    /

    返回文章
    返回
    邮件订阅 RSS
    微信订阅号<br/>（实时资讯）

    微信订阅号
    （实时资讯）

    微信服务号<br/>（同步网站）

    微信服务号
    （同步网站）

    微信视频号<br/>（视频分享）

    微信视频号
    （视频分享）

    CCF<br/>（扫码入会）

    CCF
    （扫码入会）

    版权所有 © 《计算机研究与发展》编辑部

    本系统由北京仁和汇智信息技术有限公司开发  百度统计