INFS4205/7205 Advanced Techniques for High Dimensional Data Semester 1, 2023

All assignments should be submitted to the UQ Blackboard. If any assignment fails to be submitted appropriately before the due date, late penalties will be applied as detailed in the ECP. It is your own responsibility to ensure your submission is successful on time. Email submission will not be accepted.

Updates (v1)

Clarification on number of algorithms to implement .

•    You need to implement at least three different algorithms in total.

•    For each of the query task, you need to implement at least two different algorithms so you can make comparisons between different methods for the same query task.

•    One algorithm (e.g., R-Tree) can be implemented for multiple tasks if applicable.

•    For those students who complete more than two methods for each query task, you will get bonus marks for both Completeness and Innovation.

•    Linear scan as a basic baseline method also counts.

Clarification on Correctness.

•    You need to test different cases for each query task to prove the correctness of your methods.

•    For example, to test the query task: “find all data points in a given rectangular area and within a  certain  time  window”, you  need  to test  different  rectangular  areas  and  different  time windows. You need to make sure for all cases, your algorithms return the same results as the DBMS .

Overview

The project consists of two sections (1) Implementation and (2) Report. In this assignment, you are asked to implement a set of query scenarios utilising spatial / spatial-temporal data as well as computational geometry algorithms wherever suitable. You are required to find spatial datasets that are suitable for this project and implement at least three appropriate algorithms (e.g., k-d tree, R tree indexing). You need to construct spatial DBMS (e.g., PostgreSQL, Oracle, MySQL) to validate the correctness of your implementation.  Finally, you need to present your problem statement, methodology, outcomes, and analysis in the project report. You will need to present your findings in a clear and concise manner, with a focus on the insights gained from the project.

This  assignment  is  designed  to  assess  your  ability  to  apply  advanced  techniques  for   high dimensional data manipulation to solve real-world problems. This is an individual assignment. The completion of the assignment should be based on your own design.

Language requirements: You are allowed to use any programming languages (e.g., Python or Java) for implementing the project. You are also allowed to use existing libraries (citation required).

Implementation [10 marks]

1.    Once you have determined the datasets, you need to conceptualize at least five query tasks from the real world . Some example query tasks are listed below:

a.   find all data points in a given rectangular area and within a certain time window .

b.   find all data points within certain distance to a trajectory emerging on the same day .

c .   find k nearest neighbours (data points) of a given trajectory for a given date.

d.   find the skyline data points.

e.   find the trajectory that is shortest and fastest from given data point to another.

f.    find the trajectory that is most similar to a given trajectory .

(Note: the distance should begreat-circle distance, which can be computed e.g., bygeopandas.)

2.   You should implement at least three algorithms (e.g., k-d tree, R-tree) taught in this course to solve the query tasks you defined . You are encouraged to improve the taught methods with      your own ideas or/and try novel methods proposed in recent research literature.

3.   You need to design and build a spatial(-temporal) database for the selected datasets, then write SQL code for each query task you proposed and verify the correctness of your algorithm by comparing the ground truth results returned by spatial DBMS and the results returned by   your implemented algorithms.

4.   You need to use fair and reasonable metrics to evaluate the various methods you implement.  For each query task, you need to compare e.g., the time cost, memory cost, and I/O cost of the system, when a) building the index and b) executing the query .

5.   You must upload your source code for both a) algorithm implementation and b) database

construction and query, otherwise, no marks will be given for this section.

The marking criteria is summarized as follows:

Completeness [4 marks]: The selected high-dimensional database was adequately processed and cleaned. At least three algorithms taught in this course should be implemented, or methods from recent scientific research can be reproduced. At least five query tasks from real-world scenarios  need to be given to test your implementation. The testing scenarios should cover different types    of spatial query tasks and make full use of the special attributes (e.g., sequence, relationships) of  datasets, reflecting the completeness of the methods. Evaluating and comparing implemented       methods should be in a comprehensive and fair manner.

Correctness [4 marks]: Your implementation correctly addresses the query tasks and is validated using a spatial DBMS . You need to show the SQL code used for generating the ground truth query results to validate the correctness of the implemented algorithms. The implemented code or          program runs without errors and bugs and all the functionalities and features work as intended. The code is well-structured, easy to understand and maintain, and the follows good programming practices and standards .

Effectiveness and Innovation [3 marks]: The project should present a unique, innovative and improved approach to solving a problem or meeting a need, rather than purely utilizing existing libraries or online code.

Report [10 marks]

This report should cogently (1) introduce the task or problem being proposed and elucidate its practical application value in industry or its potential contribution to scientific research (e.g., why R tree falls short in facilitating fast query and how it can be enhanced . (2) Then, you need to explicate the approach employed in a precise and explicit manner, encompassing the overall algorithm, the technical intricacies of each step or module, as well as any improvements or innovations you made. (3) You need to show the correctness (precision, recall, F1-score, etc .) of the results returned by the implemented method for different query tasks, compared to the ground truth query results.  (4) The report must also address the reasonable verification of method performance (e.g., time cost, memory cost, and I/O cost) or equitable comparison with alternative methods. (5) Lastly, experimental results must be comprehensively presented by tables, plots, and/or with some visualization tools. The results should be analysed deeply to unearth insightful findings.

The report must not exceed four pages in length and should be written in given IEEE doc or latex template. The marking criteria is summarized as follows:

Definition and Scope [2 marks]: The definition of a substantial and significant topic, problem     and/or hypothesis (including statement of purpose and relevance) and scope (including context, boundaries, and assumptions) should be clearly presented.

Methodology and Algorithm [3 marks]: The methodology should be described in a systematic and logical way . You can enrich your descriptions by drawing detailed flowcharts and/or using rigorous mathematical formulas.

Results Analysis [3 marks]: The project results are complete and comprehensively presented and analysed, using tables, plots, and/or some visualization tools. If the source code is not uploaded,   no marks will be given for this criterion.

Writing and Presentation [2 marks]: The report should be written in excellent logical structure, physical layout, scientific and technical style, with no spelling mistakes or grammar errors. You need to appropriate reference to a correctly formatted bibliography .