Efficient clustering of sparse binary vectors
You can efficiently implement e.g. Euclidean distance or Cosine on sparse data (iterate over nonzero values only!). Then you can use e.g. Hierarchical clustering.

But also consider frequent itemset mining. Usually, on sparse binary data, frequent itemsets are better than clusters.