Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
teaching:mfe:is [2019/05/13 12:39]
mahmsakr
teaching:mfe:is [2019/07/09 17:58] (current)
msakr [Scalable Map-Matching]
Line 27: Line 27:
  
  
-===== Dynamic Query Processing on GPU Accelerators ===== 
  
-This master thesis is put forward in the context of the DFAQ Research Project: "​Dyanmic ​Processing ​of Frequently Asked Queries",​ funded by the Wiener-Anspach foundation.+===== Dynamic Query Processing ​in Modern Big Data Architectures =====
  
-Within this project, our lab is hence developing novel ways for processing ​"fast Big Data", i.e., processing of analytical ​queries ​where the underlying ​data is constantly being updatedThe analytics problems envisioned cover wide areas of computer science and include database aggregate queries, probabilistic inference, matrix chain computation,​ and building statistical models.+Dynamic Query Processing refers to the activity of processing queries ​under constant ​data updates. (This is also known as continuous querying)It is a core problem in modern analytic workloads.
  
-The objective of this master thesis is to build upon the novel dynamic processing algorithms being developed in the lab, and complement these algorithms by proposing dynamic evaluation algorithms that execute on modern GPU architectures, ​thereby exploiting their massive parallel processing capabilities.+Modern big data compute ​architectures ​such as Apache SparkApache Flink, and apache Storm support certain form of Dynamic Query Processing.
  
-Since our current development is done in the Scala programming languageprospective students should either know Scala, or being willing to learn it within the context of the master thesis. +In addition, ​our lab has recently proposed DYN, a new Dynamic Query Processing algorithm that has strong optimality guaranteesbut works in centralised setting.
- +
- +
-**Validation of the approach** Validation of master thesis'​ work should be done on two levels: +
-  * theoretical level; by proposing and discussing alternative ways to do incremental computation on GPU architecturesand comparing these from theoretical complexity viewpoint +
-  * an experimental level; by proposing a benchmark collection of CEP queries that can be used to test the obtained versions of the interpreter/​compiler,​ and report on the experimentally observed performance on this benchmark.+
  
 +The objective of this master thesis is to propose extensions to our algorithm that make it suitable for distributed implementation on one of the above-mentioned platforms, and compare its execution efficiency against the state-of-the art solutions provided by Spark, Flink, and Storm. In order to make this comparison meaningfull,​ the student is expected to research, survey, and summarize the principles underlying the current state-of-the art approaches.
  
 **Deliverables** of the master thesis project **Deliverables** of the master thesis project
-  ​* An overview of query processing ​on GPUs +     * An overview of the continuous ​query processing ​models of Flink, Spark and Storm 
-  * A definition ​of the analytics queries under consideration +     ​* A qualitive comparison ​of the algorithms used 
-  * A description of different possible dynamic evaluation algorithms ​for the analytical queries on GPU architectures+     ​* A proposal ​for generalizing DYN to the distributed setting
-  A theoretical comparison ​of these possibilities +     ​An implementation ​of this geneneralization by means of compiler ​that outputs a continous query processing plan 
-  * The implementaiton ​of the evaluation algorithm(s) (as an interpreter/​compiler) +     ​* A benchmark set of continuous ​queries and associated data sets for the experimental validation 
-  * A benchmark set of queries and associated data sets for the experimental validation +     ​* An experimental validation of the extension ​and state of the art
-  * An experimental validation of the compiler, ​and analysis ​of the results.+
  
  
 **Interested?​** Contact :  [[svsummer@ulb.ac.be|Stijn Vansummeren]] **Interested?​** Contact :  [[svsummer@ulb.ac.be|Stijn Vansummeren]]
- 
  
 **Status**: available **Status**: available
- 
-===== Multi-query Optimization in Spark ===== 
- 
-Distributed computing platforms such as Hadoop and Spark focus on addressing the following challenges in large systems: (1) latency, (2) scalability,​ and (3) fault tolerance. Dedicating computing resources for each application executed by Spark can lead to a waste of resources. Unified distributed file systems such as Alluxio has provided a platform for computing results among simultaneously running applications. However, it is up to the developers to decide on what to share. 
- 
-The objective of this master thesis is to optimize various applications running on a Spark platform, optimize their execution plans by autonomously finding sharing opportunities,​ namely finding the RDDs that can be shared among these applications,​ and computing these shared plans once instead of multiple times for each query. 
- 
-**Deliverables** of the master thesis project 
-  * An overview of the Apache Spark architecture. 
-  * Develop a performance model for queries executed by Spark. 
-  * An implementation that optimizes queries executed by Spark and identify sharing opportunities. 
-  * An experimental validation of the developed system. 
- 
-**Interested?​** Contact :  [[svsummer@ulb.ac.be|Stijn Vansummeren]] 
- 
-**Status**: available 
- 
 ===== Graph Indexing for Fast Subgraph Isomorphism Testing ===== ===== Graph Indexing for Fast Subgraph Isomorphism Testing =====
  
Line 82: Line 58:
 **Interested?​** Contact : [[stijn.vansummeren@ulb.ac.be|Stijn Vansummeren]] **Interested?​** Contact : [[stijn.vansummeren@ulb.ac.be|Stijn Vansummeren]]
  
-**Status**: ​available+**Status**: ​taken
  
  
Line 116: Line 92:
  
 As MobilityDB build on top of PostGIS, the Java driver will need to do the same, and build on top of the PostGIS driver. Mainly the driver will need to provide Java classes to represent all the types of MobilityDB, and access the basic properties.  ​ As MobilityDB build on top of PostGIS, the Java driver will need to do the same, and build on top of the PostGIS driver. Mainly the driver will need to provide Java classes to represent all the types of MobilityDB, and access the basic properties.  ​
 +
 +**Interested?​**
 +  * Contact : [[ezimanyi@ulb.ac.be|Esteban Zimanyi]]
 +
 +**Status**: available
 +
 +=====Python driver for Trajectories=====
 +Similar to the previous topic, yet for Python. ​
  
 **Interested?​** **Interested?​**
Line 155: Line 139:
 This thesis is about proposing a data model for spatiotemporal regions, and implementing it in MobilityDB. This includes surveying the literature on moving object databases, and specifically on spatiotemporal reigons, proposing a discrete data model, implementing it, and implementing the basic data base functions and operations to make use of it.  This thesis is about proposing a data model for spatiotemporal regions, and implementing it in MobilityDB. This includes surveying the literature on moving object databases, and specifically on spatiotemporal reigons, proposing a discrete data model, implementing it, and implementing the basic data base functions and operations to make use of it. 
  
 +
 +**Interested?​**
 +  * Contact : [[ezimanyi@ulb.ac.be|Esteban Zimanyi]]
 +
 +**Status**: not available
 +
 +=====Scalable Map-Matching=====
 +GPS trajectories originate in the form of a series of absolute lat/lon coordinates. Map-matching is the method of locating the GPS observations onto a road network. It transforms the lat/lon pairs into pairs of a road identifier and a fraction representing the relative position on the road. This preprocessing is essential to trajectory data analysis. It contributes to cleaning the data, as well as preparing it for network-related analysis. There are two modes of map-matching:​ (1) offline, where all the observations of the trajectory exist before starting the map-matching,​ and (2) online, where the observation arrive to the map-matcher one by one in a streaming fashion. Map-matching is known to be an expensive pre-processing,​ in terms of processing time. The growing amount of trajectory data (e.g., autonomous cars) call for map-matching methods that can scale-out. This thesis is about proposing such a solution. It shall survey the existing Algorithms, benchmark them, and propose a scale out architecture. ​  
 +
 +MobilityDB has types for lat/lon trajectories,​ as well as map-matched trajectories. the implementation of this thesis shall be integrated with MobilityDB. ​
  
 **Interested?​** **Interested?​**
 
teaching/mfe/is.1557743961.txt.gz · Last modified: 2019/05/13 12:39 by mahmsakr