Oberseminar Lehrstuhl Mayr
-
Space-efficient q-gram indices
Raum: 03.11.018
Zeit: Donnerstag, 22.09.2011, 14.00 Uhr
Vortragender: Johannes Merkle
-
tt-analyze and tt-generate: Tools to Analyze and Generate Sequences with Trained Statistical Properties
Raum: 03.11.018
Zeit: Montag, 29.08.2011, 13.30 Uhr
Vortragender: Johannes Krugel
Algorithms working on sequences are influenced by the statistical properties of the sequences. Algorithms for fragment assembly for example usually produce a worse result if there are many repetitions. Also the space usage and running time of many data structures and algorithms depend on the statistical properties of the underlying text.
We implemented tt-analyze, a tool to analyze sequences for certain statistical properties, among others the entropy, the number and distribution of different substrings, and the repeat structure. Besides, we also designed and implemented tt-generate, a tool to generate synthetic sequences with certain predefined properties, using models such as a Markov process, a discrete autoregressive process, and a repeat model. In bioinformatics these models have primarily been used to analyze given sequences, whereas here, we use them to also generate synthetic ones. The respective parameters of the models can be defined manually or be learned from given training data.
The combination of both tools allows to generate sequences that are similar to real world sequences with respect to certain properties. This will allow to investigate the performance of algorithms under to some extent realistic, yet controlled conditions, and to determine the degree of dependence from parameters of the underlying sequence.
Both tools have an extensible design which allows the integration of new modules for other statistical properties or generating models with the same programming interface.
-
Distributed Shared Memory und Transactional Memory
Raum: 03.11.018
Zeit: Mittwoch, 10.8.2011, 14.00 Uhr
Vortragender: Björn Saballus, Stephan Posselt und Thomas Fuhrmann
-
Improvement Strategies for Iterative Topological Sorting in External Memory
Raum: 03.11.018
Zeit: Mittwoch, 27.7.2011, 14.00 Uhr>
Vortragender: Christoph Flake
-
On the I/O complexity of stencil computations on 2 dimensional grids
Raum: 03.11.018
Zeit: Mittwoch, 6.7.2011, 14.00 Uhr
Vortragender: Philipp Hupp
Over the past years computer architecture has changed and the gap
between floating point performance and memory bandwidth has expanded.
Furthermore the size of datasets increases continuously. Therefore the
bottleneck limiting the performance of many computations seems to be
more and more given by the memory subsystem.
The calculations performed by many numerical tasks, like evaluating an
interpolation function or solving a partial differential equation, can
be modeled by data access patterns, so called stencils. Stencils are
used vastly in numerics and memory efficient algorithms to evaluate them
are known. However, they have not been studied from an theoretical I/O
point of view and the lower bounds are missing.
Here we study a particular stencil, the 5-point stencil which arises
when differential quotients are approximated in two dimensions. Lower
and upper I/O bounds are derived for evaluating the 5-point stencil on a
full grid in a model closely related to the red-blue pebble game of Hong
and Kung.
The research prepares future analysis of stencil computations in higher
dimensions and on sparse grids, a variation of grids that reduce the
number of grid points to tackle high dimensional problems.
-
An Almost Tight Bound for Reordering Buffer Management
Raum: 03.11.018
Zeit: Mittwoch, 25.5.2011, 14.00 Uhr
Vortragender: Harald Räcke
In the reordering buffer problem, we are given an input sequence of
requests for service each of which corresponds to a point in a metric
space. The cost of serving the requests heavily depends on the
processing order. Serving a request induces cost corresponding to the
distance between itself and the previously served request, measured in
the underlying metric space. A reordering buffer with storage capacity
$k$ can be used to reorder the input sequence in a restricted fashion so
as to construct an output sequence with lower service cost. This simple
and universal framework is useful for many applications in computer
science and economics, e.g., disk scheduling, rendering in computer
graphics, or painting shops in car plants.
We present the first non-constant lower bound on the competitive ratio
of determinstic online algorithms for the reordering buffer problem in a
uniform metric. Precisely, we show that any online algorithm for the
problem has a competitive ratio of $\Omega(\sqrt{\log k/\log\logk})$.
We complement this result by presenting a determinstic online algorithm
that obtains a competitive ratio of $O(\sqrt{\log k})$ for the problem.
This improves upon an algorithm by Avigdor-Elgrabli and Rabani [SODA
2010] that obtained a competitive ratio of $O(\log k/\log\logk)$.
-
Tuning Funnelsort for Permuting
Raum: 03.11.018
Zeit: Mittwoch, 18.5.2011, 14.00 Uhr
Vortragender: Yang Guo
Several approaches are known for the task of permuting data in memory. A particular one that is based on funnelsort can be adapted very well to the characteristics of the memory hierarchy and therefore has the potential to perform very well. We compare it to other algorithms with theoretical analysis using an I/O model and with experiments conducted on real hardware.
-
Optimal Hierarchical Decompositions for Congestion Minimization in
Networks
Raum: 03.11.018
Zeit: Mittwoch, 11.5.2011, 13.45 Uhr
Vortragender: Harald Räcke
An oblivious routing protocol makes its routing decisions independent of
the traffic in the underlying network. This means that the path chosen
for a routing request may only depend on its source node, its
destination node, and on some random input. In spite of these serious
limitations it has been shown that there are oblivious routing
algorithms that obtain a polylogarithmic competitive ratios w.r.t. the
congestion in the network (i.e., maximum load of a network link).
We present a new hierarchical decomposition technique that leads to good
oblivious routing algorithms. This decomposition can also be used as a
generic tool for solving a large variety of cut based problems in
undirected graphs. As one example a straightforward dynamic
programming algorithm based on the decomposition gives an O(log
n)-approximation to the Minimum Bisection problem improving on a result
of Feige and Krauthgamer who obtained an approximation ratio of
O(\log^1.5 n).
-
Engineering Architecture Aware Algorithms
- two case studies and some thoughts on Algorithms Engineering
Raum: 03.11.018
Zeit: Mittwoch, 4.5.2011, 13.45 Uhr
Vortragender: Riko Jacob
I will present preliminary results from two ongoing projects, both
regarding memory intensive tasks in (huge) internal memory.
One is asking the question if I/O-efficient (sorting based)
algorithms can outperform the direct algorithm when permuting
several gigabytes of data in internal memory.
The other one reports on an efficient implementation for numerical
computations in high dimensional settings using so called sparse
grids.
Again, the improved implementation is inspired by I/O-efficient algorithms.
Finally, I will try to show how these two examples fit into a more
general theme of using and combining theoretical models and
experiments to find the algorithm and implementation that performs
best on a given hardware.
-
Algorithms and Index Structures for Approximate Pattern Matching
Raum: 03.11.018
Zeit: Mittwoch, 27.04.2011, 13.45 Uhr
Vortragender: Johannes Krugel
In many applications it is necessary to efficiently find a search pattern in a long text, for example while searching DNA databases. Many different index structures can be used to speed up the searches (e.g. q-gram index, suffix tree, suffix array). An extension of this problem is _approximate_ pattern matching where we want to find also those occurrences that contain some errors (spelling mistakes, gene mutations, etc.).
The talk presents three approximate search algorithms we implemented. An experimental comparison shows the strengths and weaknesses of the three algorithms, also compared to an online search.
Furthermore, two advanced index structures will shortly be presented: compressed index structures (with space usage proportional to the size of the compressed text), and DiGeST (a special representation of suffix trees optimized for secondary memory). With our test framework we plan to perform a systematic experimental comparison of the different classes of solutions for approximate pattern matching.
-
Ungleichungen für die Anzahl der Wege in Graphen
Raum: 03.11.018
Zeit: Mittwoch, 20.4.2011, 13.45 Uhr
Vortragender: Hanjo Täubig und Jeremias Weihmann
Wir untersuchen das Wachstum der Anzahl w_k von gerichteten Wegen der Länge
k in ungerichteten Graphen, sowie damit verbundene Ungleichungen.
Wir zeigen, dass es sowohl zusammenhängende bipartite Graphen als auch
unzusammenhängende kreisfreie Graphen gibt, für die die Ungleichung w_0 w_3
>= w_1 w_2 nicht gilt. Weiterhin zeigen wir, dass überraschenderweise die
Ungleichung aber für Bäume gültig ist.
Außerdem demonstrieren wir eine Methode, mit der man für eine gegebene
Gradsequenz entsprechende Bäume mit geringstmöglicher Differenz der beiden
Seiten erzeugen kann (sozusagen worst-case Instanzen bzgl. der Ungleichung).
Wir zeigen weiterhin die Gültigkeit der Ungleichung w_{2a} w_{2(a+b+c)} >=
w_{2a+c} w_{2(a+b)+c} für alle Graphen, was eine Verallgemeinerung der
Ungleichung w_{2a} w_{2b} >= w_{a+b}2 von Dress und Gutman darstellt. Ein
analoges Sandwich-Theorem leiten wir ebenfalls für geschlossene Wege von
einem gegebenen Knoten her.
Weiterhin beweisen wir, dass w_{2l+pk} w_{2l}^{k-1} >= w_{2l+p}^k gilt, was
eine weitere Verallgemeinerung der Dress/Gutman-Ungleichung sowie gleichzeit
eine Verallgemeinerung einer Ungleichung von Erdös und Simonovits darstellt.
Beide neuen Ungleichungen lassen sich direkt in entsprechende Ungleichungen
für Dichten höherer Ordnung übertragen.
Schließlich zeigen wir noch eine Folge unterer Schranken für den größten
Eigenwert der Adjazenzmatrix und beweisen diesbezügliche Monotonieresultate,
auch für eine bereits von Nikiforov publizierte Schranke.
-
Rangieren am Ablaufberg
Raum: 03.11.018
Zeit: Mittwoch, 13.4.2011, 15.15 Uhr
Vortragender: Riko Jacob
Im Güterverkehr der Eisenbahn ist es mitunter zur Auslastung der Fernstrecken notwendig, Züge zu verwenden die aus Waggons mit ähnlichen, aber nicht gleichen, Zielen bestehen. Dies macht Rangiervorgänge notwendig, deren Effizienz (Kosten, erzwungene Verweildauer im Bahnhof) direkt die Attraktivität der erbrachten Transportleistung beeinflussen. Sehr oft wird zum Rangieren ein Ablaufberg genutzt, an dem die Wagen eines Zuges in schneller Abfolge auf mehrere Gleise verteilt und so zu neuen Zügen zusammengestellt werden.
Im Vortrag werde ich zeigen wie derartige Rangiervorgänge durch Binärzahlen kodiert werden können. Dabei führen die Anzahl der verfügbaren Gleise und ihre Länge zu natürliche Einschränkungen der verwendbaren Kodes. Diese Kodierung erlaubt zum einen für bestimmte Situationen optimale Kodes anzugeben, aber auch die NP-Vollständigkeit einer allgemeineren Variante des Optimierungsproblems zu zeigen.
Die vorgestellten Überlegungen sind motiviert aus einer Zusammenarbeit der ETH Zürich mit den Schweizer Bundesbahnen.
