[tlaplus] Best way to handle a probabilistic data structure.

["thomas...@xxxxxxxxx" <thomasgebert@xxxxxxxxx>]

I wanted to simulate something like a Bloom Filter. For those unaware, a Bloom Filter is kind of like a set, but when looking up a value in a set, there's a risk of a false positive, but never a risk of a false negative.

I'm not terribly concerned with the actual implementation of this, so I just wanted to make an operator like "IsInFilter(value, filter)", where filter is actually just a set, and if value is in the set it might return TRUE or FALSE, but if it's not in the set it always returns FALSE.

I'm having a little trouble expressing the non-determinism with this.  My initial implementation was something like this:


IsInSet(value, mySet) ==
    \E result \in {TRUE, FALSE} :
        (value \in mySet => result) /\ (value \notin mySet => FALSE)

But I think the existential quantifier in this case is tautological.  Does anyone have any ideas on the best way of handling this?

-- 
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+unsubscribe@xxxxxxxxxxxxxxxx.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/4933963d-b1fb-4002-b0ca-2e9ab961c32dn%40googlegroups.com.