1
$\begingroup$

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 n x m = 1.4 billion. Now I can run K-means clustering on each bucket where k x n = 250,000. Calibrating between the numbers and distributing between multiple computers may be the best way to approach this problem.

Improve this question
$\endgroup$
8
  • $\begingroup$ reservoir sampling would imply sampling uniformly randomly right? I want n vectors that are the most "diverse", which is not uniform sampling $\endgroup$
    – SDG
    Jul 28, 2021 at 7:48
  • $\begingroup$ No problem! Any chance you know how to approach this issue? $\endgroup$
    – SDG
    Jul 28, 2021 at 7:52
  • $\begingroup$ What does your data look like? Contrasting with D.Ws answer, there are very good clique finding algorithms and heuristics, especially if your graph is not too dense. $\endgroup$
    – Juho
    Jul 28, 2021 at 7:59
  • $\begingroup$ @Juho 1.4 billion vectors of length 20 and floats, and I would like to find the 250,000 most unique vectors $\endgroup$
    – SDG
    Jul 28, 2021 at 8:09
  • $\begingroup$ Right, I meant what does it look like with respect to the graph you would construct based on it? Are the vectors mostly close to each other, ie. would the graph be very dense for a choice of the threshold t? $\endgroup$
    – Juho
    Jul 28, 2021 at 8:10

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.