本文關鍵詞：基于指令級并行的倒排索引壓縮算法

  更多相關文章： 單指令多數(shù)據(jù)流 倒排索引 壓縮 整數(shù)編碼 信息檢索

【摘要】：文本信息數(shù)量的快速增長給傳統(tǒng)的信息檢索技術帶來了新的挑戰(zhàn).搜索引擎通常使用倒排索引來高效地處理查詢.為了減少存儲開銷和加快訪問速度,倒排索引通常被壓縮存儲.因此,如何選擇一個高性能的壓縮算法對高效查詢處理是非常有必要的.在已有倒排鏈壓縮算法PackedBinary和PForDelta的基礎上,利用CPU的超標量特性和SIMD向量指令集,將其壓縮和解壓縮中的關鍵步驟并行化,提出了2種指令級并行壓縮算法SIMD-PB和SIMD-PFD.基于GOV2和ClueWeb09B兩個公開數(shù)據(jù)集的實驗表明,SIMD-PB和SIMD-PFD算法在壓縮率不變的情況下,壓縮和解壓縮速度比現(xiàn)有的壓縮算法均有非常明顯的提升.其中解壓縮速度比起目前最好的倒排鏈壓縮算法,最高能提升17%.此外,實驗表明算法在較長的倒排鏈、較大的壓縮塊單位上有更好的解壓縮性能.
【作者單位】： 北京大學網(wǎng)絡與信息系統(tǒng)研究所;淘寶(中國)軟件有限公司;北京理工大學;
【關鍵詞】： 單指令多數(shù)據(jù)流 倒排索引 壓縮 整數(shù)編碼 信息檢索
【基金】：國家“九七三”重點基礎研究發(fā)展計劃基金項目(2014CB340400) 國家自然科學基金項目(61272340) 江蘇未來網(wǎng)絡創(chuàng)新研究院項目-云服務數(shù)字資源搜索(BY2013095-4-02)
【分類號】：TP391.3
【正文快照】： 此外,實驗表明算法在較長的倒排鏈、較大的壓縮塊單位上有更好的解壓縮性能.在網(wǎng)絡時代,文本信息數(shù)量的快速增長給傳統(tǒng)的信息檢索技術帶來了新的挑戰(zhàn).搜索引擎作為網(wǎng)絡時代的信息檢索工具,如今已成為用戶獲取網(wǎng)絡信息的主要途徑之一,其核心的數(shù)據(jù)結構是倒排索引.倒排索引由詞

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前3條

1 朱虹,吳林;倒排索引壓縮及在RDBMS全文檢索中的實現(xiàn)[J];華中科技大學學報(自然科學版);2005年04期

2 王虎;王潛平;;對幾種倒排文件壓縮技術的研究與分析[J];計算機工程與應用;2006年07期

3 張旭東;孫志明;劉亞寧;單棟棟;閆宏飛;;基于64位體系結構的倒排索引壓縮算法[J];計算機工程;2014年02期

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前8條

1 丁維;周長勝;崔凌云;馬志強;楊娜;;基于多級指引索引的高效技術[J];計算機與信息技術;2006年06期

2 劉小珠;彭智勇;陳旭;;高效的隨機訪問分塊倒排文件自索引技術[J];計算機學報;2010年06期

3 馬健;張?zhí)t;陳燕紅;;中文搜索引擎分塊倒排索引存儲模式[J];計算機應用;2013年07期

4 張旭東;孫志明;劉亞寧;單棟棟;閆宏飛;;基于64位體系結構的倒排索引壓縮算法[J];計算機工程;2014年02期

5 陳燕紅;;智能中文農(nóng)業(yè)垂直搜索引擎體系的架構與實現(xiàn)[J];湖北農(nóng)業(yè)科學;2014年12期

6 史亮;張鴻;劉欣然;王勇;王斌;;倒排索引中的文檔序號重排技術綜述[J];中文信息學報;2015年02期

7 方雪華;劉祖潤;;中小型中文報刊全文數(shù)據(jù)庫的建立及其應用[J];邵陽學院學報(自然科學版);2006年01期

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

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 ;Improved Self-Indexing Inverted Files for Full-Text Retrieval[A];第四屆全國信息檢索與內容安全學術會議論文集（下）[C];2008年

2 朱虹;黃歡;;DM4全文檢索機制的改進[A];第二十三屆中國數(shù)據(jù)庫學術會議論文集（技術報告篇）[C];2006年

3 劉小珠;孫莎;曾承;彭智勇;;基于緩存的倒排索引機制研究[A];第二十四屆中國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2007年

中國博士學位論文全文數(shù)據(jù)庫 前5條

1 楊傳耀;中文信息檢索索引模型及相關技術研究[D];復旦大學;2007年

2 劉健;面向信息檢索的文本信息組織關鍵技術研究[D];國防科學技術大學;2009年

3 朱明杰;互聯(lián)網(wǎng)搜索系統(tǒng)中的高性能查詢問題研究[D];中國科學技術大學;2009年

4 吳煒;密文全文檢索系統(tǒng)中的索引機制研究[D];華中科技大學;2009年

5 孫德才;基于q-gram過濾的近似串匹配技術研究[D];湖南大學;2012年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 馬靜;基于web的數(shù)字化資源全文檢索系統(tǒng)的設計與實現(xiàn)[D];西安電子科技大學;2010年

2 劉巍;基于內容的同源音頻和視頻檢索[D];北京郵電大學;2011年

3 陳恒;基于內容的視頻搜索引擎[D];北京郵電大學;2011年

4 李春豐;面向動態(tài)文本的在線索引若干問題研究[D];廣東工業(yè)大學;2011年

5 蔣勵;關系數(shù)據(jù)庫中教育信息全文檢索效率的改進研究與實現(xiàn)[D];天津師范大學;2011年

6 薛煜陽;農(nóng)業(yè)搜索引擎倒排索引緩沖機制研究[D];新疆農(nóng)業(yè)大學;2011年

7 潘勝一;基于倒排索引的壓縮算法性能研究[D];杭州電子科技大學;2009年

8 孫德才;相似字符串匹配過濾算法研究[D];湖南大學;2009年

9 苗帥;海量數(shù)據(jù)存儲與全文檢索[D];江蘇科技大學;2011年

10 漆團;數(shù)據(jù)庫中基于多索引段的全文索引研究[D];華中科技大學;2011年

【二級參考文獻】

中國期刊全文數(shù)據(jù)庫 前3條

1 朱虹,吳林;倒排索引壓縮及在RDBMS全文檢索中的實現(xiàn)[J];華中科技大學學報(自然科學版);2005年04期

2 王虎;王潛平;;對幾種倒排文件壓縮技術的研究與分析[J];計算機工程與應用;2006年07期

3 紀蕾,陳英;基于文檔重排的索引壓縮技術[J];清華大學學報(自然科學版);2005年S1期

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 吳恒山,劉興宇,左瓊;一種基于可擴展散列表的倒排索引更新策略[J];計算機工程;2004年08期

2 王冬;左萬利;赫楓齡;彭濤;張長利;;一種增量倒排索引結構的設計與實現(xiàn)[J];吉林大學學報(理學版);2007年06期

3 林潔;李丹寧;吳曉;;基于用戶的個性化綜合倒排索引[J];杭州師范大學學報(自然科學版);2008年03期

4 寧可為;王煒;;基于倒排索引的答疑系統(tǒng)知識庫文本研究[J];湖北廣播電視大學學報;2010年06期

5 譚斌;丁莎;車念;徐力;聶清彬;譚錢茂;黃翔;;一種面向域的高效倒排索引結構及實時更新[J];四川大學學報(自然科學版);2011年02期

6 楊建武,陳曉鷗;基于倒排索引的文本相似搜索[J];計算機工程;2005年05期

7 鄺礫;鄧水光;李瑩;吳健;吳朝暉;;使用倒排索引優(yōu)化面向組合的語義服務發(fā)現(xiàn)[J];軟件學報;2007年08期

8 趙亮;;基于復合結構的高效索引在線更新策略[J];計算機工程;2008年02期

9 吳曉;李丹寧;呂爽;林潔;李丹;;基于綜合倒排索引的個性化搜索引擎研究[J];微計算機信息;2008年27期

10 張旭東;孫志明;劉亞寧;單棟棟;閆宏飛;;基于64位體系結構的倒排索引壓縮算法[J];計算機工程;2014年02期

中國重要會議論文全文數(shù)據(jù)庫 前4條

1 李棟;史曉東;;對搜索引擎中倒排索引更新策略的研究和改進[A];第二十二屆中國數(shù)據(jù)庫學術會議論文集（技術報告篇）[C];2005年

2 劉小珠;孫莎;曾承;彭智勇;;基于緩存的倒排索引機制研究[A];第二十四屆中國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2007年

3 維尼拉·木沙江;吳俊森;吐爾根·依布拉音;;維吾爾文搜索引擎的倒排索引設計與實現(xiàn)[A];民族語言文字信息技術研究——第十一屆全國民族語言文字信息學術研討會論文集[C];2007年

4 孫宇;劉憬;張宇;劉挺;;基于分詞和倒排索引的短文本檢索技術的研究與實現(xiàn)[A];黑龍江省計算機學會2007年學術交流年會論文集[C];2007年

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 艾列富;基于內容的大規(guī)模圖像索引與檢索方法研究[D];華中科技大學;2014年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 劉興宇;基于倒排索引的全文檢索技術研究[D];華中科技大學;2004年

2 劉紅雨;基于倒排索引的微博話題檢測[D];哈爾濱工業(yè)大學;2013年

3 毛福林;倒排索引壓縮算法研究[D];北京交通大學;2015年

4 汪紅敏;基于固態(tài)硬盤的倒排索引動態(tài)更新策略及其優(yōu)化研究[D];華中科技大學;2013年

5 林潔;基于綜合倒排索引的個性化搜索技術研究[D];貴州大學;2008年

6 陳雪帆;基于固態(tài)硬盤的倒排索引構建與維護策略研究[D];華中科技大學;2012年

7 吳俊森;維哈柯多語種搜索引擎倒排索引模塊的實現(xiàn)[D];新疆大學;2007年

8 潘勝一;基于倒排索引的壓縮算法性能研究[D];杭州電子科技大學;2009年

9 董長春;基于Hadoop的倒排索引技術的研究[D];遼寧大學;2011年

10 代萬能;倒排索引技術在Hadoop平臺上的研究與實現(xiàn)[D];電子科技大學;2013年

，

本文編號：1014774