计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2015年
5期
995-1004
,共10页
闫宏飞%张旭东%单栋栋%毛先领%赵鑫
閆宏飛%張旭東%單棟棟%毛先領%趙鑫
염굉비%장욱동%단동동%모선령%조흠
单指令多数据流%倒排索引%压缩%整数编码%信息检索
單指令多數據流%倒排索引%壓縮%整數編碼%信息檢索
단지령다수거류%도배색인%압축%정수편마%신식검색
single instruction multiple data(SIMD)%inverted index%compression%integer encoding%information retrieval
文本信息数量的快速增长给传统的信息检索技术带来了新的挑战.搜索引擎通常使用倒排索引来高效地处理查询.为了减少存储开销和加快访问速度,倒排索引通常被压缩存储.因此,如何选择一个高性能的压缩算法对高效查询处理是非常有必要的.在已有倒排链压缩算法PackedBinary和PForDelta的基础上,利用CPU的超标量特性和SIMD向量指令集,将其压缩和解压缩中的关键步骤并行化,提出了2种指令级并行压缩算法SIMD-PB和SIMD-PFD.基于GOV2和ClueWeb09B两个公开数据集的实验表明,SIMD-PB和SIMD-PFD算法在压缩率不变的情况下,压缩和解压缩速度比现有的压缩算法均有非常明显的提升.其中解压缩速度比起目前最好的倒排链压缩算法,最高能提升17％.此外,实验表明算法在较长的倒排链、较大的压缩块单位上有更好的解压缩性能.
文本信息數量的快速增長給傳統的信息檢索技術帶來瞭新的挑戰.搜索引擎通常使用倒排索引來高效地處理查詢.為瞭減少存儲開銷和加快訪問速度,倒排索引通常被壓縮存儲.因此,如何選擇一箇高性能的壓縮算法對高效查詢處理是非常有必要的.在已有倒排鏈壓縮算法PackedBinary和PForDelta的基礎上,利用CPU的超標量特性和SIMD嚮量指令集,將其壓縮和解壓縮中的關鍵步驟併行化,提齣瞭2種指令級併行壓縮算法SIMD-PB和SIMD-PFD.基于GOV2和ClueWeb09B兩箇公開數據集的實驗錶明,SIMD-PB和SIMD-PFD算法在壓縮率不變的情況下,壓縮和解壓縮速度比現有的壓縮算法均有非常明顯的提升.其中解壓縮速度比起目前最好的倒排鏈壓縮算法,最高能提升17％.此外,實驗錶明算法在較長的倒排鏈、較大的壓縮塊單位上有更好的解壓縮性能.
문본신식수량적쾌속증장급전통적신식검색기술대래료신적도전.수색인경통상사용도배색인래고효지처리사순.위료감소존저개소화가쾌방문속도,도배색인통상피압축존저.인차,여하선택일개고성능적압축산법대고효사순처리시비상유필요적.재이유도배련압축산법PackedBinary화PForDelta적기출상,이용CPU적초표량특성화SIMD향량지령집,장기압축화해압축중적관건보취병행화,제출료2충지령급병행압축산법SIMD-PB화SIMD-PFD.기우GOV2화ClueWeb09B량개공개수거집적실험표명,SIMD-PB화SIMD-PFD산법재압축솔불변적정황하,압축화해압축속도비현유적압축산법균유비상명현적제승.기중해압축속도비기목전최호적도배련압축산법,최고능제승17％.차외,실험표명산법재교장적도배련、교대적압축괴단위상유경호적해압축성능.
