Um, wouldn't just a cache of the last N (based on memory available) items (or their hashes, whatever) just do the job, and do it better than his solution (which removes elements randomly based on collisions, rather than just removing the oldest element in the cache when it gets full, a much better approach given the time locality he describes)?

The description in this article seems to add too much complexity ("the opposite of a bloom filter") for what really is just a simple cache (albeit, IMO, a relatively inefficient one for the problem he describes).