An Approach for the Pre-estimation of Bloom Filter Size in Approximate Bitmap Index
Xuejun Jiang · Transactions of Shenyang Ligong University · 2009
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.