# Ref question: K-nearest neighbours in a graph

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/

• Nice, but why would you need to compute KNN? You can get better statistical and algorithmic performance out of an appropriately regularized 1-NN. – Aryeh Apr 5 '15 at 14:19
• I have no clue what "appropriately regularized 1-NN" is. Ref? – Sariel Har-Peled Apr 6 '15 at 1:03
• A. Kontorovich, Roi Weiss. A Bayes consistent 1-NN classifier, to appear in AISTATS 2015. dl.dropboxusercontent.com/u/3198145/bayes-consistent-1nn.pdf – Aryeh Apr 6 '15 at 14:13
• That was the statistical part. The algorithmic one is here: – Aryeh Apr 6 '15 at 14:13
• 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... – Sariel Har-Peled Apr 6 '15 at 20:58

## 2 Answers

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, ...

• 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. – Sariel Har-Peled Sep 24 '14 at 15:54

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).