HEINZ NIXDORF INSTITUTE
University of Paderborn
Theoretical Computer Science
AG Meyer auf der Heide

Theoretical Computer Science: Algorithms, Complexity, Parallel Computing

HNI Research Report Series: December 2001, 2000, 1999, 1998, 1997, 1994, 1993.

 

  1. Abstract
  2. Focus in Research and Education
  3. Central research positions
    1. Bulk Synchronous Parallel Computing
    2. Mobile ad hoc Networks
    3. Data Management in Networks
    4. Algorithms for Large Dynamic Geometric Networks
    5. Algorithms and Computer Graphics - Data Structures for Walkthrough Problems
  4. Appendix
    1. Publications
    2. Fairs/Conferences/Seminars
    3. Prizes/Awards
    4. Additional Functions
    5. Projects
 

1. Abstract

High computing performance can only be achieved by a combination of powerful computer systems and algorithms that solve the given application problems as efficiently as possible. Therefore, the development of efficient algorithms has established itself as a classical branch of computer science. In our research area, we concentrate on solutions where current technological possibilities such as computer networks used as high-performance computers pose new challenges for algorithm development.

2. Focus in research and education

Parallel computer networks can potentially supply unlimited computing power. However, the efficient use of these networks is an extremely complex problem. We provide users with a programming environment that is easy to handle and guides them towards the development of efficient algorithms. In order to support such an environment, efficient implementations of basic routines for communication and synchronization are needed. Our research on bridging models, which leads to theoretical evaluation and development of a BSP-like programming framework, and our PUB-library, constitute a valuable contribution to this area. Moreover, our work on data management in networks leads to provably efficient techniques. We implement and test these techniques in the DIVA-library and integrate them in the development of a distributed multimedia server.

To be able to navigate in a virtual 3-dimensional space, and to give a realistic optical impression of the changing scene, enormous demands are imposed on the underlying data structures that handle the scene. Above all, we have to guarantee real time processing in order to guarantee a realistic impression of the scene. Our work on the development of such new types of data structures are incorporated into our prototype walk-through system ParSIWal.

Dynamic networks,i.e., networks whose nodes change their (geometric, geographic) position over time, play a major role in many areas: They can, e.g., be used as data structures for moving objects in Computer Graphics, as well as models for wireless mobile communication networks. We systematically model various kinds of dynamic networks, design algorithms, and apply them to the above mentioned Computer Graphics and communication problems.

The algorithmic work described above has shown us that using randomized procedures can produce amazing gains in efficiency. We are therefore systematically studying the potential of randomized algorithms and using, or developing, probability theory for analyzing such algorithms.

Our research is closely linked to our teaching. Our courses deal with methods and concepts of the development and analysis of efficient algorithms. We also run project groups and support diploma thesis that apply our theoretical insights in order to design efficient algorithms and libraries.

3. Central research positions

Abstract structure of a BSP computer

3.1 Bulk Synchronous Parallel Computing

There is an increasing demand of performance in many scientific and engineering areas. One way to satisfy this demand is the use of parallel computing systems. Unfortunately, programming and maintenance of such systems is much more difficult than that of a sequential computer where we have the versatile, universally successful von Neumann model for which we write our sequential programs.

One prominent reason for this difficulty is the variety of different hardware systems which makes it hard to write portable parallel programs or maintain large parallel software systems. Hence, an abstract model is needed that includes all of the important performance-relevant features and hides hardware specific solutions - a so-called bridging model, that means a ``parallel analogue'' to the von Neumann model. We extended Valiant's Bulk Synchronous Parallel (BSP) bridging model and implement and evaluate the PUB library (Paderborn University BSP) that is used in different scientific projects.

Recently, the PUB Library has been implemented on a Cluster of Linux PCs. Now, also process migration has been sucessfully implemented 

Dr. rer. nat. Rolf Wanka
Phone: +49 (0)52 51 60 64 34
Fax:   +49 (0)52 51 60 64 82
Email: wanka@upb.de
URL:   www.upb.de/cs/wanka.html

3.2 Mobile ad hoc Networks

Simulation of ad hoc networks (SAHNE) Mobile electronic devices (PDA; laptop, mobile phones) are connected to wired networks, e.g. the internet, by centralised protocols (e.g. GPRS, UMTS). In such networks central structure increasing the number of participants reduces the quality of service.

Mobile ad hoc networks (MANET) rely on a different approach. Such a wireless decentralised network has less restrictions for the mobility, since it comes without a fixed infrastructure. Here, increasing network density improves network properties like connectivity and data throughput.

Our research concentrates on the analysis and implementation of of suitable algorithms for network management and routing in MANETs. In cooperation with the system and circuit technology group we implement a prototypical MANET based on the mini-robot Khepera. In this environment, we investigate realistic secenarios and measure the efficiency of different strategies. 

Dr. rer. nat. Christian Schindelhauer
Phone: +49 (0)52 51 60 64 52
Fax:   +49 (0)52 51 60 64 82
Email: schindel@upb.de
URL:   www.upb.de/cs/schindel.html

3.3 Data Management in Networks

SGI(TM) TP9400 Disk Array with up to 1 Terabyte storage capacity. The data distribution bases on a RAID approach. Current storage systems face the difficult task to manage constantly growing data entities very flexible. One way of meeting capacity and performance requirements is the usage of dedicated storage networks. We designe randomized algorithms which not only distribute data blocks evenly but furthermore support diffent dis k sizes and which are adaptive to system changes.
Unfortunately, using randomized approaches introduces new problems. Hence, we search for new techniques which map randomized data blocks to the physical disk layout. Furthermore, we implement our strategies prototypically in order to enable a thorough evaluation. We want to get practical evidence not only for the feasibility of the heterogenous setting and the replacement behaviour but also for the stress imposed onto the underlying hardware structure. This is of crucial importance if distributions over greater distances are concerned.

In another scenario we assume that the usage of network resources like bandwidth or memory is not for free but the user has to pay a fee depending on the amount of data that he wants to store on network nodes or transfer via network links, respectively. This is a realistic model for cost based networks as e.g. the Internet. Whereas in previous scenarios the main goal was only to utilize the available resources as good as possible to gain maximum performance, we now consider the cost that arise from a given data management strategy as well.
In this scenario we have developed data management strategies that aim for a given access pattern, to minimize the cost of the data distribution within the network. We show that the cost of the resulting placement is only a constant factor away from optimal. 

Kay Salzwedel
Phone: +49 (0)5251 606458
Fax:   +49 (0)5251 606482
Email: nkz@upb.de
URL:   www.upb.de/cs/salzwedel.html

Harald Räcke
Phone: +49 (0)5251 606457
Fax:   +49 (0)5251 606482
Email: harry@upb.de
URL:   www.upb.de/cs/raecke.html

3.4 Algorithms for Large Dynamic Geometric Networks

Keeping up dynamic data structure of Delaunay triangulation while nodes move Rapidly decreasing hardware prices and the increase in storage capacity by orders of magnitude in the recent years are the reason for larger and larger data sets that have to be processed by database systems and data mining tools. Cisco, for example, uses the NetFlow software to gather information about the network flow that is routed through their servers. One flow data entry contains information about the IP-adress, source and destination, number of routed packets and number bytes. At a single WorldNet gateway router the amount of information gathered each day is roughly 10 GB.
Another example for huge data sets can be found in telecommunication industry. AT&T, for example, maintains call-detail statistics which contain the called number, the caller's phone number, time, date, and length of the call, as well as data about the billing. Overall, AT&T serves about 200-300 million calls per day and the size of the gathered call-detail data is more than 7 GB. It is often impossible to process data sets of this size with standard linear time algorithms and thus there is a lot of research in new techniques to deal with huge data sets.
One of these techniques is the so called 'Propoerty Testing'. The goal of property testing is to decide whether a given huge object has a (global) property or is far away from any object that has the property. This task should be achieved by only looking at a small sample of the object. We have investigated in fundamental issues in the field of property testing and we developed new models for the testing of geometric properties.
We also worked on data structures for huge dynamic data sets. We assumed that motion is generated outside the system, e.g., by users of mobile phones, and that the data structure may only query for the current position of an object. Again we focussed our work on huge data sets, i.e. we assume that it is impossible to answer queries by simply updating the position of each object at the time when the query is processed. We developed a theoretical model to analyze the quality of algorithms in this szenario. 

Christian Sohler
Phone: +49 (0)5251 606427
Fax:   +49 (0)5251 606482
Email: csohler@upb.de
URL:   www.upb.de/cs/csohler.html

Image creation by randomised sampling

3.5 Algorithms and Computer Graphics - Data Structures for Walkthrough Problems

Real-time navigation in very large highly detailed virtual scenes is an extreme challenge for virtual reality systems. Real-time navigation allows the visitor of the scene an intuitive understanding of the virtual scene. There are two problems: On the one side it is not easy to handle scenes of such sizes and on the other side you have to develop an efficient rendering algorithm.
The main focus of our research consists of the development of virtual reality systems for large scenes that cannot be rendered on one workstation in real-time. Our distributed rendering system PaRSIWal manages such kind of scenes on a distributed workstation cluster and allows a computation of all objects within a fixed distance in nearly output sensitive time.
Currently we focus on the efficient rendering process: We speed up our rendering by the reduction of objects and polygons. Another approach is occlusion culling. Some of the hidden polygons are computed and removed in an early stage of the rendering process. In the scope of two diploma theses we have developed two new occlusion culling algorithms: The first algorithm computes large artificial occluder for an efficient culling computation. The second algorithm substitutes the commonly used hierarchical data structures by a network data structure. This allows a good distributed computation of the hidden surfaces.
Another approach to speed up the rendering process is the approximation of the scenes, e.g., by the use of our randomized Z-buffer algorithm. This algorithm allows an interactive real-time rendering with scenes up to 1014 polygons.
We cooperate with the University of Tübingen in order to develop an interactive real-time visualisation of very large virtual worlds which are stored on a large data server. 

Jens Krokowski
Phone: +49 (0)5251 606491
Fax:   +49 (0)5251 606482
Email: kroko@upb.de
URL:   www.upb.de/cs/kroko.html

4. Appendix

4.1 Publications

[1] V. Brattka, M. Ziegler: "Turing-Computability of (Non-)Linear Optimization", pp.181-184 in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'2001).
[2] V. Brattka, M. Ziegler: "A Computable Spectral Theorem", pp.378-388 in Computability and Complexity in Analysis vol.2064, Springer LNCS series (2001).
[3] A. Czumaj, C. Sohler: "Property Testing with Geometric Queries", in Proceedings of the 9th Annual European Symposium on Algorithms (ESA'2001).
[4] A. Czumaj, C. Sohler: "Testing Hypergraph Coloring", in Proceedings of the 28th International Colloqium on Automata, Languages and Programming (ICALP'2001).
[5] A. Czumaj, C. Sohler: "Soft Kinetic Data Structures", in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA'2001).
[6] J. Fiala, A. V. Fishkin, F. V. Fomin: "Online and Offline Distance Constrained Labeling of Disk Graphs", pp.464-476 in Proceedings of the 9th Annual European Symposium on Algorithms (ESA'2001), vol.2161 Springer LNCS series (2001).
[7] F. V. Fomin, D. Kratsch, J. C Novelli: "Approximating minimum cocolourings.", pp.118-125 in Proceedings of the 13-th International Symposium on Fundamentals of Computation Theory (FCT 2001), vol.2138 Springer LNCS.
[8] F. V. Fomin, A. Lingas: "Approximation algorithms for time-depending orienteering", pp.508-515 in Proceedings of the 13-th International Symposium on Fundamentals of Computation Theory and the 1st International Workshop on Efficient Algorithms (FCT'2001 + WEA'2001), vol.2138 Springer LNCS.
[9] F. V. Fomin, M. Matamala, E. Prisner, I. Rapaport: "Bilateral orientations and domination", in Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2001), vol.7 of Electronic Notes in Discrete Mathematics, Elsevier Science Publishers (2001).
[10] A. Jakoby, C. Schindelhauer: "Efficient Addition on Field Programmable Gate Arrays", in Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'2001).
[11] B. Juurlink, P. Kolman, F. Meyer auf der Heide, I. Rieping: "Optimal Broadcast on Parallel Locality Models", to appear in Journal of Discrete Algorithms (2001).
[12] J. Klein, M. Fischer: "Occlusion Culling for Virtual Environments based on the 3D-Sectorgraph", Informatiktage 2001 (Bad Schussenried).
[13] C. Krick, H. Räcke, M. Westermann: "Approximation Algorithms for Data Management in Networks", pp.237-246 in Proceedings of the 13th ACM SPAA (2001).
[14] F. Meyer auf der Heide, R. Wanka: "Parallel Bridging Models and Their Impact on Algorithm Design", pp.628-637 in Part II of Proc. Int. Conf. on Computational Science (ICCS'2001).
[15] A. Piccolboni, C. Schindelhauer: "Discrete Prediction Games with arbitrary Feedback and Loss", pp.208-232 in 14th Annual Conference on Computational Learning Theory (COLT'2001).
[16] R. Preis, K. Salzwedel, G. Hartmann, C. Wolff: "Efficient Parallel Simulation of Pulse-Coded Neural Networks (PCNN)", pp.463-469 in Proceedings of the 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'2001):
[17] M. Reza Emamy-K., M. Ziegler: "New Bounds for Hypercube Slicing Numbers", pp.155-164 in Proceedings of the First International Conference on Discrete Models - Combinatorics, Computation and Geometry (DM-CCG'2001).
[18] C. Schindelhauer, B. Weber: "Tree Approximation for the Weighted Cost-Distance Problem", in Proceedings of the International Symposium on Algorithms and Computation (ISAAC'2001).
[19] M. Wand, M. Fischer, I. Peter, F. Meyer auf der Heide, W. Straßer: "The Randomized z-Buffer Algorithm: Interactive Rendering of Highly Complex Scenes", in Computer Graphics Conference Proceedings (SIGGRAPH'2001).

4.2 Fairs/Conferences/Seminars

 ALCOM-FT Spring School on Dynamic Algorithms, May 10-11, 2001
Organizer: Rolf Wanka

4.3 Prizes/Awards

Every year, the Department no.17 (Computer Science) of Paderborn University awards the best diploma thesis. In 2001, this prize was rewarded to Michael Wand for his thesis on "Approximative Darstellung dreidimensionaler Szenen mit randomisiertem Z-Buffer".

4.4 Additional Functions
Friedhelm Meyer auf der Heide
Rolf Wanka

4.5 Projects