> I'm currently looking for the opposite of an bloom filter, which > may have false negatives but no false positives. > > The purpose is allowing an spooling (store+forward) mail relay > to learn which addresses are not accepted by the actual maildrop > (which is connected by an uucp-link, so no direct smtp chat), > to get rid of the thousands silly error bounces from brute force > attacks on email addresses. > > An trivial idea would be simply using an hashtable as blacklist, > but obviously that would become very big. I need a more compact > form, perhaps a subset of regex'es, a colored (b)tree, etc ? > > Any ideas ?
Use a Bloom filter. You are looking for the opposite of a Bloom filter in order to ask the question "is this an invalid email address?". Instead, use a Bloom filter to ask the question "is this a valid email address?". This requires the remote uucp site to give you a Bloom filter with all the valid addresses inserted, but that seems unavoidable. I don't know how the opposite-of-Bloom-filter approach would work anyway. Russ
