Differences

This shows you the differences between two versions of the page.

--- teaching:projh402 [2020/10/01 12:35]
mahmsakr [Geospatial Trajectory Data Cleaning]
+++ teaching:projh402 [2020/10/03 14:11]
ezimanyi [K-D-Tree Indexes for MobilityDB]
@@ Line 3: / Line 3: @@
 ===== Course objective =====
-The course PROJ-H-402 is managed by Dr. Mauro Birattari. Please refer to the course description page http://iridia.ulb.ac.be/proj-h-402/index.php/Main_Page for the rules concerning the project.  What follows is a list of project proposals supervised by academic members of CoDE.
+The course PROJ-H-402 is managed by Dr. Mauro Birattari. Please refer to the course description page http://iridia.ulb.ac.be/proj-h-402/index.php/Main_Page for the rules concerning the project.  What follows is a list of project proposals supervised by academic members of the WIT laboratory.
 ===== Projects in Mobility Databases =====
@@ Line 20: / Line 20: @@
-===== Visualization Moving Objects on the Web =====
+===== Visualization of Moving Objects on the Web =====
-<TBD>
+There are several open source platforms for publishing spatial data and interactive mapping applications to the web. Two populars ones are [[https://mapserver.org/|MapServer]] and [[http://geoserver.org/|GeoServer]], which are written, respectively, in C and in Java.
+Newer platforms exists, such as [[https://kepler.gl/|kepler.gl]], which were designed for handling large-scale data sets.
+However, these platforms are used for static spatial data and are unable to cope with moving objects. The goal of the project is to extend one of these platforms with spatio-temporal data types in order to be able to display animated maps.
 ===== Implementing TSBS on MobilityDB =====
@@ Line 64: / Line 66: @@
 ===== Geospatial Trajectory Similarity Measure =====
+One of the main functions for a wide range of application domains is to measure the  similarity between two  moving objects' trajectories. This is desirable for similarity-based retrieval, classification, clustering and  other querying and mining tasks over moving objects' data. The  existing movement similarity measures can be classified into  two classes: (1) spatial similarity that focuses on finding trajectories with  similar geometric shapes, ignoring the temporal dimension; and (2) spatio-temporal similarity that takes into account both the spatial and the temporal dimensions of movement data.
+The goal of this project is to survey and to prototype in MobilityDB the state of art methods in trajectory similarity. Since it is a complex problem, these outcomes should serve as a base for a thesis project to propose effective and efficient trajectory similarity measures.
 ===== Spatiotemporal k-Nearest Neighbour (kNN) Queries =====
+An example of continuous kNN is when the GPS device of the vehicle initiates a query
+to find the three closest gas stations to the vehicle at any time instant during its trip from source to destination. According to the location of the vehicle, the set of three nearest gas stations can change. The result is thus a set of intervals, where very interval is associated with a set of three gas stations. The challenge in this type of query is to find an efficient incremental way of evaluation.
+The goal of the project is to survey the state of art in continuous kNN queries, and to prototype selected methods in MobilityDB. Since it is a complex problem, these outcomes should serve as a base for a more elaborate thesis project.
+===== K-D-Tree Indexes for MobilityDB =====
+Indexes are essential in databases for quickly locating data without having to search every row in a table every time a database table is accessed. Thus, an index is an auxiliary data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index. PostgreSQL provides [[https://habr.com/ru/company/postgrespro/blog/441962/|multiple types of indexes]] for various data types.
+In MobilityDB two types of indexes has been implemented, [[https://habr.com/en/company/postgrespro/blog/444742/|GiST]] and [[https://habr.com/ru/company/postgrespro/blog/446624/||SP-GiST]]. More precisely, in PostgreSQL, these types of indexes are frameworks for developing multiple types of indexes. Concerning SP-GiST indexes, in MobilityDB we have developed 4-dimensional quad-trees where the dimensions are X, Y, and possibly Z for the spatial dimension and T for the time dimension. An alternative approach would be to use [[https://en.wikipedia.org/wiki/K-d_tree|K-D Trees]]. K-D trees can be implemented in PostgreSQL using the SP-GiST framework and an example [[https://github.com/postgres/postgres/blob/master/src/backend/access/spgist/spgkdtreeproc.c|implementation]] for simple [[https://www.postgresql.org/docs/current/datatype-geometric.html|geometric types]] exist. The goal of the project is to implement K-D indexes for MobilityDB and perform a benchmark comparison between K-D trees and the existing 4-dimensional quad-trees.