This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
teaching:mfe:is [2019/05/13 12:39] mahmsakr |
teaching:mfe:is [2020/09/29 17:03] (current) mahmsakr [Data modeling of spatiotemporal regions] |
||
|---|---|---|---|
| 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 updated. The 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 Spark, Apache Flink, and apache Storm support certain form of Dynamic Query Processing. |
| - | Since our current development is done in the Scala programming language, prospective 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 guarantees, but works in a centralised setting. |
| - | + | ||
| - | + | ||
| - | **Validation of the approach** Validation of master thesis' work should be done on two levels: | + | |
| - | * a theoretical level; by proposing and discussing alternative ways to do incremental computation on GPU architectures, and comparing these from a 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 a 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**: taken | |
| - | **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 120: | Line 96: | ||
| * Contact : [[ezimanyi@ulb.ac.be|Esteban Zimanyi]] | * Contact : [[ezimanyi@ulb.ac.be|Esteban Zimanyi]] | ||
| - | **Status**: available | + | **Status**: taken |
| =====Mobility data exchange standards===== | =====Mobility data exchange standards===== | ||
| Line 150: | Line 127: | ||
| **Status**: available | **Status**: available | ||
| - | =====Data modeling of spatiotemporal regions===== | ||
| - | In moving object databases, a lot of attention has been given to moving point objects. Many data model have been proposed for this. Less attention has been given to moving region objects. Imagine a herd of animals that moves together in the wild. At any time instant, this herd can be represented using a spatial region, e.g., their convex hull. Over time, this regions changes place and extent. A spatiotemporal region is an abstract data type that can represent this temporal evolution of the region. | ||
| - | 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. | + | =====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?** | ||