While this question already exists and does talk about a heuristic with the Farthest Point First technique, I would like to approach the problem in a more efficient way. I do agree that this is an NP Hard problem, but the Farthest Point First technique might not be the best here, since I am looking for something more computationally efficient, as I am trying to sample about 250,000 vectors from 1.4 billion vectors.
Is there any specific research out there about this? Has anyone used any machine learning techniques such as K-means clustering or so?
My approach would be to divide the task into
n buckets which each contain
m vectors, where
m = 1.4 billion. Now I can run K-means clustering on each bucket where
n = 250,000. Calibrating between the numbers and distributing between multiple computers may be the best way to approach this problem.