文献类型：期刊文献

中文题名：基于Bloom过滤器的精确位图索引

英文题名：Precise Bitmap Index Based on Bloom Filter

作者：肖琳[1];梁军[2];钮文良[1]

第一作者：肖琳

机构：[1]北京联合大学应用科技学院;[2]北京联合大学电子信息技术实验实训基地

第一机构：北京联合大学应用科技学院

年份：2011

卷号：37

期号：13

起止页码：272-274

中文期刊名：计算机工程

外文期刊名：Computer Engineering

收录：CSTPCD;;Scopus;北大核心:【北大核心2008】；CSCD:【CSCD2011_2012】；

语种：中文

中文关键词：位图索引;Bloom过滤器;假阳率;假阳表;压缩率;查询效率

外文关键词：bitmap index; Bloom Filter（BF）; false positive probability; false positive table; compression ratio; search efficiency

摘要：针对基于Bloom过滤器的位图索引方法查询结果不精确的问题,提出一种精确位图索引算法——FPT-Index。该算法采用Bloom过滤器对基本位图索引进行压缩,同时引入假阳表,对查询结果进行筛选,从而达到精确查询的目的。通过理论分析得出,在给定关键词出现频率的前提条件下,可计算出最小压缩率以及所需哈希函数的个数。实验结果表明,FPT-Index相较于WAH方法在压缩率和查询效率两方面都有较好的表现。
A precise bitmap index named FPT-Index is proposed to solve the problem that the query results are not precise m approximate oltmap index base on bloom filter. FPT-Index uses bloom filter to compress the basic bitmap index and introduces false positive table to screen the query results. The query results from FPT-Index are precise. Through theoretical analysis, the minimum of compression ratio and the corresponding number of hash functions can be worked out when the keyword frequency is confirmed. Experimental results show that FPT-Index does better in compression ratio and search performance than WAH.