Suppose I have encoded a set of cardinality n in a standard Bloom filter (m bits, k hash functions).
I randomly select p bits from the Bloom filter and run the membership query with those p bits only.
What will the false positive/false negative rates be?
This has certainly been studied before in the literature: Could someone provide me with the relevant link?
Dear friend,
You need to write the equations appropriately suited to your problem.
you may look at some of my publications:
Mandal, I., Sairam, N. New machine-learning algorithms for prediction of Parkinson's disease (2014) International Journal of Systems Science, 45 (3), pp. 647-666. DOI: 10.1080/00207721.2012.724114
Mandal, I., Sairam, N. Accurate telemonitoring of Parkinson's disease diagnosis using robust inference system (2013) International Journal of Medical Informatics, 82 (5), pp. 359-377. DOI: 10.1016/j.ijmedinf.2012.10.006
Mandal, I., Sairam, N. Accurate prediction of coronary artery disease using reliable diagnosis system (2012) Journal of Medical Systems, 36 (5), pp. 3353-3373. DOI: 10.1007/s10916-012-9828-0
Mandal, I., Sairam, N. Enhanced classification performance using computational intelligence (2011) Communications in Computer and Information Science, 204 CCIS, pp. 384-391. DOI: 10.1007/978-3-642-24043-0_39
Mandal, I. Software reliability assessment using artificial neural network (2010) ICWET 2010 - International Conference and Workshop on Emerging Trends in Technology 2010, Conference Proceedings, pp. 698-699. DOI: 10.1145/1741906.1742067
Mandal, I. A low-power content-addressable memory (CAM) using pipelined search scheme (2010) ICWET 2010 - International Conference and Workshop on Emerging Trends in Technology 2010, Conference Proceedings, pp. 853-858. DOI: 10.1145/1741906.1742103
Mandal, I. A novel approach for accurate identification of splice junctions based on hybrid algorithms (2014) Journal of Biomolecular Structure and Dynamics
pp. 1-10 | DOI: 10.1080/07391102.2014.944218 PMID: 25203504 http://www.tandfonline.com/eprint/TzMeXxpEXxujtEATHwqY/full
Best regards,
Dr.Indrajit Mandal
.
Dear Dr Mandal
although i am having hard times to link your impressive publication list to my modest problem, i sincerely thank you for ypur excellent advice ; yes indeed "writ(ing) the equations appropriately suited to (my) problem" would sure help me solve it.
But i am just too lazy ...
.
p bits? Do you mean only using p hash functions?
1) If so, there are only false positives without false negatives.
The false positive rate is (1-p')^p, where p' is the probability that any bit of the bloom filter is 0.
2) If you random choose p bits, this is not a good way. Because there will be false negatives, the false negative rate is 1-(1-p')^p
.
Thx !
(indeed in some situations you may not be able to recover all the bits of the filter ... of course, i would not recommend using a few random bits but sometimes you have no choice and still have to bound the quality of the estimation you give from censored data)
.
Dear Fabrice Clerot,
Another solution is not to use random bits, you can use half number of hash functions and half number of memory access, but still achieving the same small false positive rate and without false negatives.
The concrete method is shown in my new paper, which will appear in VLDB 2016:
A Shifting Bloom Filter Framework for Set Queries
You can download the pdf from my homepage or from arxiv.org.
.
interesting !
in my setting, i do not "choose" random bits, it just happens that i have no choice : for instance, imagine a BF distributed on many nodes with a non negligible probability of having a node down (and i have no way to control how the bits are distributed across the nodes)
.
- Badges
- Science topic