This question reminds me of the k-means clustering problem (which is NP-complete). Could an algorithm like that one be used here?

https://en.wikipedia.org/wiki/K-means_clustering

Huh, that sounds like a good idea. This could then be used for deciding which data structure to use.