Fast checking of set membership on large data Let's say that I am an email provider like Gmail. Let's assume that I have two categories of email-address: spammers and non-spammers. When my servers receive a mail I need to quickly check if that email-ID is in the spammers set and if yes I take some action.

The problem is that each email-Id could be several bytes ( say 10 bytes each) and I might have 1 billion spammers so I need 10GB of RAM to just store the emails in main memory. 

Let's say I want to use only 1 GB RAM. To do this I'm now ready to accept an approximate answer. In particular I'm ok with a non-spam email mistakenly flagged as belonging to the spam  set but not vice versa. How will I do it?
Somebody already tagged this with "bloom-filter".  I agree with them.

A Bloom Filter is a hash-based technique that never results in false negatives, but trades off probability of false positives for saved space.  It meets your specific performance requirements - "fewer than 10 bits per element are required for a 1% false positive probability, independent of the size or number of elements in the set (Bonomi et al. (2006))." (from the linked article)

The main reason you wouldn't use a Bloom filter for this is that removing spammers is computationally expensive, requiring you to rebuild the filter or track your list of removed spammers separately.