Depth-First Search (DFS)

Starting from the root node, DFS visits the child nodes in a certain order. More specifically, the order is determined by the $mindist$ of each node from the query point $q$ , where $mindist$ is the minimum distance between $q$ and the node's minimum bounding rectangle (MBR). When a leaf node is reached, the objects are retrieved and the list of nearest neighbor candidates is updated. Let $q.dist_k$ be the distance of $k^{th}$ nearest neighbor from $q$ , clearly the algorithm does not need to visit any node $N$ and its child entries if $mindist(N,q)\geq q.dist_k$ .

Figure: An Example of a NN Query on R-tree Index

Fig. (a) illustrates an example of a nearest neighbor query: $a,b,...,h$ are the spatial objects and $q$ is the query point. Fig. (b) shows the corresponding R-tree, including the root, intermediate nodes $1$ and $2$ and leaf nodes $A,B,C$ and $D$ . The algorithm first visits node $1$ because $mindist(1,q)<mindist(2,q)$ . Then, DFS visits node $B$ (because $mindist(B,q)<mindist(A,q)$ ). It computes the $mindist$ of the object $c$ and $d$ in node $B$ and inserts $d$ in the nearest neighbor candidate list $q.kNN$ . DFS next visits the node $A$ but does not find a better candidate than $d$ . Next node visited is $2$ . Since $mindist(C,q)<mindist(D,q)$ , DFS visits the node $C$ and finds object $e$ that is closer to $q$ than $d$ , so it replaces $e$ with $d$ in $q.kNN$ . The next node to be visited is $D$ , DFS prunes it because $mindist(D,q)>mindist(e,q)$ . There is no other node to be visited so DFS reports $e$ as the final answer. Table  shows the nodes in the order they were processed by DFS algorithm.

Table: Depth-First Search

Node in Process	candidate set ($q.kNN$ )	$q.dist_k$
$1$	$\phi$	$\infty$
$B$	$d$	$mindist(d,q)$
$A$	$d$	$mindist(d,q)$
$2$	$d$	$mindist(d,q)$
$C$	$e$	$mindist(e,q)$