Task : Skyline Search:

Dataset: There are three datasets$$city$1,$ city$2,$ and city$3$each representing homes in

the city. These datasets contain $2$D points and are stored in text files formatted as follows:

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

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

$...$

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

Each line in the datasets represents a home, with $$x$$ indicating the cost of the home $($for example, $$500,000)$ and $$y$$ representing its size $($for example, $200$ square meters$).$ The goal is to apply the Skyline Search algorithm to find homes that provide the optimal balance of size and cost. This method helps to filter out properties that are either too costly or too small in comparison to other available options.

Program Design:

Select ONE dataset $($city$1,$ city$2,$ or city$3).$

Implement the following algorithms to assist users in choosing the ideal home based

on two key criteria: cost and size.

$1.$ Sequential Scan Based Method: Identify the skyline by sequentially evaluating whether each node is dominated by any other nodes.

$2.$ Branch and Bound Skyline $($BBS$)$ Algorithm: Construct an R$-$tree for the selected dataset. Implement the BBS algorithm with the R$-$tree to identify the skyline.

$3.$ BBS 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. Implement the BBS algorithm to identify the skyline in each subspace. Finally, obtain the skyline for the entire space through $1$D dominance screening method.

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

$.$ The skyline results for the selected dataset, i$.$e$.,$ sequentially output each point$$s ID$,$ x$-$value, and y$-$value.

$.$ The execution time taken to find the skyline for the selected dataset.