0
$\begingroup$

can someone explain how the triangle inequality helps speed up kNN?

I understand the general principle of the triangle inequality, however I don't see how a lower bound on $d(x_1, x_2)$ would help with computation.

Lower bound from: $$d(x_1,x_2) \ge d(x_1,x_3)-d(x_2,x_3)$$

$\endgroup$
0
$\begingroup$

Answering my own question:

assuming another point $x_4$ with $d(x_1,x_4)<d(x_1,x_3)-d(x_2,x_3)$ is known, then we know that $x_2$ is not a newest neighbor, the distance then does not need to be calculated (which can be expensive in high dimensional spaces).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.