> except that in the data science contexts with which I'm familiar we're looking at billions of records among petabytes of data.

At the core of the author’s Show HN is an exact algorithm implementation / port for the all-pair similarity search. One of the steps of an all-pair similarity search, metric K-center, is an NP-complete problem. [1]

So we’ve got an exact algorithm that needs to solve an np-complete problem to produce a result, making it at least as hard.

Any speed increases to such an algorithm in the millions of data points is awesome! If you’ve got billions of data points chances are you can distill it down to millions, and if that’s possible you’d get an exact result. Or you could use a heuristic algorithm, some sort of polynomial-time approximation, which can scale to billions, and still get you a good-enough result.

1 - https://static.googleusercontent.com/media/research.google.c...