search

mavam / libbf

:dart: Bloom filters for C++11
http://mavam.github.io/libbf
BSD 3-Clause "New" or "Revised" License
354 stars 89 forks source link

Correction about counting bf. #51

Closed dasfex closed 4 years ago

dasfex commented 4 years ago

Should we decrement count if one of bits are equal to zero?

mavam commented 4 years ago

I'm not sure what you propose exactly. Currently, the algorithm decrements a cell value iff it is non-zero. It is a for-loop, however, so if the first cell is already zero and subsequent ones not, then the algorithms stops immediately. This doesn't affect correctness, because the minimum is used when computing the count.

What should be the expected behavior in your opinion?

dasfex commented 4 years ago

I say about that fact that you stop only the first cell value is zero, as I understand. I suggest firstly take sure that any of cell values is non-zero and if all correct to decrement. I agree that we are use minimum so everything correct. But if you decrement and I am not, can we put this down to the fact that we don't necessarily get a 100% correct result? (sorry for poor eng)

mavam commented 4 years ago

I think that's also a valid approach and slight less aggressive. I haven't had a chance to look around, but I wouldn't be surprised if someone sat down and proved the bounds analytically of the various options.

If there is some evidence that it makes sense to have multiple approaches, we can make the decrement algorithm a policy.