Sparse hyperspace clustering I have a dataset of M elements where every item is represented by a feature vector of length N where N is very large and only a small subset of N is bigger then zero for every item. So I have a sparse MxN  matrix and I want to cluster these M items.
What tools and algorithms do you advise to use? Any script or library in R or in other programming languages would be very useful.
 A: Your data is quite likely best modeled as a network. I suggest using a similarity (note, not a distance) between vectors. This could for example be the cosine similarity, or, if weights are not important, the Tanimoto coefficient. Cosine similarity is often used in document clustering (which has similar dimensionality characteristics), and Tanimoto is often used in what is called 'fingerprint' analysis (e.g. when analysing databases of chemical compounds), again with similar dimensionality characteristics. You can subsequently cluster such a network with one of the algorithms that do not require the number of clusters as input parameter; I recommend either RNSC (restricted neighbour search clustering), the Louvain method, or MCL (Markov cluster algorithm; disclaimer - I wrote this). Another (well-known) algorithm is APC (Affinity Propagation Clustering), which is based on similar principles as MCL but differs quite a bit in how these principles are modeled.
A: The Matrix package is standard in R and comes installed by default.
Example:
library(Matrix)
N <- 1e6
M <- 1e4
x <- Matrix(0, nrow=N, ncol=M)
x[1, 2] <- 1
x[1:10, 1:10]

Most commands are nearly the same as matrix.  There are a couple things that are slightly different that you need to make sure to use so that you stay in sparse matrix format instead of standard matrix format (e.g., cBind instead of cbind).
reference: http://cran.r-project.org/web/packages/Matrix/Matrix.pdf
You might also check the packages sparcl and bibmemory and see what they do in their examples.
