Handling huge dataset imbalance (2 class values) and appropriate ML algorithm
I'm not allowed to comment, but I have more a suggestion: you could try to implement some "Over-sampling Techniques" like SMOTE:
http://scholar.google.com/scholar?q=oversampling+minority+classes