What methods scale to really big data?

I have found that linear models work exceptionally well. It's possible to code up a logistic regression or neural network trained with stochastic gradient descent in a few lines of C code that will train and test very quickly and use very little memory even without dimensionality reduction since only one instance needs to be held in memory.

If you're not a fan of C programming, John Langford has already done the work for you with a very full-featured program called Vowpal Wabbit. Installing Vowpal Wabbit can be a bit of a pain, depending on how frequently you do these sorts of things, but this link might be of some help. Vowpal Wabbit uses a neat dimensionality-reduction trick called feature hashing, which has been discussed in many other questions here... just search for it if you're interested.

If VW doesn't meet your needs, there are a couple other fast-linear-model programs out there:

• LibLinear
• Bayesian Regression
• LibSVM

One thing worth noting is that Vowpal Wabbit, while it can train an SVM-like model with hinge loss, doesn't train kernel SVMs and as such will train a strictly linear model. LibLinear and LibSVM will build kernel models.

Hope this helps.

Linear methods, as suggested by Troy, are a very good candidate for your problem. Linear methods tend to scale well with the number of examples & very high dimensionality makes it likely that your problem is linearly separable. However with more than 10k training samples you should really use either primal space SVMs (eg liblinear, Vowpal Wabbit, Pegasos & SGD) or approximate solvers like those based on core sets or Nydstrom method. Avoid dual space SVMs (eg libsvm, svmlight and most of the older svm solvers) for data sets of this size. I have also found that for very sparse data, as I am guessing yours is, L2 regularization usually works better than L1, contrary to what is recommended for most applications.

For this kind of data the main alternative to linear methods are ensemble methods (eg random forests). They can be made to scale by training the base learners on manageable sized samples of the original data, considering only subsets of the features during individual steps of the algorithm & parallelizing the training of the base learners.

A useful technique that can be combined with almost any ML technique is to use hashed representations or random projections (the only dimension reduction techniques that are likely to scale to your data). This can make it feasible to use methods that would not be able to handle your data in it's original form and may actually help with accuracy even for methods that can handle the original data. However, the dimension reduction must not be too aggressive; you should probably leave at least 1000s of dimensions.

Well, traditionally you could use Principal Component Analysis (or Factor Analysis) to reduce the high dimensionality, but if we assume a nonlinear feature space you would probably be best served with a Manifold Learning technique.

Assuming you manage to get the feature situation under control, handling a large number of observations is really dependent on what you want to do with the data. If you look around at a lot of the big name conferences in recent years, many of the popular techniques for classification or clustering, such as SVM and k-means have had the theory extended for large datasets.