Differences

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

--- teaching:projh402 [2018/10/02 08:13]
svsummer
+++ teaching:projh402 [2020/12/23 22:53]
ezimanyi [Distributed Moving Object Database on MS Azure]
@@ 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.
-===== Project proposals =====
+===== Projects in Mobility Databases =====
-=== Engineering of a Rule-Based Information Extraction Engine ===
+Mobility databases (MOD) are database systems that can store and manage moving object geospatial trajectory data. A moving object is an object that changes its location over time (e.g., a car driving on the road network). Using a variety of sensors, the location tracks of moving objects can be recorded in digital formats. A MOD, then, helps storing and querying such data. A couple of prototype systems have been proposed by research groups. Yet, a mainstream system is by far still missing. By mainstream we mean that the development builds on widely accepted tools, that are actively being maintained and developed. A mainstream system would exploit the functionality of these tools, and would maximize the reuse of their ecosystems. As a result, it becomes more closer to end users, and easily adopted in the industry.
-Information extraction, the activity of extracting structured
+Towards filling this gap, our group is building the [[https://github.com/MobilityDB/MobilityDB|MobilityDB]] system. It builds on [[https://postgis.net/|PostGIS]], which is a spatial database extension of [[https://www.postgresql.org/|PostgreSQL]]. MobilityDB extends the type system of PostgreSQL and PostGIS with abstract data types (ADTs) for representing moving object data. It defines, for instance, the tgeompoint type for representing a time dependant geometry point. MobilityDB types are well integrated into the platform, to achieve maximal reusability, hence a mainstream development. For instance, the tgeompoint type builds on the PostGIS geometry(point) type. Similarly MobilityDB builds on existing operations, indexing, and optimization framework.
-information from unstructured text, is a core data preparation
-step. Systems for information extraction fall into two main
-categories. The first category contains machine-learning based
-systems, where a significant amount of training is required to train
-good models for specific extraction tasks. The second category
-consists of rule-based systems in which the data to be extracted from
-the text is specified by (human-written) rules in some (often
-declarative) extraction language. Despite advances in machine
-learning, rule-based systems are widely used in practice.
-In recent years, novel theoretical algorithms have been proposed to
+MobilityDB supports SQL as query interface. Currently it is quite rich in terms of types and functions. It is incubated as community project in [[https://www.osgeo.org/projects/mobilitydb/|OSGeo]], which certifies high technical quality.
-more efficiently execute rule-based information extraction
-workloads. The objective in this project is to implement one such
-Algorithm, by Florenzano et al (2018), experimentally analyze its
-performance, and propose extensions of the algorithm to overcome
-performance bottlenecks.
+The following project ideas contribute to different parts of MobilityDB. They all constitute innovative development, mixing both research and development. They hence will help developing the student skills in:
-References:
+  * Understanding the theory and the implementation of moving object databases.
+  * Understanding the architecture of extensible databases, in this case PostgreSQL.
+  * Writing open source software.
-- Fernando Florenzano, Cristian Riveros, Martín Ugarte,
-Stijn Vansummeren, Domagoj Vrgoc: Constant Delay Algorithms for
-Regular Document Spanners. PODS 2018: 165-177
+===== Visualization of Moving Objects on the Web =====
-**Interested?** Contact Stijn Vansummeren (stijn.vansummeren@ulb.ac.be)
+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.
-**Status**: available
+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|}}
-=== Query processing for mixed database-machine learning based workloads ===
+Animated visualization of car trajectories
-Because of the growing importance and wide deployment of large-scale
+**Status**: taken
-Machine Learning (ML), there is wide interest in the design and
+===== Implementing TSBS on MobilityDB =====
-implementation of processing engines that can efficiently evaluate ML
-workloads. One class of sytems, embodied by systems such as Tensorflow
-and SystemML takes linear algebra as the key primitive for expressing
-ML workflows, and obtain efficient processing engines by porting known
-database-style optimization techniques to the linear algebra
-setting. Another class of systems, embodied by FAQ queries take
-relational algebra as the key primitive, but modify it to allow
-expression of certain ML workloads. To some extent, the classical
-optimization techniques as well as recent results for exploiting
-modern hardware transfer to this extended relational algebra. As an
-added bonus, traditional database workloads (OLTP/OLAP style) can be
-trivially supported
-The focus in this project is in the latter style of systems. The
+The Time Series Benchmark Suite ([[https://github.com/timescale/tsbs|TSBS]]) is a collection of Go programs that are used to generate datasets and then benchmark read and write performance of various time series databases. This bechmark has been developed by [[https://www.timescale.com/|TimescaleDB]], which is a time series extension of PostgreSQL.
-overall goal is to experimentally identify classes of FAQ queries for
-which it would be beneficial to exploit techniques developped in the
+A significant addition of TimescaleDB to PosgreSQL is the addition of the [[https://blog.timescale.com/blog/simplified-time-series-analytics-using-the-time_bucket-function/|time_bucket]] function. This function allows to partition the time line in user-defined interval units that are used for aggregating data.
-former class of systems. Concretely, this can be approached by
-experimentally studying queries in the FAQ framework (featuring joins)
+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.
-for which known results in evaluating linear algebra operations (in
-concretum: matrix multiplication algorithms that run in less than
+**Status**: taken
-O(n^3) time) can be exploited.
+===== 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.
+**Status**: taken
+===== 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.
+{{:teaching:original.png?direct&400|}}
+Original trajectory
+{{:teaching:mapmatched.png?direct&400|}}
+Map-matched 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.
+Links:
+  * [[https://github.com/bmwcarit/barefoot|Barefoot]]
+  * [[https://valhalla.readthedocs.io/en/latest/api/map-matching/api-reference/|Valhalla Map Matching API]]
+  * [[https://github.com/graphhopper/map-matching|GraphHopper]]
+  * [[https://github.com/cyang-kth/fmm|Fast Map Matching]]
+**Status**: taken
+===== Geospatial Trajectory Data Cleaning =====
+Data cleaning is essential preprocessing for analysing the data and extracting meaningful insights. Real data will typically include outliers, inconsistencies, missing data, repeated transactions possibly with different keys, and other kinds of acquisition errors. In geospatial trajectory data, there are even more sources of error, such as GPS inaccuracies.
+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.
+===== 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, namely, [[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.
+===== VODKA Indexes for MobilityDB =====
+MobilityDB provides [[https://habr.com/en/company/postgrespro/blog/444742/|GiST]] and [[https://habr.com/ru/company/postgrespro/blog/446624/|SP-GiST]] indexes for temporal types. These indexes are based on bounding boxes, that is, the nodes of the index tree store a bounding box that keeps the mininum and maximum values of each of the dimensions where X, Y, Z (if available) are for the spatial dimension and T for the temporal dimension. The reason for this is that a temporal type (for example, a moving point representing the movement of a vehicle) can have thousands of timestamped points and keeping all these points for each vehicle indexed in a table is very inefficient. By keeping the bounding box only it is possible to quickly filter the rows in a table and then a more detailed analysis can be made for those rows selected by the index.
+However, the drawback of keeping a single bounding box for the whole trajectory makes that the index is not very selective as shown in the following figure (extracted from a presentation by Oleg Bartunov from PostgresPro)
+{{:teaching:gist.png?400|}}
+The goal of the project is to define [[https://www.pgcon.org/2014/schedule/events/696.en.html|VODKA indexes]] for MobilityDB, which  enable us to store in the index multiple bounding boxes (one per segment) associated to each row in the table as shown in the following figure
+{{:teaching:vodka.png?400|}}
-**Contact** : Stijn Vansummeren (stijn.vansummeren@ulb.ac.be)
-**Status**: available