INFS4205/INFS7205 Advanced Techniques for High Dimensional Data - Individual Project: Query Algorithms for Spatial / spatial-temporal data
INFS4205/7205 Advanced Techniques for High Dimensional Data Semester 1, 2023 1 INFS4205/7205 Individual Project Due: 16:00 AEST on 19 May 2023 Weighting: 20% 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 di fferent method s 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 area s and different time window s. 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 spati al 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 assig nment. The completion of the assignment should be based on your own design. Language requirement s: You are allowed to use any programming languages (e.g., Python or Jav a) for implementing the project. You are also allowed to use existing libraries (cit ation required).
Datasets Selection Any open -sourced dataset is allowed as long as it fits topic about spatial / spatial -temporal data manipulation . We provide some example datasets for reference , including but not limited to: Exam ple Datasets Size Attributes Difficulty Marks Capped Chipotle Locations 2,629 Coordinates Easy 15 Satellite Data 419,438 Coordinates Easy 15 Traffic Accident 2,845,342 Coordinates, Timestamps Moderate 17 FourSquare 38,333 Coordinates, Timestamps Moderate 17 Taxi Trajectory Data 1,703,650 Coordinate Sequenc es, Timestamps Hard 20 Gowalla 6,442,890 Coordinates, Timestamps, Relationships Hard 20
Note that , for the datasets you found but not listed above, we evaluate the difficulty considering both datasets size and attributes . For ‘moderate’ datasets, the size is greater than 10, 000 and attributes contain at least coordinates and timestamps. For ‘hard’ datasets , the datasets size is greater than 100, 000 and attributes should be more complicated and informative . Marks Capped (as shown in the last column) : If you choose to work with the easy dataset, the maximum marks you can obtain for this project is 15. This means that any marks beyond 15 will not be counted towards your final grade.
Implementation [10 marks ]
- Once you have determined the datasets, you need to conceptualize at least five quer y tasks from the real world . Some example quer y tasks are listed below: a. find all data points in a given rectangular area and within a certain time window . b. find all data poin ts within certain distance to a trajectory emerging on the same day . c. find k neare st 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 be great -circle distance , which can be computed e.g., by geopandas .)
- You should implement at least three algori thms (e.g., k -d tree, R -tree) taught in this course to solve the quer y 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 .
- You need to design and build a spatial (-temporal) database for the selected datasets, then write SQL code for each query task you propose d and verify the correctness of your algorithm by comparing the ground truth results returned by spatial DBMS and the r esults returned by your implemented algorithms.
- You need to use fair and reasonable metric s 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) buildi ng the index and b) executing the query .
- 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 m arking criteria is summarized as follow s: 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 reprodu ced. 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 , reflect ing 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 a ll the functionalities and features wo rk 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 . INFS4205/7205 Advanced Techniques for High Dimensional Data Semester 1, 2023 5 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 over all 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 q uery 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, experimen tal 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 m ethodology should be describe d 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 analyse d, 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 e xcellent logical structure, physical layout , scientif ic and technical style , with n o spelling mistakes or grammar errors. You need to a ppropriate referenc e to a correctly formatted bibliography.
INFS4205/7205 Advanced Techniques for High Dimensional Data Semester 1, 2023 6 Submission You are required to submit all following files. − A compressed file (zip) consisting of all source code : o algorithm implementation in any language, o a SQL file including the database construction, manipulation, and task queries . − A 4-page project report in PDF format . Only your submitted version will be marked. A penalty will be applied to the late submission according to the ECP.
Use of AI Tool Artificial Intelligence (AI) provides emerging tools that may support students in completing this assessment task. Students may appropriately use AI in completing this assessment task. Students must clearly reference any use of AI in each instance. A failure to reference AI use may constitute student misconduct under the Student Code of Conduct. This task has been designed to be challenging, authentic and complex. Whilst students may use AI technologies, successful completion of assessment in this course will require students to critically engage in specific contexts and tasks for which artificial intelligence will provide only limited support and guidance. A failure to reference AI use ma y constitute student misconduct under the Student Code of Conduct. To pass this assessment, students are required to demonstrate detailed comprehension of their written submission independent of AI tools . When you use g enerative AI (ChatGPT) in this assessment , you should: − Do not provide any private information when using these tools. − Verify any information provided by generative AI tools with credible sources and check for missing information. − Acknowledge any generative tools that you use for your assignments or work and how you used them. For example, include the name, model or version, date used and how you used it in your assignment or work.
Useful Tools − Visualization spatial ( -temporal) data over google maps : [link ] − Import CSV file into PostgreSQL table : [link ]
