Please provide a step by step solution $-$

Task $1$: Nearest Neighbor Search

$$ Datasets: There are three datasets: Restaurant, Shop, and Parking Datasets. Each dataset consists of $2$D points, stored in a text file with the following format:

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

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

$...$

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

Each line includes a unique ID for a point and its geographical coordinates, longitude and latitude. For example, an entry in the Shop dataset, such as $$id$\_1=1,$ x$\_1=33\mathrm{.}85,$ y$\_1=151\mathrm{.}21$ precisely indicates the location of a shop, with $"$x$"$ representing longitude and

$"$y$"$ representing latitude.

$$ Queries: We have $200$ users interested in finding the nearest facilities. Their locations are provided in a text file formatted identically to the datasets:

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

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

$...$

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

For example, id$\_1=1,$ x$\_1=31\mathrm{.}45,$ y$\_1=150\mathrm{.}44$ indicates a user$$s location.

$$ Program Design:

$$ Select ONE dataset $($Restaurant$,$ Shop, or Parking$).$

$$ Find the nearest facility $($restaurant$,$ shop, or parking lot$)$ for each query using the following algorithms:

$1.$ Sequential Scan Based Method: Calculate the distance between a query point to every point in the selected dataset to find the nearest neighbor.

$2.$ Branch$-$and$-$Bound $($BaB$)$ Algorithm: Construct an R$-$tree for the selected dataset. Then, apply the BaB algorithm using the R$-$tree to find the nearest neighbor for each query point.

$3.$ BaB with Divide$-$and$-$Conquer: Firstly, divide the dataset into two subspaces $($based on X dimension or Y dimension$),$ then construct an R$-$tree for each subspace. Use the BaB algorithm to find the nearest point to the query in each subspace. Finally, compare the distance between the nearest points delivered from each subspace to determine the final nearest neighbor in the entire dataset.

$$ Output: For each algorithm $($Sequential Scan Based, BaB Algorithm, and BaB with Divide$-$and$-$Conquer$),$ display and output the following information in a single txt file:

$$ The ID$,$ x$,$ and y coordinates of the nearest neighbor identified for each query point $($e$.$g$.,$id$=56,$ x$=34\mathrm{.}15,$ y$=149\mathrm{.}21$ for query $1).$

$$ The total running time for processing all $200$ queries and the average time per query $($i$.$e$.,$ divide the total running time by $200).$

Programming Environment:

We highly recommend using Python with only the standard libraries provided by the programming languages, rather than relying on existing R$-$Tree libraries. If you choose to use a different programming language, you must provide detailed instructions on how to configure the programming environment and how to execute the program.