From mboxrd@z Thu Jan 1 00:00:00 1970 MIME-Version: 1.0 In-Reply-To: <20101113184343.GA17279@nibiru.local> References: <20101113184343.GA17279@nibiru.local> Date: Sat, 13 Nov 2010 17:31:30 -0500 Message-ID: Subject: Re: [9fans] opposite of bloom filter From: Russ Cox To: weigelt@metux.de, Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> Content-Type: text/plain; charset=UTF-8 Topicbox-Message-UUID: 7c6bb8bc-ead6-11e9-9d60-3106f5b1d025 > 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