Efficient clustering of sparse binary vectors I'm trying to perform clustering of the data to improve the efficiency of brute-force kNN . The dataset consists of objects described by a large set of binary features, each identified by a 32-bit hash code. Data point can be understood as a 2^32 elements long very sparse binary vector, with bits set to 1 on the positions denoted by hash code of feature. To simplify, each of the data points is being represented as an array of hashes - if we know which of the bits are set to 1, we know which of them are set to 0.

I have a working distance function (mentioned in here) but have difficulties to cluster the dataset in reasonable time.  Because of the binary nature of the data it is impossible to create any kind of mean value based on a collection of datapoints, so k-Centroids is not an option. I tried k-Clustroids but it doesn't converge, hierarchical approaches are too inefficient. Do you happen to know any clustering algorithm that would efficiently handle fixed size dataset, with custom metric calculation method without the need to create any temporary, centroid datapoints?

Many thanks.
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.