1
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But since you are anyways alright with false positives as long as the fraction of folks required to be removed from the spammers list is small you don't need to update the filter $\endgroup$ – wabbit Jun 16 '16 at 1:59
  • $\begingroup$ You can use a cuckoo filter when you need support for deletions. $\endgroup$ – Emre May 7 '18 at 3:40
0
$\begingroup$

Your problem is suitable for machine learning technique.
You are modeling the problem as a non-parametric model, i.e. parameters are dependent on your data, as your data grows, parameters also grow as well.
Simple non-parametric models will be something like k-nearest neighbors. each time you want to predict some new data point, you have to calculate all the training examples distances with that data point.
So keeping track of email addresses is not a good idea, what if you let a machine read the content, then automatically decide with a fixed set of parameters what the output should be?

You could access large dataset of spam/ham emails. and train large deep models on, following that fine-tune it on your custom dataset.

As for the accuracy of the model, after you train a classifier, the output of the model will be a simple real value between 0 and 1, telling you how much the model believes it's ham or spam respectively, usually, we set a threshold of 0.5 to give definite answers. yet if you want to optimize the false negatives, you could increase the threshold.
e.g. if you set it to be 0.8, you are saying I don't want the machine to classify it as ham if it's not 80% sure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.