Programming Language: Python.

You should implement the R-tree by using the existing libraries provided in the programming

language of your choice (i.e., some standard libraries or the libraries for R-Tree).

1. Source Code:

NOTE: Make sure your code can be run in the standard general programming

environment.

2. Report: the report should include the following:

A detailed description of the main functions in your source code. Please provide

comments for each key part of the program including each function, each

FOR/WHILE loop and each IF statement and each calculation and value

assignment.

• A clear specification of the requirements for executing the code such as, OS

environment, placement of input files, any input parameters, etc.

• A detailed analysis for the construction and search of an R-Tree: Select no less

than 10 data points from the given dataset, and one query from the given queries.

You need to draw figures (including the R-tree structure, the MBRs and the

process of R-Tree establishment) to illustrate the whole process of R-Tree

construction and the R-Tree based search. The search should traverse several

nodes of the tree, and during the construction of the R-Tree, there should be an

overflow and a node splitting.

• The report should also include the screenshots of the running results (e.g., the

average execution time of both sequential-scan and R-Tree based methods.

3. A step-by-step video: The video should clearly introduce the design of the program,

show the process of running the program, show the delivered results and implementing

the R-Tree.