2
$\begingroup$

Say we have $x_i, \ldots, x_n \in R ^ D$ with positive, real components and use Jaccard distance

$$d(x_i, x_j) = 1 - \frac{\sum_{d = 1}^D\min(x_i^d, x_j^d)}{\sum_{d = 1}^D\max(x_i^d, x_j^d)}$$

to find $k$ nearest neighbors for every point. I wonder, is it possible to get exact solution (all $k$ neighbors are found) without computing all pairwise distances?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.