基于Bloom过滤器的精确位图索引  

Precise Bitmap Index Based on Bloom Filter

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

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

出　　处：《计算机工程》2011年第13期272-274,278,共4页Computer Engineering

摘　　要：针对基于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.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]