<p>In <a href="http://dl.acm.org/citation.cfm?doid=1141277.1141291" rel="nofollow">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</a>, 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.</p>

<p>In the introduction they simply use the reference to the original Dijkstra's paper:</p>

<p>... An obvious modification on Dijkstra's algorithm 
[<em>reference to the original Dijkstra's 1967 paper</em>] 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, ...</p>

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

CC BY-SA 3.0
2014-09-24T15:54:50.223Z
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
CC BY-SA 3.0
2014-09-24T10:32:21.567Z
2014-09-24T10:39:37.970Z
2014-09-24T10:39:37.970Z
Marzio De Biasi
<p>This paper:</p>

<blockquote>
  <p>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)</p>
</blockquote>

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

CC BY-SA 3.0
2016-06-18T20:46:46.527Z
2016-06-18T20:46:46.527Z
Alexandros
<p>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?</p>

<p>thanks....</p>

<p><strong>Update:</strong> I wrote down my algorithm in case anybody is interested... 
<a href="http://sarielhp.org/p/14/k_nn/" rel="nofollow">http://sarielhp.org/p/14/k_nn/</a></p>

CC BY-SA 3.0
2015-04-05T14:19:59.367Z
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
CC BY-SA 3.0
2015-04-06T01:03:07.950Z
I have no clue what "appropriately regularized 1-NN" is. Ref?
Sariel Har-Peled
CC BY-SA 3.0
2015-04-06T14:13:20.437Z
A. Kontorovich, Roi Weiss. A Bayes consistent 1-NN classifier, to appear in AISTATS 2015. https://dl.dropboxusercontent.com/u/3198145/bayes-consistent-1nn.pdf
Aryeh
CC BY-SA 3.0
2015-04-06T14:13:44.813Z
That was the statistical part. The algorithmic one is here:
Aryeh
CC BY-SA 3.0
2015-04-06T14:14:03.027Z
L. Gottlieb, A. Kontorovich, P. Nisnevitch. Near-optimal sample compression for nearest neighbors, NIPS 2014.
http://arxiv.org/pdf/1404.3368v3.pdf
Aryeh
CC BY-SA 3.0
2015-04-06T20:58:26.800Z
Well, you should probably check out section 7 in this paper. http://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
CC BY-SA 3.0
2015-04-06T23:14:52.250Z
Interesting. Do these results extend to doubling spaces?
Aryeh
CC BY-SA 3.0
2015-04-06T23:45:48.320Z
Some of the stuff do...
Sariel Har-Peled
<reference-request><shortest-path>
Ref question: K-nearest neighbours in a graph
Sariel Har-Peled
# Ref question: K-nearest neighbours in a graph

(Asked by: username_0 on 2014-09-24)

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/>

**Tags:** reference-request, shortest-path
> **Comments:**
> **username_1**: Nice, but why would you need to compute KNN? You can get better statistical and algorithmic performance out of an appropriately regularized 1-NN.  
> **username_0**: I have no clue what "appropriately regularized 1-NN" is. Ref?  
> **username_1**: A. Kontorovich, Roi Weiss. A Bayes consistent 1-NN classifier, to appear in AISTATS 2015. https://dl.dropboxusercontent.com/u/3198145/bayes-consistent-1nn.pdf  
> **username_1**: That was the statistical part. The algorithmic one is here:  
> **username_1**: L. Gottlieb, A. Kontorovich, P. Nisnevitch. Near-optimal sample compression for nearest neighbors, NIPS 2014. http://arxiv.org/pdf/1404.3368v3.pdf  
> **username_0**: Well, you should probably check out section 7 in this paper. http://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...  
> **username_1**: Interesting. Do these results extend to doubling spaces?  
> **username_0**: Some of the stuff do...  

---

## 2 answers

### Answer by username_2 on 2014-09-24. Score: 2

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](http://dl.acm.org/citation.cfm?doid=1141277.1141291), 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, ...

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2016-06-18. Score: 0

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


---

