<div dir="ltr">you'd use the bloom filter first to determine if it's possible that you've seen it before, and then if you get a hit, just do a lookup into some other structure.  Depending on your hash functions and the sparsity, it could be significantly faster; consider, for example, if the sequence is<div><br></div><div>1,2,3,4,2^1024,2^1024+1,2^1024+2...</div><div><br></div><div>just about anything except a bloom filter is going to have possibly-interesting behavior when the 2^1024 shows up.  The bloom filter may give you some false positives and will generally be slower, but if you're trying to maintain a packet train for, like, remote medical surgery, you might accept the extra space and the slightly higher average latency for less jitter.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 18, 2016 at 10:45 AM, Jesper Louis Andersen <span dir="ltr"><<a href="mailto:jesper.louis.andersen@gmail.com" target="_blank">jesper.louis.andersen@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><span class=""><br><div class="gmail_quote">On Thu, Feb 18, 2016 at 7:28 PM,  <span dir="ltr"><<a href="mailto:dmkolesnikov@gmail.com" target="_blank">dmkolesnikov@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">The right data structure is either bloom filter or scalable bloom filter.</blockquote></div><br></span>You also need to delete elements, which a cuckoo filter can do.</div><div class="gmail_extra"><br></div><div class="gmail_extra">The problem with bloom filters in this situation is the probability of error as far as I see. They either say NOPE or MAYBE??? The other problem is that it probably wont beat integer operations on 60 bit words since it requires a hash.<span class="HOEnZb"><font color="#888888"><br><br clear="all"><div><br></div>-- <br><div>J.</div>
</font></span></div></div>
<br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br></div>