Best-First Search (BFS)

BFS uses a priority queue to store the entries to be explored during the search. The entries in priority queue are sorted by their $mindist$ from $q$ . For each popped entry $e$ , all its child are pushed into the queue if $e$ is a node. If $e$ is a leaf, all the objects it contains are considered and the candidate set $q.kNN$ and $q.dist_k$ is updated, accordingly. The algorithm stops as soon as the next popped entry has $mindist$ greater than $q.dist_k$

Consider the same example of Fig. . BFS inserts nodes $1$ and $2$ in queue. The node $1$ is popped first and its child entries $A$ and $B$ are inserted in the priority queue $PQ$ which becomes $PQ=$ {$2$ ,$B$ ,$A$ }. Since $2$ has the smallest $mindist$ , it is popped next and its child entries $C$ and $D$ are inserted in the queue ($PQ=$ {$C$ ,$B$ ,$A$ ,$D$ }). The next entry is $C$ , the object $e$ is inserted in candidate set $q.kNN$ and the $q.dist_k$ is updated to $mindist(e,q)$ . Algorithm stops because the next entry in queue $B$ has $mindist$ greater than $mindist(e,q)$ . Table  shows the nodes in the order they were processed by DFS algorithm.

Table: Best-First Search

Priority Queue	candidate set ($q.kNN$ )	$q.dist_k$
$1,2$	$\phi$	$\infty$
$2,B,A$	$\phi$	$\infty$
$C,B,A,D$	$\phi$	$\infty$
$B,A,D$	$e$	$mindist(e,q)$