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

发布时间：2017-10-11 21:15

  本文关键词：基于指令级并行的倒排索引压缩算法

  更多相关文章： 单指令多数据流 倒排索引 压缩 整数编码 信息检索

【摘要】：文本信息数量的快速增长给传统的信息检索技术带来了新的挑战.搜索引擎通常使用倒排索引来高效地处理查询.为了减少存储开销和加快访问速度,倒排索引通常被压缩存储.因此,如何选择一个高性能的压缩算法对高效查询处理是非常有必要的.在已有倒排链压缩算法PackedBinary和PForDelta的基础上,利用CPU的超标量特性和SIMD向量指令集,将其压缩和解压缩中的关键步骤并行化,提出了2种指令级并行压缩算法SIMD-PB和SIMD-PFD.基于GOV2和ClueWeb09B两个公开数据集的实验表明,SIMD-PB和SIMD-PFD算法在压缩率不变的情况下,压缩和解压缩速度比现有的压缩算法均有非常明显的提升.其中解压缩速度比起目前最好的倒排链压缩算法,最高能提升17%.此外,实验表明算法在较长的倒排链、较大的压缩块单位上有更好的解压缩性能.
【作者单位】： 北京大学网络与信息系统研究所;淘宝(中国)软件有限公司;北京理工大学;
【关键词】： 单指令多数据流 倒排索引 压缩 整数编码 信息检索
【基金】：国家“九七三”重点基础研究发展计划基金项目(2014CB340400) 国家自然科学基金项目(61272340) 江苏未来网络创新研究院项目-云服务数字资源搜索(BY2013095-4-02)
【分类号】：TP391.3
【正文快照】： 此外,实验表明算法在较长的倒排链、较大的压缩块单位上有更好的解压缩性能.在网络时代,文本信息数量的快速增长给传统的信息检索技术带来了新的挑战.搜索引擎作为网络时代的信息检索工具,如今已成为用户获取网络信息的主要途径之一,其核心的数据结构是倒排索引.倒排索引由词

【参考文献】

中国期刊全文数据库 前3条

1 朱虹,吴林;倒排索引压缩及在RDBMS全文检索中的实现[J];华中科技大学学报(自然科学版);2005年04期

2 王虎;王潜平;;对几种倒排文件压缩技术的研究与分析[J];计算机工程与应用;2006年07期

3 张旭东;孙志明;刘亚宁;单栋栋;闫宏飞;;基于64位体系结构的倒排索引压缩算法[J];计算机工程;2014年02期

【共引文献】

中国期刊全文数据库 前8条

1 丁维;周长胜;崔凌云;马志强;杨娜;;基于多级指引索引的高效技术[J];计算机与信息技术;2006年06期

2 刘小珠;彭智勇;陈旭;;高效的随机访问分块倒排文件自索引技术[J];计算机学报;2010年06期

3 马健;张太红;陈燕红;;中文搜索引擎分块倒排索引存储模式[J];计算机应用;2013年07期

4 张旭东;孙志明;刘亚宁;单栋栋;闫宏飞;;基于64位体系结构的倒排索引压缩算法[J];计算机工程;2014年02期

5 陈燕红;;智能中文农业垂直搜索引擎体系的架构与实现[J];湖北农业科学;2014年12期

6 史亮;张鸿;刘欣然;王勇;王斌;;倒排索引中的文档序号重排技术综述[J];中文信息学报;2015年02期

7 方雪华;刘祖润;;中小型中文报刊全文数据库的建立及其应用[J];邵阳学院学报(自然科学版);2006年01期

8 Hao Wu;Guoliang Li;Lizhu Zhou;;Ginix: Generalized Inverted Index for Keyword Search[J];Tsinghua Science and Technology;2013年01期

中国重要会议论文全文数据库 前3条

1 ;Improved Self-Indexing Inverted Files for Full-Text Retrieval[A];第四届全国信息检索与内容安全学术会议论文集（下）[C];2008年

2 朱虹;黄欢;;DM4全文检索机制的改进[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

3 刘小珠;孙莎;曾承;彭智勇;;基于缓存的倒排索引机制研究[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

中国博士学位论文全文数据库 前5条

1 杨传耀;中文信息检索索引模型及相关技术研究[D];复旦大学;2007年

2 刘健;面向信息检索的文本信息组织关键技术研究[D];国防科学技术大学;2009年

3 朱明杰;互联网搜索系统中的高性能查询问题研究[D];中国科学技术大学;2009年

4 吴炜;密文全文检索系统中的索引机制研究[D];华中科技大学;2009年

5 孙德才;基于q-gram过滤的近似串匹配技术研究[D];湖南大学;2012年

中国硕士学位论文全文数据库 前10条

1 马静;基于web的数字化资源全文检索系统的设计与实现[D];西安电子科技大学;2010年

2 刘巍;基于内容的同源音频和视频检索[D];北京邮电大学;2011年

3 陈恒;基于内容的视频搜索引擎[D];北京邮电大学;2011年

4 李春丰;面向动态文本的在线索引若干问题研究[D];广东工业大学;2011年

5 蒋励;关系数据库中教育信息全文检索效率的改进研究与实现[D];天津师范大学;2011年

6 薛煜阳;农业搜索引擎倒排索引缓冲机制研究[D];新疆农业大学;2011年

7 潘胜一;基于倒排索引的压缩算法性能研究[D];杭州电子科技大学;2009年

8 孙德才;相似字符串匹配过滤算法研究[D];湖南大学;2009年

9 苗帅;海量数据存储与全文检索[D];江苏科技大学;2011年

10 漆团;数据库中基于多索引段的全文索引研究[D];华中科技大学;2011年

【二级参考文献】

中国期刊全文数据库 前3条

1 朱虹,吴林;倒排索引压缩及在RDBMS全文检索中的实现[J];华中科技大学学报(自然科学版);2005年04期

2 王虎;王潜平;;对几种倒排文件压缩技术的研究与分析[J];计算机工程与应用;2006年07期

3 纪蕾,陈英;基于文档重排的索引压缩技术[J];清华大学学报(自然科学版);2005年S1期

【相似文献】

中国期刊全文数据库 前10条

1 吴恒山,刘兴宇,左琼;一种基于可扩展散列表的倒排索引更新策略[J];计算机工程;2004年08期

2 王冬;左万利;赫枫龄;彭涛;张长利;;一种增量倒排索引结构的设计与实现[J];吉林大学学报(理学版);2007年06期

3 林洁;李丹宁;吴晓;;基于用户的个性化综合倒排索引[J];杭州师范大学学报(自然科学版);2008年03期

4 宁可为;王炜;;基于倒排索引的答疑系统知识库文本研究[J];湖北广播电视大学学报;2010年06期

5 谭斌;丁莎;车念;徐力;聂清彬;谭钱茂;黄翔;;一种面向域的高效倒排索引结构及实时更新[J];四川大学学报(自然科学版);2011年02期

6 杨建武,陈晓鸥;基于倒排索引的文本相似搜索[J];计算机工程;2005年05期

7 邝砾;邓水光;李莹;吴健;吴朝晖;;使用倒排索引优化面向组合的语义服务发现[J];软件学报;2007年08期

8 赵亮;;基于复合结构的高效索引在线更新策略[J];计算机工程;2008年02期

9 吴晓;李丹宁;吕爽;林洁;李丹;;基于综合倒排索引的个性化搜索引擎研究[J];微计算机信息;2008年27期

10 张旭东;孙志明;刘亚宁;单栋栋;闫宏飞;;基于64位体系结构的倒排索引压缩算法[J];计算机工程;2014年02期

中国重要会议论文全文数据库 前4条

1 李栋;史晓东;;对搜索引擎中倒排索引更新策略的研究和改进[A];第二十二届中国数据库学术会议论文集（技术报告篇）[C];2005年

2 刘小珠;孙莎;曾承;彭智勇;;基于缓存的倒排索引机制研究[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

3 维尼拉·木沙江;吴俊森;吐尔根·依布拉音;;维吾尔文搜索引擎的倒排索引设计与实现[A];民族语言文字信息技术研究——第十一届全国民族语言文字信息学术研讨会论文集[C];2007年

4 孙宇;刘憬;张宇;刘挺;;基于分词和倒排索引的短文本检索技术的研究与实现[A];黑龙江省计算机学会2007年学术交流年会论文集[C];2007年

中国博士学位论文全文数据库 前1条

1 艾列富;基于内容的大规模图像索引与检索方法研究[D];华中科技大学;2014年

中国硕士学位论文全文数据库 前10条

1 刘兴宇;基于倒排索引的全文检索技术研究[D];华中科技大学;2004年

2 刘红雨;基于倒排索引的微博话题检测[D];哈尔滨工业大学;2013年

3 毛福林;倒排索引压缩算法研究[D];北京交通大学;2015年

4 汪红敏;基于固态硬盘的倒排索引动态更新策略及其优化研究[D];华中科技大学;2013年

5 林洁;基于综合倒排索引的个性化搜索技术研究[D];贵州大学;2008年

6 陈雪帆;基于固态硬盘的倒排索引构建与维护策略研究[D];华中科技大学;2012年

7 吴俊森;维哈柯多语种搜索引擎倒排索引模块的实现[D];新疆大学;2007年

8 潘胜一;基于倒排索引的压缩算法性能研究[D];杭州电子科技大学;2009年

9 董长春;基于Hadoop的倒排索引技术的研究[D];辽宁大学;2011年

10 代万能;倒排索引技术在Hadoop平台上的研究与实现[D];电子科技大学;2013年

，

本文编号：1014774