You will be given a dataset which contains 2D points. The dataset will be provided in a text file.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

[Dataset]: You will be given a dataset that contains 2D points.  The dataset will be provided  in a text file as the following format:

n

id 1 x  1 y 1

id 2 x  2 y 2

...

id n x n y  n

Specifically, the first line gives the number of points in the dataset. Then, every subsequent line gives a point’s id, x-,  and y-coordinates.  Your program should build an R-tree in memory from the dataset.

[Range Query]: You will be given a set of 100 range queries in a text file whose format is:

 

x  1 x’  1 y  1 y’ 1

x  2 x’  2 y  2 y’ 2

...

x 100 x’ 100 y 100 y’ 100

 

That is, each line specifies a query whose rectangle is [x, x′] [y, y′]. Then, we will measure its  query efficiency as follows.

You should output to a disk file:

Firstly, your program should display the time of answering queries by reading the entire dataset sequentially. This time serves as the sequential-scan benchmark to be compared with the cost of your query algorithms that leverage the R-tree.

Secondly, display the number of points returned by each query-note: we need only the number of points retrieved , instead of the details of those points.

Thirdly, display the total running time of answering all the 100 queries, and the average time of each query (i.e., divide the total running time by 100).

Programming Language]: Python, Java, C++ (including variants like C, C#, ...), or any other

 

language approved by the instructor. You can 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).

 

[Deliverables]: Your submission includes the following components:

 

1. Source Code: The code you have developed yourself. Make sure your code can be run in the standard general programming

2. Report: Your report should include the following:

   • A brief description of the main functions in your source code;

A clear specification of the requirements for executing your code such as, OS environ- ment, placement of input files, any input parameters, etc.

3. Zip all your code and report into a single file, and name the file in the following format:

yourstudentid surname.zip.

Marking: Your total mark earned for this assignment is based on:

•    [Queries: 60 marks]

• Correctness: 50

[Sequential-Scan Based Method (10 marks)]: If your program correctly an- swers m (out of 100) queries by reading the entire dataset (reading all the data points) sequentially, you get 10 · (m/100) marks for this part.

∗ [R-Tree Based Method (40 marks)]: If your program correctly answers m (out of 100) queries by searching the R-Tree, you get 40 · (m/100) marks for this part.

• Efficiency: 10 marks. If the average query time is at least 5 times faster than sequential scan, you get 10 marks for this part.  If at least 2  times  faster (but less than  5 times), you get 5 If less than 2 times faster, no marks.

•    [The Report: 40 marks]

• Function Description: 30   If your report includes a clear description of all  the functions in your source code, you get 30 marks. If only part of your functions is introduced, you will be given the marks based on the proportion of the correct answers.

• Requirement Description: 10 If your report includes a clear description of the requirements for executing your code such as, OS environment, placement of input files, any input parameters, etc, and your report includes the screenshots of the  run-  ning results (e.g., the average execution time of both sequential-scan and R-Tree based methods, etc.), you get 10 marks.

 

•    [Bonus: 10 marks]

• Implementing the R-Tree by Using Standard Libraries Only (5 marks). S- tudents are encouraged to implement the R-Tree by  using standard libraries provided    by the program languages rather than using the existing R-Tree If you can correctly implement the R-Tree  without the help of the existing R-Tree libraries,  you  get 5 marks as the bonus.

• Analysing the Working of R-Tree: (5 marks). In addition to coding, students are encouraged to provide a high-quality report that contains a detailed analysis of the working of R-Tree. You need to select no less than 10 data points from the given dataset, and one query from the given queries. Then, if you can clearly and correctly analyse the process of the R-Tree construction and the query process (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), you get 5 marks as the bonus.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of