Differences

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

--- teaching:projh402 [2015/06/26 16:09]
svsummer
+++ teaching:projh402 [2021/10/04 19:30]
msakr
@@ Line 1: / Line 1: @@
-====== MA Computer Science Projects (PROJ-H-402)  ======
+====== MA Computer Science Projects (PROJ-H-402) =====
+====== Master's Thesis Projects (MEMO-H-504) ======
 ===== 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 Pr. 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.
+The course MEMO-H504 is managed by Pr. Nicolas Cerf.
-===== Project proposals =====
+What follows is a list of project proposals supervised by academic members of the WIT laboratory. The proposals below concern both PROJ-H-402 or MEMO-H-504.
+===== Projects in Mobility Databases =====
-===== Graph Indexing for Fast Subgraph Isomorphism Testing =====
+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.
-There is an increasing amount of scientific data, mostly from the bio-medical sciences, that can be represented as collections of graphs (chemical molecules, gene interaction networks, ...). A crucial operation when searching in this data is that of subgraph    isomorphism testing: given a pattern P that one is interested in (also a graph) in and a collection D of graphs (e.g., chemical molecules), find all graphs in G that have P as a   subgraph. Unfortunately, the subgraph isomorphism problem is computationally intractable. In ongoing research, to enable tractable processing of this problem, we aim to reduce the number of candidate graphs in D to which a subgraph isomorphism test needs   to be executed. Specifically, we index the graphs in the collection D by means of decomposing them into graphs for which subgraph   isomorphism *is* tractable. An associated algorithm that filters graphs that certainly cannot match P can then formulated based on ideas from information retrieval.
+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.
-In this project, the student will emperically validate on real-world datasets the extent to which graphs can be decomposed into graphs for which subgraph isomorphism is tractable, and run experiments to validate the effectiveness of the proposed method in terms of filtering power.
+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.
-**Interested?** Contact : [[stijn.vansummeren@ulb.ac.be|Stijn Vansummeren]]
+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:
-**Status**: available
+  * Understanding the theory and the implementation of moving object databases.
+  * Understanding the architecture of extensible databases, in this case PostgreSQL.
+  * Writing open source software.
-==== Principles of Database Management Architectures in Managed Virtual Environments ====
-With the gaining popularity of Big Data, many data processing engines
+===== Visualization of Moving Objects on the Web =====
-are implemented in a managed virtual environment such as the Java
-Virtual Machine (e.g., Apache Hadoop, Apache Giraph, Drill,
-...). While this improves the portability of the engine, the tradeoffs
-and implementation principles w.r.t. traditional C++ implementations
-are sometimes less understood.
-The objective in this project is to develop some basic functionalities
+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.
-of a database storage engine (Linked files, BTree, Extensible Hash
-table, basic external-memory sorting ) in a managed virtual machine
-(i.e., the Java Virtual Machine or and the .NET Common Language
-Runtime), and compare this with a C++-based implementation both on (1)
-ease of implementation and (2) execution efficiency. In order to
-develop the managed virtual machine implementation, the interested
-student will need to research the best practices that are used in the
-above-mentioned projects to gain maximum execution speed (e.g., use of
-the java.lang.unsafe feature, memory-mapped files, ...).
-**Contact** : Stijn Vansummeren (stijn.vansummeren@ulb.ac.be)
+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.
-**Status**: available
+{{:teaching:trips2.gif?direct|}}
+Animated visualization of car trajectories
-==== Development of a compiler and runtime engine for AQL ====
+===== MobilityDB on Google Cloud Platform =====
-In 2005, researchers at the IBM Almaden Research Center developped a
+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.
-new system specifically geared for practical information extraction in
-the enterprise. This effort lead to [[https://www.google.be/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&ved=0CEYQFjAB&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.179.356%26rep%3Drep1%26type%3Dpdf&ei=gyhIUe-XPIexPJ-fgLAG&usg=AFQjCNHgkbcREbd6bCA26BVf0FuIZ9n7Sg&sig2=LVQkus_67uSVlwK34BXZ8w&bvm=bv.43828540,d.ZWU|SystemT]] , a rule-based IE system with an SQL-like declarative language named [[http://pic.dhe.ibm.com/infocenter/bigins/v2r0/topic/com.ibm.swg.im.infosphere.biginsights.analyze.doc/doc/aql_overview.html|AQL (Annotation Query Language)]].
-The declarative nature of AQL enables new kinds of tools for extractor
-development, and a cost-based optimizer for
-performance.
-The goal of this project is to develop an open-source compiler and
+Links:
-runtime environment of (a simplified version of) AQL.
+  * [[https://github.com/MobilityDB/MobilityDB-Azure|MobilityDB-Azure]]
+  * [[https://github.com/MobilityDB/MobilityDB-AWS|MobilityDB-AWS]]
-**Contact** : Stijn Vansummeren (stijn.vansummeren@ulb.ac.be)
+**Status**: taken
+===== Implementing TSBS on MobilityDB =====
-**Status**: available
+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.
-==== Development of a distributed simulation algorithm ====
+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.
-Simulation and Bisimulation are fundamental notions in computer
+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.
-science. They underly many formal verification algorithms, and have
-recently been applied to the construction of so-called structural
-indexes,which are novel index data structures for relational databases
-and the Semantic Web.  Essentially, a (bi)simulation is a relation on
-the nodes of a graph. Unfortunately, however, while efficient
-main-memory algorithms for computing whether two nodes are similar
-exist, these algorithms fail when no the input graphs are too large to
-fit in main memory.
-The objective of this project is to implement a recently proposed
+**Status**: taken
-algorithm for  computing simulation in a distributed setting, and
-provide a preliminary performance evaluation of this implementation.
-**Contact** : Stijn Vansummeren (stijn.vansummeren@ulb.ac.be)
-**Status**: available
+===== 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 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:
+  * [[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]]
+===== 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:
+  * R.H. Guting, F Valdés, M.L. Damiani, {{:teaching:symbolic_trajectories.pdf|Symbolic Trajectories}}, ACM Transactions on Spatial Algorithms Systems, (1)2, Article 7, 2015
+===== 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]]
+===== 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.
+===== 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 that has linear time and space complexity has been proposed.
+The goal of this project is to survey and to prototype in MobilityDB the state of art methods in dynamic time warping.
+  * T. Giorgino, [[https://www.jstatsoft.org/article/view/v031i07|Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package]], Journal of Statistical Software, (31)7, 2009.
+  * S. Salvador, P. Chan, [[https://cs.fit.edu/~pkc/papers/tdm04.pdf|FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space]], Intelligent Data Analysis, 11(5):561-580, 2007.
+  * D.F. Silva, G.E.A.P.A. Batista, [[http://sites.labic.icmc.usp.br/dfs/pdf/SDM_PrunedDTW.pdf|Speeding Up All-Pairwise Dynamic Time Warping Matrix Calculation]], Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 837-845, 2016.
+  * G. Al-Naymat, S. Chawla, J. Taheri (2012). [[https://arxiv.org/abs/1201.2969|SparseDTW: A Novel Approach to Speed up Dynamic Time Warping]]. CoRR abs/1201.2969, 2012.
+  *  M. Müller, H. Mattes, F. Kurth,  [[https://www.audiolabs-erlangen.de/content/05-fau/professor/00-mueller/03-publications/2006_MuellerMattesKurth_MultiscaleAudioSynchronization_ISMIR.pdf|An Efficient Multiscale Approach to Audio Synchronization]]. Proceedings of the International Conference on Music Information Retrieval (ISMIR), pp. 192-197, 2006.
+  * Thomas Prätzlich, Jonathan Driedger, and Meinard Müller, [[https://www.researchgate.net/publication/303667579_Memory-Restricted_Multiscale_Dynamic_Time_Warping|Memory-Restricted Multiscale Dynamic Time Warping]], Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 569-573, 2016.
+===== 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|}}
+===== Finding Logic Bugs in Database Systems =====
+Database management systems are complex in their implementations. Implementation errors (Bugs) are therefore inevitable, no matter how mature the implementation is. Logic bugs are one kind of bugs, that cause a query to return incorrect results (e.g., less or more data in the results). Since they don't result in a system crash, logic bugs are difficult to discover.
+{{:teaching:mfe:logicBugs.png?400|}}
+source: Finding Logic Bugs in Database Management Systems (Manuel Rigger, ETH SQLancer)
+[[https://github.com/sqlancer/sqlancer|SQLLancer]] is an interesting tool that finds logic bugs by implementing a set of automated logic techniques for generated test queries. One techniques, for instance is the Ternary Logic Partitioning (TLP). TLP partitions a query into three partitioning queries, each of which computes its result, where respectively a predicate p, NOT p, and p IS NULL holds. Clearly the union of the three results must be the whole relation, otherwise a bug is spotted !
+The aim of this project is to extend SQLLancer (and the theory behind it) for testing moving object databases. In more detail, the goals are:
+  - Identify the relevant state of the art
+  - Test SQLLancer, and repeat all its experiments
+    * ----- Milestone PROJ-H-402
+  - Extend the logic bug finding methods for spatiotemporal trajectories
+  - Find logic bug in MobilityDB
+    * ----- Milestone MEMO-H-504
+Links for further readings:
+  * [[https://www.usenix.org/system/files/osdi20-rigger.pdf|Testing Database Engines via Pivoted Query Synthesis (OSDI '20)]]
+  * [[https://arxiv.org/abs/2007.08292|Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction (ESEC/FSE '20) ]]
+  * [[https://dl.acm.org/doi/pdf/10.1145/3428279|Finding Bugs in Database Systems via Query Partitioning (OOPSLA '20) ]]
+===== Improving Database Query Performance Using Learned Indexes =====
+Secondary indexes are essential for fast query evaluation in databases. An index is a data structure that stores attribute values in a way that enables fast search, and links these values to their tuples in the storage medium. Recent works revealed that the
+learned index can improve query performance while reducing the index storage overhead.
+In [1] a learned 2D index is proposed, SPRIG. It samples the spatial data to construct an adaptive grid and use the sample data as inputs to fit a spatial interpolation function. Given a spatial search key, first, it will use the fitted spatial interpolation function to predict the approximate position of the key. Then, around the estimated position, it conducts a local binary search to find the target key.
+{{:teaching:mfe:sprig.png?400|}}
+source: [1]
+While the SPRIG index is built for 2D spatial data, it should be possible to generalize it to nD, e.g., spatiotemporal, because the main structure is a grid. The goal of this thesis is to design and build learned indexes for geospatial trajectory data. In more detail, the goals are:
+  - Identify the relevant state of the art
+  - Implement and benchmark the SPRIG learned index [1]
+    * ----- Milestone PROJ-H-402
+  - Design a spatiotemporal learned index
+  - Implement in MobilityDB
+    * ----- Milestone MEMO-H-504
+Links for further readings:
+  - [[https://arxiv.org/pdf/2102.06789.pdf|Spatial Interpolation-based Learned Index for Range and kNN Queries]]
+  - [[https://www.cs.purdue.edu/homes/aref/LMDI2020/LMDI_Tutorial_SIGSpatial2020.pdf|A Tutorial on Learned Multi-dimensional Indexes (SigSpatial20)]]