中国科学技术大学:《信息检索与数据挖掘》课程教学资源(研讨汇报)BitFunnel Revisiting Signatures for Search

BIT FUNNEL:REVISITING SIGNATURES FOR SEARCH 信息检索与数据挖掘研讨报告 凌华泽 20190521 Goodwin B,Hopcroft M,Luu D,et al.BitFunnel:Revisiting signatures for search[C]//Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,2017:605-614
-----信息检索与数据挖掘研讨报告 凌华泽 20190521 Goodwin B, Hopcroft M, Luu D, et al. BitFunnel: Revisiting signatures for search[C]//Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2017: 605-614

INTRODUCTION -BitFunnel Signature-based approach Bloom filter Four Challenges ·查询词项时需要查看每个文件的signature higher rank rows ·存在一定的误报率 frequency-conscious signature ·文件大小存在差异,signatur需要适应最大文件 shard the corpus ·基于签名的方案不是众所周知的问题 a cost model
BitFunnel Signature-based approach Bloom filter Four Challenges 查询词项时需要查看每个文件的signature higher rank rows 存在一定的误报率 frequency-conscious signature 文件大小存在差异,signatur需要适应最大文件 shard the corpus 基于签名的方案不是众所周知的问题 a cost model

Q A B C D E M N O P 0 0 BACK GROUND 2 1 00 00100 00 3 3 4 5 .Bit-Sliced Signature 1 6 0 6 10 0 ·这种方法将签名向量从行转换成列以方便 8 0 8888 同时查询多个文档 9 1 9 10 0 10 ·每个文档对应保存16位签名的列,每行对 0 11 对应于文档签名中的位 0 12 13 0 13 ·文档集C={A..) 14 00 150 15100 000 ·查询项Q A B O P .Bit-Sliced Blocked Signature 2 5 ·多个文件公用一列,以减小行的长度 9 01 2n5n9 0100010000000000 A B C D E FG H IJ K L M N O P
Bit-Sliced Signature 这种方法将签名向量从行转换成列以方便 同时查询多个文档 每个文档对应保存16位签名的列,每行对 对应于文档签名中的位 文档集C={A….P} 查询项Q Bit-Sliced Blocked Signature 多个文件公用一列,以减小行的长度

BITFUNNEL INNOVATIONS -Higher Rank Rows Rank00100010010001000 0123456789101112131415 Rank r: Rank111001100 01234567 89101112131415 ir +(io mod2) Rank 2 1100 0123 4567 .W:machine word log2 891011 12131415
Higher Rank Rows Rank r: W : machine word 的log2

noISE 0123456789101112131415 0123456789101112131415 R2COUOSOUOS OUOCOUO R200S00CU000G00SU0 RCUOOS OOU S UOOC O U R:0Us00C000Ug00s00 RoOUUOS OUOS UO OUOUO R 00 S U O C OO 00 C UO S OO Results o 000 S O 0 O S O 0 O UO 00 RRR00500C0000C00S00 0123456789101112131415 ■S:signal bit ·三个rank-l,得到对应的rank-0 ·U:rank-2导致的noise bit .Correlated noise: ■C:rank-0导致的noise bit n0-nr=sr-s0=1-(1-50)2'-s0
S : signal bit U:rank-2导致的 noise bit C: rank-0导致的 noise bit 三 个 rank - 1,得到对应的rank - 0 Correlated noise :

BITFUNNEL INNOVATIONS -Frequency Conscious Signature ·待解决的问题:Bloom filter中每个词项固定使用k个hash ·方案:引入S,存在词项t的文档数目,s不同,使用的hash数目k不同 signal (s) hashes (k) 4) 0.1 1.954242509 0.01 2.995635195 0.001 3.999565488 0.0001 4.999956568 0.00001 5.999995657
Frequency Conscious Signature 待解决的问题:Bloom filter 中每个词项固定使用k个hash 方案:引入S,存在词项t 的文档数目,s不同,使用的hash数目k不同

EXPERIMENATAL EVALUATION Table 1:Corpora. A B C D E Min terms 64 128 256 1,024 2,048 Max terms 127 255 511 2,047 4,095 Documents(M) 5.870 7.545 3.726 0.494 0.157 Total terms(M) 4.181 6.524 6.647 10.109 9.697 Postings (M) 563 1,411 1,268 687 432 Matches/query 1,115 3,561 5,124 3,728 3,688 Input text(GB) 6.85 25.48 21.02 22.89 20.26 ·碎片A、B..逐渐变大
碎片A、B…逐渐变大

EXPERIMENATAL EVALUATION Match Time vs.Quadwords Impact of Frequency Conscious Signatures and Higher Rank Rows Comparison with Contemporary Indexes
Match Time vs. Quadwords Impact of Frequency Conscious Signatures and Higher Rank Rows Comparison with Contemporary Indexes

EXPERIMENATAL EVALUATION Table 3:Query Processing Performance. BitFunnel PEF MG4] Lucene Match Time vs.Quadwords QPS 21,427 14,675 6.866 6,310 False positives(%) 1.62 0.00 0.00 0.00 A Bits per posting 38.43 7.64 7.85 Impact of Frequency Conscious DQ 558 1,921 875 QPS 8,674 5,049 3,636 3,011 Signatures and Higher Rank False positives(‰) 4.32 0.00 0.00 0.00 IDF B Bits per posting 20.72 7.33 7.59 Rows DQ 419 689 479 3 QPS 12,722 3,959 3,096 4,120 。4 False positives (% 3.88 0.00 0.00 0.00 5 .Comparison with C Bits per posting 16.91 6.63 6.88 DQ 752 450 Contemporary Indexes 598 OPS 57,014 8,268 5,900 3,632 False positives (% 2.43 0.00 0.00 0.00 D Bits per posting 13.69 6.25 6.28 DQ 4,163 1,322 939 QPS 105,782 13,151 7,349 4,991 False positives(%) 2.64 0.00 0.00 0.00 Bits per posting 11.69 6.15 6.15 DQ 9,047 2,139 1,195
Match Time vs. Quadwords Impact of Frequency Conscious Signatures and Higher Rank Rows Comparison with Contemporary Indexes
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(研讨汇报)Beliefs and Biases in Web Search.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(研讨汇报)Accelerating Innovation Through Analogy Mining.pdf
- 厦门大学:《智能语音技术》课程教学资源(PPT课件讲稿)第2章 语音信号基础(洪青阳).pdf
- 大连民族大学(大连民族学院):《工程管理信息系统》课程教学资源(PPT课件讲稿)第二章 工程管理信息系统的开发.ppt
- 《现代音响与调音技术》课程教学资源(PPT课件讲稿)第2章 传声器.ppt
- 华中农业大学:《信息检索与利用》课程教学资源(PPT课件讲稿)第一章 信息资源与信息素养概述(主讲:宛章齐).ppt
- 房地产投资决策信息系统的开发(PPT课件讲稿).ppt
- 国家科技基础条件资源调查管理信息系统(PPT讲稿)系统操作培训.ppt
- 西安电子科技大学:《信息管理学》课程教学资源(PPT课件讲稿)第1章 绪论(主讲:赵捧未).ppt
- 海南大学:《管理信息系统》课程教学资源(PPT课件讲稿)第六章 管理信息系统的系统设计.ppt
- 海南大学:《管理信息系统》课程教学资源(PPT课件讲稿)第三章 管理信息系统的技术基础.ppt
- 北京大学:传统图书馆数字图书馆复合图书馆及其发展(PPT讲稿,信息管理系:刘兹恒).ppt
- 上海海事大学:《Management Information System》课程PPT教学课件(英文)Chapter 1 Business Information Systems in Your Career.ppt
- 北京师范大学:《管理信息系统》课程PPT教学课件(教育方向)第2讲 管理信息系统的技术基础.ppsx
- 大连民族大学(大连民族学院):《工程管理信息系统》课程教学资源(PPT课件讲稿)第三章 系统规划.ppt
- 北京师范大学:《管理信息系统》课程PPT教学课件(教育方向)第1讲 管理信息系统概念(主讲:马秀麟).ppsx
- 《管理信息系统的系统》课程教学资源(PPT课件讲稿)第八章 系统实施.ppt
- 北京师范大学:《管理信息系统》课程PPT教学课件(教育方向)第6讲 管理信息系统的项目管理.ppsx
- 《信息系统》课程教学资源(PPT课件)第七章 信息系统的安全与运行管理.ppt
- 《信息检索与利用》课程教学资源(PPT课件讲稿)第二章 信息检索基础知识.ppt
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(研讨汇报)FOTS - Fast oriented Text Spotting with a Unified Network.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(研讨汇报)Memory - Augmented Monte Carlo Tree Search.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(研讨汇报)Neural Ordinary Differential Equations.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(研讨汇报)QuickScorer a Fast Algorithm to Rank Documents with Additive Ensembles of Regression Trees.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(研讨汇报)SSD Single Shot MultiBox Detector.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第1章 绪论(主讲:陈晓辉).pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第2章 布尔检索和倒排索引.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第3章 词项词典和倒排记录表.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第4章 索引构建与索引压缩 4.1 索引构建.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第4章 索引构建与索引压缩 4.2 索引压缩.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第5章 向量模型及检索系统 5.1 向量模型.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第5章 向量模型及检索系统 5.2 检索系统.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第6章 检索的评价.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第7章 相关反馈和查询扩展.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第8章 概率模型.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第9章 基于语言建模的检索模型.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)课程要求(论文阅读&研讨).pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)矩阵分解在信息检索中的应用.pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第10章 文本分类(文本分类及朴素贝叶斯方法).pdf
- 中国科学技术大学:《信息检索与数据挖掘》课程教学资源(课件讲稿)第10章 文本分类(基于向量空间的文本分类).pdf