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
CS Help, Email: tutorcs@163.com
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).
Programming Help, Add QQ: 749389476
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:
Example Datasets
Chipotle Locations Satellite Data Traffic Accident FourSquare
Taxi Trajectory Data Gowalla
Size Attributes
2,629 Coordinates
419,438 Coordinates
2,845,342 Coordinates, Timestamps 38,333 Coordinates, Timestamps 1,703,650 Coordinate Sequences,
Timestamps
6,442,890 Coordinates, Timestamps, Relationships
Difficulty Marks Capped Easy 15
Moderate 17
Moderate 17 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.
浙大学霸代写 加微信 cstutorcs
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 be great-circle distance, which can be computed e.g., by geopandas.)
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.