2
$\begingroup$

So there are many well known algorithms for approximate nearest neighbor on the $\ell_1$ distance. My question is, what about the weighted version of the problem (where the weights are specified along with each query). Is there anything known in the research literature already, or is it a trivial extension of established techniques?

More rigorously, the classical nearest neighbor problem is given point set $P$ and query point $q$, find $\text{argmin}_{p \in P} \sum_i | p_i - q_i |$.

A weighted nearest neighbor problem would be, given point set $P$, query point $q$ and weight vector $w$ s.t $\sum_i w_i = 1$ and $w_i \geq 0, \forall i$., find $\text{argmin}_{p \in P} \sum_i w_i | p_i - q_i |$.

Obviously one can do a linear scan for each specified $w$ and $q$, but that seems heavily redundant. So I was just curious if this has already been solved or is a trivial reduction.

The exact version of this is generally hard, so I'd expect the approximation version of this to be more studied or known.

Although the application I have currently is a specific one, its easy to come up with scenarios where a weighted $\ell_1$ distance is reasonable. For instance, say the points correspond to sets of features and the user decides for certain queries they want to accord more importance to specific target dimensions.

Having thought about this some more, if you fixed $q$ to be $0$ and varied $w$, then this problem becomes finding the minimum dot product in $P$ with $w$. As such its at least as hard as MIPS (maximum inner product search). Whether its harder is a more open question.

$\endgroup$
  • 1
    $\begingroup$ 1. Where you write $||.||$, do you really mean $|.|$? 2. Have you considered mapping $p_i \mapsto p'_i = w_i p_i$ and $q_i \mapsto q'_i = w_i q_i$ and then doing the query on $P',q'$? $\endgroup$ – D.W. May 4 '16 at 19:05
  • $\begingroup$ I made the correction, that I intended $|.|$, and not $\|. \|$. Thanks for the catch! As for the solution you proposed, one could map $q_i \to q_i'$ as you suggest, but recall that $w$ is given at query time. As such you cant map $P \to P'$ the same way without doing a linear scan. $\endgroup$ – Amir May 5 '16 at 1:10

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.