7
$\begingroup$

Given an undirected graph $G$ with $n$ vertices, $m$ edges, and positive weights on the edges, I am interested in the problem of computing for each vertex the $k$ distinct vertices in $G$ that are closest to it on the shortest-path distances in $G$. There is a solution that follows by modifying Dijkstra, where the running time is $k$ times the running time of the standard Dijkstra. Anybody knows a ref to this result? Should I bother to write this down?

thanks....

Update: I wrote down my algorithm in case anybody is interested... http://sarielhp.org/p/14/k_nn/

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Nice, but why would you need to compute KNN? You can get better statistical and algorithmic performance out of an appropriately regularized 1-NN. $\endgroup$
    – Aryeh
    Apr 5 '15 at 14:19
  • $\begingroup$ I have no clue what "appropriately regularized 1-NN" is. Ref? $\endgroup$
    – Sariel Har-Peled
    Apr 6 '15 at 1:03
  • $\begingroup$ A. Kontorovich, Roi Weiss. A Bayes consistent 1-NN classifier, to appear in AISTATS 2015. dl.dropboxusercontent.com/u/3198145/bayes-consistent-1nn.pdf $\endgroup$
    – Aryeh
    Apr 6 '15 at 14:13
  • $\begingroup$ That was the statistical part. The algorithmic one is here: $\endgroup$
    – Aryeh
    Apr 6 '15 at 14:13
  • 1
    $\begingroup$ Well, you should probably check out section 7 in this paper. sarielhp.org/p/12/kann Naturally, removing points if they are not necessary for answering ANN queries is a natural approach to thin out data... $\endgroup$
    – Sariel Har-Peled
    Apr 6 '15 at 20:58
2
$\begingroup$

In Victor Teixeira de Almeida, Ralf Hartmut Güting: Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases. SAC 2006: 58-62, Teixeira and Güting describe a new storage schema with a set of indexed structures to support an efficient execution of a slightly modified version of the Dijkstra's algorithm.

In the introduction they simply use the reference to the original Dijkstra's paper:

... An obvious modification on Dijkstra's algorithm [reference to the original Dijkstra's 1967 paper] that computes shortest path between objects could be done in order to compute the k-NN using the network space. But, in this case, sepcial storage schemas are necessary in order to efficiently support this algorithm. In this paper, ...

So I think you can use the same approach: if your work is NOT focused on a new variant of a k-NN algorithm you can simply mention it and cite Dijkstra's paper; otherwise you should also include other references on the subject; I think there are many of them because the k-NN problem is important, for example, in navigation systems; googling around I found: Fast Nearest Neighbor Search on Road Networks, Alternative Solutions for Continuous K-NN Queries in Spatial Network Databases, ...

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yeh - I run across the same thing when doing web search. However, since they do not give details, I have no clue what they are referring to. What I am asking for is for a reference that describes how to do the k-NN in detail using Dijkstra, including exact running time analysis - see it is not totally obvious. $\endgroup$
    – Sariel Har-Peled
    Sep 24 '14 at 15:54
0
$\begingroup$

This paper:

Man Lung Yiu, Dimitris Papadias, Nikos Mamoulis, Yufei Tao: Reverse Nearest Neighbors in Large Graphs. IEEE Trans. Knowl. Data Eng. 18(4): 540-553 (2006)

calculates the kNN of each vertex belonging to the target set. The proof can be found on Section 4.1 and algorithm All-NN(k).

Improve this answer
$\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.