Cluster very many sparse binary vectors I have a very big set of high-dimensional, but sparse binary vectors. Each vector represents a "one-hot-style" n-gram sequence of words where each index of the words that occur in the n-gram is set to 1, all others to 0. E.g.

[0,0,0,0,0,1,0,0,0,0,1,0,0,0,...]


An efficient representation for a 5-gram:

[5,10,235,1253,5521]


What I would like to do is generate such n-gram representations from a large text corpus. Hence, this may easily result in a vocabulary size of hundreds of thousands (depending on potential pre-processing steps including stopword removal, stemming, etc.) and even more distinct n-grams (m).
This could be represented as a matrix of size m x vocab_size.

Subsequently, I would like to reduce the number of rows by clustering similar n-grams together while retaining the contained words. For instance:

[5,7,10,12,15],[5,8,10,15,18] -&gt; [5,7,8,10,12,15,18]


My naive approach would be to apply some traditional clustering algorithm in order to assign each entry in the initial n-gram set to a specific cluster and then perform a union over all the n-grams assigned to a cluster.

1st question: what would be an sensible algorithm for clustering sparse binary representations?
2nd question: how could this be done with a very big data set?
I don't think clustering is the right approach here. You want to merge them automatically, but clustering is too unpredictable for this; you need to manually examine clustering results.

I suggest you look at near duplicate detection instead. You want to merge documents that have a high overlap. There are some interesting - and scalable - algorithma for that. In particular, minhash (and later work) is worth looking at.