a Bloom filter works much like the Rabin-Miller primality test: the URL is entered into a set of equations that essentially check for “witnesses” to its novelty. (Rather than proclaim “n is not prime,” these equations say “I have not seen n before.”) If you’re willing to tolerate an error rate of just 1% or 2%, storing your findings in a probabilistic data structure like a Bloom filter will save you significant amounts of both time and space.
read up on book filters to see how they work
