Department of Informatics – DDIS


Bachelor Theses

This pages lists the BSc. Theses topics currently available in our group. Don't hesitate to contact the respective person if you are interested in one of the topics. If you would like to write a thesis about your own idea you can propose it to the person most related to what you plan to do or you can contact Prof. Bernstein directly.

Rank Based Algorithms for Distributed Constraint Optimization

Approaching Distributed Constraint Optimization Problems with Local Iterative Best Response Algorithms [1,2] is a way to get approximate solutions in a short amount of time, proving to be useful in a number of critical-time scenarios.

Based on the framework description in [1], we created a framework in Signal/Collect [3] that allows to seamlessly plug in different components to create different Local Iterative Best Response Algorithms. So far, we have created components for DSA and extended the framework and this algorithm with a version inspired by PageRank, Ranked-DSA. This ranked version leads to much faster convergence, but usually to a lower-utility local optimum than the original. The trade-off between speed of convergence and solution quality can further be explored by adding vertices of different types in different proportions.

The goal of the thesis would be to extend and evaluate other Local Iterative Best Response Algorithms with ranked versions. This would also include an evaluation of mixing vertices that use different algorithms.

Challenges: Design and implement the components for, and evaluate the ranked versions of the algorithms in Signal/Collect.

[1] Chapman et al., A unifying framework for iterative approximate best-response algorithms for distributed constraint optimization problems
[2] Chapman et al., Benchmarking Hybrid Algorithms for Distributed Constraint Optimisation Games

Posted: 16.06.2014

Contact: Mihaela Verman

Behavior-Based Quality Assurance in Crowdsourcing Markets

A big problem in crowdsourcing markets is the design of robust quality assurance mechanisms. Today, the lack of methods is compensated using massive redundancy in task allocation and / or the use of voting mechanisms. Recenty research showed that the use of behavioral data (e.g., working time per task, mouse movements) can be a sophisticated indicator for the resulting quality.

In this bachelor / master thesis, you will design several worker behavior-based quality predictors and evaluate them in various domains.

Contact: Patrick de Boer or Michael Feldmann

Linked Raster Data

In the Geo-Sptial community, Linked Data is gaining increasing importance. Recent examples are Linked Geo-Data and, most popular, Geonames aka the Linked Data version of Open Street Map. Such initiatives are not only supported by academia but indeed backed by prominent partners from industry (e.g. ESRI, Oracle) and the public services (UK Ordnance Survey, Swiss Federal Office for the Environment, US National Geographic Survey). Most approaches, however, aim towards the processing of vector data where entities (points, lines, polygons) are defined ex-ante. In collaboration with the Department of Geography (UZH) we recently approached towards linking raster data such as fields containing information about slope, height, population density, etc. to the Linked Open Data cloud. In particular, it is features deduced from raster data that can potentially be enriched with semantics.

Your task will be to integrate operators from a Geographic Information System such as ArcGIS or GRASS into a SPARQL engine such as Jena or Sesame. Based on a faceted browser you will integrate raster-data into the results of faceted search and/or faceted browsing. In the context of a Bachelor's thesis you will also show how operators in SPARQL translate into operators in the GIS. If performed as a Master Project, the work will more focus on the integration and optiomization aspect of SPARQL to GIS and vice versa.

Contact: Thomas Scharrenbach

High performance data (RDF) processing

As published RDF data continues to grow (the LOD reported 31 billion triples as of September 2011), the need for high-performance data processing algorithms is paramount. This series of bachelore-thesis projects is intended to attract students that have good knowledge of algorithmic desing and/or are interested in learning more. Possible topics include but are not limited to: efficient merge algoritms (in-place), efficient external sorting (standard and/or map-reduce based), load balancing of resources (CPU / DISK) in parallel processing systems (fuzzy logic based controllers, evolutionary algorithms, other). The students should also have knowledge of C and python.

Contact: Cosmin Basca