不精确位图索引中Bloom filter空间预估的一种方法

为了控制不精确位图索引的查询精度，根据位图索引查询结果中假阳元组所占的比率，提出了新的查询精度度量指标-查询假阳率，该指标可以准确反映不精确位图索引的查询精度，并容易被用户理解和设置．根据索引属性的基数、用户预期的属性选择率和查询假阳率，给出了一种预估Bloom filter空间大小的计算公式．实验结果表明，根据该计算公式确定的Bloom filter空间大小能很好地满足用户期望的查询精度．

An Approach for the Pre-estimation of Bloom Filter Size in Approximate Bitmap Index

A new measurement--query false positive rate is proposed to control the query precision of approximate bitmap index based on the ratio of the number of false positive tuples to that of all the tuples in query result. This measurement can well and truly reflect the query precision of approximate bitmap index, and be easily understood and set by user. We also provide a formula to pre-estimate the size of Bloom filter according to the cardinality of attribute indexed, query attribute selectivity rate and query false positive rate. Experiments show that the size of Bloom filter calculated by our proposed formula can fit user＇s expecting query precision well.