Question about the clustering the Binary data.

[chenmc1996]

From my understanding, training IndexBinaryIVF already needs to cluster the data to obtain some centroids.
Then why the faiss.Kmeans doesn't support binary data?
Thanks

[mdouze]

Binary data is converted to float before clustering.
Clustering binary vectors directly (ie. the vector-to-centroid assignment step) could be faster, but it is not implemented.

[chenmc1996]

Thanks for the reply.
Could you please elaborate a bit little more?
I want to perform clustering on my binary data based on hamming distance, But I think the conversion is not very straightforward, Since the Euclidean distance for, e.g., uint8 is not positive correlated to the Hamming distance, e.g., Hamming distance between (10 vs. 00) is equal to (01 vs. 00). but the former one has bigger Euclidean distance?
Or can you suggest how can I implement the clustering on my binary data?

[sef43]

Hi sorry to bump but I would also like to know more about this question. In IndexBinaryIVF I see that there is a binary to float conversion then a indexFlatL2 is used:

faiss/faiss/IndexBinaryIVF.cpp

Lines 251 to 269 in 33c0ba5

	IndexFlatL2 index_tmp(d);
	if (clustering_index && verbose) {
	printf("using clustering_index of dimension %d to do the clustering\n",
	clustering_index->d);
	}
	// LSH codec that is able to convert the binary vectors to floats.
	IndexLSH codec(d, d, false, false);
	clus.train_encoded(
	n, x, &codec, clustering_index ? *clustering_index : index_tmp);
	// convert clusters to binary
	std::unique_ptr<uint8_t[]> x_b(new uint8_t[clus.k * code_size]);
	real_to_binary(d * clus.k, clus.centroids.data(), x_b.get());
	quantizer->add(clus.k, x_b.get());
	quantizer->is_trained = true;

Does this mean that the BinaryIVF index has its clusters created based on the euclidean distance between the binary vectors? and not the hamming distance between them?

[chasingegg]

At the index training stage, binary vectors are converted to float vectors and its centroids are float vectors so we use euclidean distance, when training stage is finished, centroids are converted to binary vectors and start the index assigning stage, assigning is based on the hamming distance between binary vectors.
Also hamming distance == euclidean distance on binary vectors.
In my opinion, binary vectors are converted to float vectors and do the clustering based on float vectors could benefit recall? And hamming distance does not make any sense on float vectors, have to use euclidean distance.