How do I deal with large data similarity computation? I have lot of records like this:

M is about 10 million and N is about 100K.
Now I want to apply collaborative filtering on these data, for example, A user comes in with its features(sparse data), how do I find out which existing user is most similar to him/she ?
I don't think I could compute all of the records every time a request comes in, thanks ! Or is there any other algorithm could do this ?
 A: I have been doing a similar procedure on a regular basis lately.  It isn't quick and it takes a decent chunk of HDD space if you process a lot of files.  As a note, the data I work with has fewer "features", more "users", and I use perl to process it.
First off, I would not recommend storing the data together as a single matrix, since most programs (certainly R) will not be able to handle it.  If you store each user as a separate file (.txt or whatever other format works better for you), you can then access them individually, even with R.  
Then, as a new document comes in, you will have to do 100,000 comparisons each between two vectors of length 10 million.
Here's an example in R with two random binary vectors of length 10,000,000.  
x=as.numeric(rnorm(10000000)<0)

y=as.numeric(rnorm(10000000)<0)

sim = crossprod(x,y)/sqrt(crossprod(x)*crossprod(y))  

         [,1]
[1,] 0.4999211

Since the two vectors in this example are random 0,1 vectors, they have a cosine similarity of 0.5.  This one similarity (cosine sim) calculation took less than a second without me trying to optimize it. 
To see how long your process would take, you could loop this code over 100,000 iterations and store each similarity result to a results vector that contains all its matches.  I tried the above code with 1000 iterations and it took about 70 seconds.
You can also insert whatever similarity measure you desire.  It is certainly doable in terms of computation time, but you may want to optimize this if you need it done faster. Hope this gives you an idea of what it might take computationally.
A: What you're talking about is a "Vector Space Model" of information retrieval. Wikipedia lists some programs which help with this - the one I'm most familiar with is Lucene.
This page describes their algorithm. The major points are that 1) you can invert your index, 2) you can look through indices in parallel and 3) you can limit to just the top $k$. All of these things give you a pretty nice speedup.
A: There are a number of non-euclidean distance measures, some of which are specifically used for binary data. Two distance-measures are:
1) Simple Matching Coefficient;
2) Jaccard Coefficient.
They have some different strengths and weaknesses. In the simple matching coefficient, mutual absences and presences contribute to the similarity, although the Jaccard coefficient is good for focusing on mutual presences. 
You can look up those measures for more specifically if you want (Simple Matching and Jaccard are summarized here: http://stat.ethz.ch/education/semesters/ss2012/ams/slides/v4.2.pdf)
If you are using R, the function "dist" in the base package has the simple matching coefficient (referred to as "binary symmetric") and command "vegdist" in the package "vegan" has the Jaccard index.
(Edit): I just found something, which, depending on your hardware, might yield some benefit. If you have a NVIDIA multicore GPU (which is fairly common), the package 'rpud' has a function rpuDist() which computes a number of the standard distance metrics using the GPU with great improvement, as shown here: [http://www.r-tutor.com/gpu-computing/clustering/distance-matrix] http://www.r-tutor.com/gpu-computing/clustering/distance-matrix
I haven't tested it, and with a dataset your size there might be other bottlenecks, but it might be worth having a go at it.  Also, it appears that this, and another package (gputools) are only available on Linux, so that is another limitation...
Hope that helps!
A: You could try sorting your data by the total number of "1s" in each row (vector length). This would give you a space to start searching when you're given a new user. For example, if the new user has a length of 1342, you could check all entries with lengths plus or minus 500. You can do this efficiently if the data are sorted. Obviously, this requires an upfront investment of compute time to pre-sort your data.
The best solution will probably depend on the special features of the data you have (you mention that the data are sparse, so you should try to exploit that somehow). My answer would be effective if the difference in the length of two vectors correlates with the distance between them (e.g. Hamming distance). You could check to see if this is true on a random sample of your data by making a simple scatter plot.
In general, your best bet would be to determine some scalar function that is a good predictor of how similar two entries are, then sort your data by that function, and then search locally when given a new entry. My first guess would be to try vector length as that function, but there is a decent chance you'll be able to find a better one by playing around with your data.
