Prof. Dr. rer. nat. Christian Sohler

Prof. Dr. rer. nat. Christian Sohler

Christian Sohler was junior professor in the research group Algorithms and Complexity.

Christian Sohler is now Professor at the TU Dortmund.

Areas of Research:

My research is focussed on foundations of algorithms and data structures. Currently, I am working on one of the major algorithmic challenges introduced by the increased inter-connectivity of modern computer systems: The phenomenon of massive data sets. Maybe the most prominent example for massive data sets is the Web Graph, whose vertices represent the web pages in the Internet and its arcs correspond to the links between then. Other examples for massive data sets include network traffic logs, clickstreams, human genome data, etc.

Besides massive data sets I am interested in Computational Geometry and Computer Graphics.

Algorithm for massive data sets (sublinear algorithms):

There are two paradigms for the development of algorithms for massive data sets: Sampling and Streaming. When we use sampling we select a small random subset of the input by some stochastic process. We hope that this subset represents the input well with respect to the objective of our algorithm. If it does we have a sublinear algorithm, i.e. an algorithm that approximates a problem without looking at the whole input. We distinguish between two types of sublinear sampling algorithms: Sublinear time approximation algorithm and property testers. The first type of algorithm is an approximation algorithm in the classical sense. It can compute from the randomly selected subset of the input a solution whose objective value approximates the objective value of an optimal solution. Because of the fact that it can compute such an approximation by looking only at a (small) random subset of the input, the running time of such an algorithm is sublinear in the input size. The second type of algorithm is a property tester. In property testing the goal is to approximately sove a decision problem. Instead of deciding whether a given object has a predetermined property or not, one has only to decide whether the object has the property or is far away from it.

In streaming the input occurs in the form of a data stream. A good example for a data stream are packets arriving at an Internet router. When we want to maintain statistics about the routed packets we have the effect that we have access to every packet but (usually) not enough space to store even all of their headers. In such a scenario we need an algorithm that extracts a small representative sketch of the input data given as a data stream. Such an algorithm is called a streaming algorithm. Since the size of a sketch is much smaller than the size of the whole input we also speak of a sublinear algorithm.
  • Streaming algorithms
  • Sublinear time approximation algorithms
  • Combinatorial property testing

Geometry and Computer Graphics:

We are currently working on three projects in the area of Computational Geometry and Computer Graphics. The first project deals with the complexity of fundamental geometric structures like the convex hull, Voronoi diagram, and Delaunay triangulation of a point set whose points are perturbed by small random error. This research is motivated by the fact that in many applications these point sets come from physical measurements and the corresponding measurement devices make small errors that are typically modelled by a Gaussian distribution.
The second project is more application oriented. Our goal is to speed up the rendering process in a Computer Graphics system by reording the rendered primitives in one or more relatively small buffers. These buffers can be useful to reduce the number of state changes (change of color, texture, verx program, etc.) in the Graphics hardware or for purposes of improved occlusion culling. We try to model similar problems in the framework of online algorithms, find a good theoretical solution, and derive a good practical solution from our theoretical understanding of the problem.
In the third project we develop algorithms and models for mobile objects. This research is motivated by the massive increase in the number of mobile devices in the recent years. Nowaday, every mobile phone, car, laptop, PDA, etc. has its own processing power and possibly (wireless) network connetion. Basic services like the maintanance of such a network connection require algorithms for mobile data, because the mobile devices have limited power supply and we cannot always connect to the same service station.
  • Smoothed and average case analysis
  • Online algorithms for problems in Computer Graphics
  • Algorithms for mobile data

Current Projects:

  • Algorithms for Data Streams
    The increasing communication capabilities of modern computer systems has led to the phenomenon of massive data sets occurring in the form of data streams. The goal of this project is the development of algorithms that are able to analyze such data streams. The project is funded by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG). [... more]
  • Algorithms for Large Dynamic Geometric Graphs
    The goal of this project is to develop methods for the analysis and processing of large dynamic graphs, which arise among others in applications of computer graphics and in mobile ad-hoc networks. The project Algorithms for Large Dynamic Geometric Graphs is part of the research cluster Algorithms for large and complex Networks and is funded by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG). [...more]
  • Development of a Practical Theory for Clustering Algorihtms through Data-Driven Modeling and Analysis
    The project is part of the research cluster Algorithm Engineering and is funded by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG).