Differences

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

--- teaching:mfe:is [2019/06/07 14:56]
svsummer [Dynamic Query Processing on GPU Accelerators]
+++ teaching:mfe:is [2019/07/09 17:58]
msakr [Scalable Map-Matching]
@@ Line 28: / Line 28: @@
-===== Multi-query Optimization in Spark =====
+===== Dynamic Query Processing in Modern Big Data Architectures =====
-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.
+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 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.
+Modern big data compute architectures such as Apache Spark, Apache Flink, and apache Storm support certain form of Dynamic Query Processing.
+In addition, our lab has recently proposed DYN, a new Dynamic Query Processing algorithm that has strong optimality guarantees, but works in a centralised setting.
+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
-  * An overview of the Apache Spark architecture.
+     * An overview of the continuous query processing models of Flink, Spark and Storm
-  * Develop a performance model for queries executed by Spark.
+     * A qualitive comparison of the algorithms used
-  * An implementation that optimizes queries executed by Spark and identify sharing opportunities.
+     * A proposal for generalizing DYN to the distributed setting.
-  * An experimental validation of the developed system.
+     * An implementation of this geneneralization by means of a compiler that outputs a continous query processing plan
+     * A benchmark set of continuous queries and associated data sets for the experimental validation
+     * An experimental validation of the extension and state of the art
 **Interested?** Contact :  [[svsummer@ulb.ac.be|Stijn Vansummeren]]
 **Status**: available
 ===== Graph Indexing for Fast Subgraph Isomorphism Testing =====
@@ Line 52: / Line 58: @@
 **Interested?** Contact : [[stijn.vansummeren@ulb.ac.be|Stijn Vansummeren]]
-**Status**: available
+**Status**: taken
@@ Line 86: / 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.
+**Interested?**
+  * Contact : [[ezimanyi@ulb.ac.be|Esteban Zimanyi]]
+**Status**: available
+=====Python driver for Trajectories=====
+Similar to the previous topic, yet for Python.
 **Interested?**
@@ Line 125: / 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.
+**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?**