3
$\begingroup$

I remember reading a paper about finding k nearest neighbors for all N multi-dimensional objects in the set.

I've tries to find it again many times, but have failed so far.

The algorithm was as follows:

  1. Each object is assigned a sorted queue of nears neighbors (maximum size is k). Let's assume that $k < log(N)$
  2. Each time you calculate $distance(A, B)$ try to add A into B's neighbor list and vise versa.
  3. Choose $log(N)$ support objects (say, first $log(N)$ objects out of $N$). (Or maybe that was $sqrt(N)$)
  4. For each support, build the distance-based index containing all N objects
  5. After the index construction, every object has a candidate list of k nearest neighbors. All real nearest neighbors are not further than the furthest neighbor in the candidate list - candidate neighbor radius.
  6. For each point we use triangle inequality and current neighbor radius to constrain the distances between a candidate point and the support points: $|dist(candidate_i, support_j) - dist(point, support_j)| <= radius$. We efficiently extract the candidates that fall in radius-based ranges for all support points.
  7. We calculate the distances for those candidates and update the nearest-neighbor lists for both the current point and the candidate points.
  8. As we process more points, the neighbor lists become "tighter" - the radius, the distance to the furthest neighbor decreases with each update of the list.
  9. Tighter constraints mean that the candidate lists become smaller and smaller after each processed point and leading to total run time of $N*log(N)$.

So, why do I need the paper again? First of all, several people have asked me for it and I was surprised I cannot find it again. More importantly, it did not work well for me. This might be caused by a bad choice of the support objects. I remember nothing about the selection process.

$\endgroup$
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/83021/755, stackoverflow.com/q/46944749/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Oct 26 '17 at 16:24
  • $\begingroup$ @D.W. Sorry for cross-posting. I posted it at Computer Science, because it looks like computer science. Then I've remembered that there is a high probability I saw the paper linked somewhere at SO. $\endgroup$ – Ark-kun Oct 26 '17 at 21:23
  • $\begingroup$ What do you mean by multi-dimensional (3-4 or higher)? Do you remember parameter $d$ in the runtime? I have some suspicions: similar, fuzzy with support. performant, but not that similar, similar. $\endgroup$ – Evil Oct 27 '17 at 3:24
  • $\begingroup$ @Evil My d is bug. 50-100-300-1000 dimensions. $d$? (number of dimensions?) very likely. Now that I think of it, the runtime I've stated might be very wrong. All I really remember is that it was sub-quadratic (in relation to N). $\endgroup$ – Ark-kun Oct 27 '17 at 7:36
  • $\begingroup$ @Evil Finally found my algorithm by deep searching "all nearest neighbors index radius" in Google. Maybe that's not THE paper I read, but the algorithm matches exactly. Thank you for the other papers too. cs.stackexchange.com/a/83073/79338 $\endgroup$ – Ark-kun Oct 27 '17 at 7:39
2
$\begingroup$

Found the paper finally. Not sure I've read exactly the same paper (maybe I read some SO or SE answer or some other paper that inspired/was inspired by this paper). Nethertheless, the algorithm is exactly the same.

A Fast Algorithm for the All k Nearest Neighbors Problem in General Metric Spaces by Edgar Chávez and Karina Figueroa and Gonzalo Navarro. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.9299 http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A580FE7BF3251BC23DB793E3B1DFDF64?doi=10.1.1.21.9299&rep=rep1&type=pdf

Algorithm description

$\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.