|
Hello, I was thinking about scaling(distributing) Nearest Neighbor Search algorithm (simple exhaustive search). Assumption is that you have N nodes, S samples stored in database and request dispatcher before nodes. There could be two aproaches:
I was thinking which approach could handle more requests per second, which has lower latency, which is better ;) |
|
At first approximation 1 favors throughput & 2 favors latency, since 1 minimizes the amount of communication while 2 parallelizes the search, assuming that takes longer than the communication. However, it all depends on a number of factors: how long does it take for a complete sequential search? how many nodes? what is the network bandwidth & latency? how reliable is your network? how many nearest neighbors are you looking for? must the result be exact be exact or is some degree of approximation acceptable? A simple counter example to my answer above is if you use a lot of nodes & your network is flaky, and you really need exact NNs, then 2 can have poor latency, since it will have the latency of the slowest node and with enough nodes it is likely at least one will flake out. Depending on what the factors are in your case you could try an intermediate approach where you have overlap between nodes and you send the query to each node, but not wait for all to respond, just when you have received enough responses to be sufficiently confident you have seen the best result. Alternatively you can also not send responses to all only to be confident enough that you have covered all your items. All that depends on being able to tolerate some degree of approximation, though. |
|
Approach 2 is certainly going to be better than 1. You are distributing load and parallelizing much better in the second case. |
