Best First $($BF$)$ Algorithm

Pseudocode of BF

algorithm $BF(q)$

$/*$ in the following $H$ is a sorted list where each entry is an MBR

whose sorting key in $H$ is its mindist to $q$;

$p_{\text{b}\text{e}\text{s}\text{t}}$ is a global variable that keeps the NN found so far. $*/$

insert the MBR of the root in $H$

while $||q,p_{\text{b}\text{e}\text{s}\text{t}}||$ is greater than the smallest mindist in $H$

$\frac{?}{{?}^{**}}$ if $p_{\text{b}\text{e}\text{s}\text{t}}=\frac{O}{,}||q,p_{\text{b}\text{e}\text{s}\text{t}}||=\frac{{}^{**}}{?}$

remove from $H$ the MBR $r$ with the smallest mindist

access the child node $u$ of $r$

if $u$ is an intermediate node then

insert all the MBRs in $u$ into $H$

else

if the NN of $q$ in $u$ is closer to $q$ than $p_{\text{b}\text{e}\text{s}\text{t}}$ then

$,p_{\text{b}\text{e}\text{s}\text{t}}=$ the NN of $q$ in $u$

UsiTng BF algorithm, solve the following task:

There is restaurant dataset which consist of $2$ D data points. stored in text file with folllowing data format:

id$\_1$ x$\_1$ y$\_1$

id$\_2$ x$\_2$ y$\_2$

$...$

id $\_$n x$\_$n y$\_$n

each line includes unique id for a data point, and its geographical coordinates $,$ longitude and latitude. FOr an example an entry in the restaurant dataset $"$id$\_1=1$ x$\_1=31\mathrm{.}45$ y$\_1=140\mathrm{.}5"$ precisely indicates the location of a shop, with x $=$ longitutde and y $=$ latitude.

we have $200$ users are interested in finding nearest restaurant. Their locations are provided in a text file formatted identically to datasets:

id$\_1$ x$\_1$ y$\_1$

id$\_2$ x$\_2$ y$\_2$

$...$

id$\_200$ x$\_200$ y$\_200$

use BF algorithm to construct a R Tree for the selected dataset then apply the BF algorithm using the R tree to find the nearest neighbor for each query point.

output shuould display following information in different single text output file:

The id$,$ x and y coordinates of the nearest restaurant

$"$id $=12$ x $=45$ y $=140\mathrm{.}8$ for query $1"$

The total running time for processing all $200$ queries and the average time per query. divide the total running time by $200$