Re:Show HN: All-pair similarity search on millions of sets i...
by algorias on Monday November 19, 2018 @05:48AM
(#18485466)
> 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.
This is not correct. It's very obvious that all-pair similarity search can be solved in O(n^2) calls to the similarity metric, as stated in the readme. So unless the metric itself falls outside P, this problem is easy (but still hard to scale up in practice, of course)
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...