This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
teaching:projh402 [2020/10/12 19:11] ezimanyi [Map-matching as a Service] |
teaching:projh402 [2021/09/18 18:34] ezimanyi [Dynamic Time Warping for Trajectories] |
||
---|---|---|---|
Line 3: | Line 3: | ||
===== Course objective ===== | ===== 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 the WIT laboratory. | + | The course PROJ-H-402 is managed by Dr. Mauro Birattari. Please refer to the [[http://iridia.ulb.ac.be/wiki/PROJ-H-402_-_Computing_Project:_Rules|course description 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 ===== | ===== Projects in Mobility Databases ===== | ||
Line 22: | Line 22: | ||
===== Visualization of Moving Objects on the Web ===== | ===== Visualization of Moving Objects on the Web ===== | ||
- | 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. | + | There are several open source platforms for publishing spatial data and interactive mapping applications to the web. Two popular 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. | 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. | ||
+ | {{:teaching:trips2.gif?direct|}} | ||
+ | |||
+ | Animated visualization of car trajectories | ||
+ | |||
+ | ===== MobilityDB on Google Cloud Platform ===== | ||
+ | |||
+ | Deploying MobilityDB on the cloud enables the processing of the large amounts of mobility data that are continuously being generated nowadays. MobilityDB has been already deployed on Azure and on AWS. This project continue this effort on the Google Cloud Platform. The objective is to build on the similarities and differences of the three cloud platforms for defining a foundation for mobility data management on the cloud. | ||
+ | |||
+ | Links: | ||
+ | * [[https://github.com/MobilityDB/MobilityDB-Azure|MobilityDB-Azure]] | ||
+ | * [[https://github.com/MobilityDB/MobilityDB-AWS|MobilityDB-AWS]] | ||
+ | |||
+ | **Status**: taken | ||
===== Implementing TSBS on MobilityDB ===== | ===== Implementing TSBS on MobilityDB ===== | ||
Line 35: | Line 47: | ||
The project consists in implementing a multidimensional generalization of the time_bucket function that allows the user to partition the spatial and/or temporal domain of a table in units (or tiles) that can be used for aggregating data. Then, the project consists of performing a benchmark comparison of TimescaleDB and MobilityDB. | The project consists in implementing a multidimensional generalization of the time_bucket function that allows the user to partition the spatial and/or temporal domain of a table in units (or tiles) that can be used for aggregating data. Then, the project consists of performing a benchmark comparison of TimescaleDB and MobilityDB. | ||
+ | **Status**: taken | ||
- | ===== Distributed Moving Object Database on Amazon AWS ===== | ||
- | A distributed database is an architecture in which multiple database instances on different machines are integrate in order to form a single database server. Both the data and the queries are then distributed over these database instances. This architecture is effective in deploying big databases on a cloud platform. | ||
- | MobilityDB is engineered as an extension of PostgreSQL. AWS supports PostgreSQL databases in [[https://aws.amazon.com/rds/postgresql/|Amazon RDS]] for PostgreSQL and in [[https://aws.amazon.com/rds/aurora/postgresql-features/|Amazon Aurora]]. The goal of this project is to integrate MobilityDB with these products. The key outcomes are a comprehensive assessment of which MOD API can/cannot be distributed, and an assessment of the performance gain. These outcomes should serve as a base for a thesis project to achieve effective integration. | ||
- | |||
- | ===== Distributed Moving Object Database on MS Azure ===== | ||
- | A distributed database is an architecture in which multiple database instances on different machines are integrate in order to form a single database server. Both the data and the queries are then distributed over these database instances. This architecture is effective in deploying big databases on a cloud platform. | ||
- | |||
- | MobilityDB is engineered as an extension of PostgreSQL. MS Azure supports distributed PostgreSQL databases using [[https://www.citusdata.com/|Citus]]. We have made successful tests for integrating MobilityDB and Citus on a local cluster. The goal of this project is to repeat this work on MS Azureintegrate MobilityDB with these products. The key outcomes are a comprehensive assessment of which MOD API can/cannot be distributed, and an assessment of the performance gain. These outcomes should serve as a base for a thesis project to achieve effective integration. | ||
===== Map-matching as a Service ===== | ===== Map-matching as a Service ===== | ||
GPS location tracks typically contain errors, as the GPS points will normally be some meters away from the true position. If we know that the movement happened on a street network, e.g., a bus or a car, then we can correct this back by putting the points on the street. Luckily there are Algorithms for this, called Map-Matching. There are also a handful of open source systems that do map matching. It remains however difficult to end users to use them, because they involve non-trivial installation and configuration effort. Preparing the base map, which will be used in the matching is also an issue to users. | GPS location tracks typically contain errors, as the GPS points will normally be some meters away from the true position. If we know that the movement happened on a street network, e.g., a bus or a car, then we can correct this back by putting the points on the street. Luckily there are Algorithms for this, called Map-Matching. There are also a handful of open source systems that do map matching. It remains however difficult to end users to use them, because they involve non-trivial installation and configuration effort. Preparing the base map, which will be used in the matching is also an issue to users. | ||
- | {{:teaching:original.png?direct&400|}} {{:teaching:mapmatched.png?400|}} | + | {{:teaching:original.png?direct&400|}} |
+ | Original trajectory | ||
- | The goal of this project is to build an architecture for a Map-Matching service. The challanges are that the GPS data arrives in different formats, and that Map-Matching is a time consuming Algorithm. This architecture should thus allow different input formats, and should be able to automatically scale according to the request rate. Another key outcome of this project is to compare the existing Map-Matching implementations, and to discuss their suitability in real world problems. | + | {{:teaching:mapmatched.png?direct&400|}} |
+ | |||
+ | Map-matched trajectory | ||
+ | |||
+ | The goal of this project is to build an architecture for a Map-Matching service. The challenges are that the GPS data arrives in different formats, and that Map-Matching is a time consuming Algorithm. This architecture should thus allow different input formats, and should be able to automatically scale according to the request rate. Another key outcome of this project is to compare the existing Map-Matching implementations, and to discuss their suitability in real world problems. | ||
Links: | Links: | ||
Line 61: | Line 71: | ||
* [[https://github.com/graphhopper/map-matching|GraphHopper]] | * [[https://github.com/graphhopper/map-matching|GraphHopper]] | ||
* [[https://github.com/cyang-kth/fmm|Fast Map Matching]] | * [[https://github.com/cyang-kth/fmm|Fast Map Matching]] | ||
+ | |||
+ | ===== Symbolic trajectories ===== | ||
+ | |||
+ | Symbolic trajectories enable to attach semantic information to geometric trajectories. Essentially, symbolic trajectories are just time-dependent labels representing, for example, the names of roads traversed obtained by map matching, transportation modes, speed profile, cells of a cellular network, behaviors of animals, cinemas within 2km distance, and so forth. Symbolic trajectories can be combined with geometric trajectories to obtain annotated trajectories. | ||
+ | |||
+ | The goal of this project is to explore how to implement symbolic trajectories in MobilityDB. This implementation will be based on the ttext (temporal text) data type implemented in MobilityDB and will explore how to extend it with regular expressions. This extension can be inspired from the [[https://www.postgresql.org/docs/13/functions-json.html|jsonb]] data type implemented in PostgreSQL. | ||
+ | |||
+ | Links: | ||
+ | * {{:teaching:symbolic_trajectories.pdf|}} | ||
+ | |||
+ | ===== Trajectory Data Warehouses ===== | ||
+ | Mobility data warehouses are data warehouses that keep location data for a set of moving objects. You can refer to the article below for more information about the subject. The project consists in building a mobility data warehouse for ship trajectories on MobilityDB. | ||
+ | |||
+ | The input data comes from the Danish Maritine Authority (follow the link "Get historical AIS data"). To download the data you must use an FTP client (such as FileZilla). Follow the instructions in Chapter 1 of the MobilityDB Workshop to load the data into MobilityDB. | ||
+ | |||
+ | You must implement a comprehensive data warehouse application. For this, you will perform in particular the following steps. | ||
+ | * Define a conceptual multidimentional schema for the application. | ||
+ | * Translate the conceptual model into a relational data warehouse. | ||
+ | * Implement the relational data warehouse in MobilityDB. | ||
+ | * Implement analytical queries based on the queries proposed in [1]. | ||
+ | |||
+ | Links: | ||
+ | |||
+ | * A. Vaisman and E. Zimányi. [[https://www.mdpi.com/2220-9964/8/4/170|Mobility data warehouses]]. ISPRS International Journal of GeoInformation, 8(4), 2019. | ||
+ | * [[https://www.dma.dk/SikkerhedTilSoes/Sejladsinformation/AIS/Sider/default.aspx|Danish Maritine Authority]] | ||
+ | * [[https://github.com/MobilityDB/MobilityDB-workshop|MobilityDB Workshop]] | ||
+ | |||
+ | |||
+ | |||
+ | |||
Line 68: | Line 108: | ||
The goal of this project is to survey the state of the art in geospatial trajectory data cleaning, both model-based and machine learning. The work also includes prototyping and empirically evaluating a selection of these methods in the MobilityDB system, and on different real datasets. These outcomes should serve as a base for a thesis project to enhance geospatial trajectory data cleaning. | The goal of this project is to survey the state of the art in geospatial trajectory data cleaning, both model-based and machine learning. The work also includes prototyping and empirically evaluating a selection of these methods in the MobilityDB system, and on different real datasets. These outcomes should serve as a base for a thesis project to enhance geospatial trajectory data cleaning. | ||
+ | ===== Dynamic Time Warping for Trajectories ===== | ||
+ | |||
+ | The dynamic time warping (DTW) algorithm is able to find the optimal alignment between two time series. It is often used to determine time series similarity, classification, and to find corresponding regions between two time series. Several dynamic time warping implementations are available. However, DTW has a quadratic time and space complexity that limits its use to small time series data sets. Therefore, a fast approximation of DTW have been proposed that has linear time and space complexity. | ||
+ | |||
+ | The goal of this project is to survey and to prototype in MobilityDB the state of art methods in dynamic time warping. | ||
+ | |||
+ | * Toni Giorgino, [[https://www.jstatsoft.org/article/view/v031i07|Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package]] | ||
+ | * S. Salvador, P. Chan, [[https://cs.fit.edu/~pkc/papers/tdm04.pdf|FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space]] | ||
===== Geospatial Trajectory Similarity Measure ===== | ===== 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. | 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. |