Engineering von Algorithmen für große Datenmengen

  • Ansprechperson: R. Dementiev, P. Sanders

Wir entwickeln eine Bibliothek von Algorithmen und Datenstrukturen namens Stxxl (stxxl.sourceforge.net), die riesige Datenmengen, die nicht in den Hauptspeicher des Rechners passen, schnell verarbeiten kann. Die Bibliothek implementiert die Schnittstellen der C++ Standardbibliothek und lässt sich in vielen Gebieten anwenden.

Stxxl ist der Grundstein unserer Implementierung eines Algorithmus, der die Volltextindizes von mehreren Gigabyte großen Textsammlungen schnell konstruiert. Im Rahmen des DFG Projekts "Algorithm Engineering for Large Graphs and Memory Hierarchies" haben wir Stxxl erweitert, um enorm große Graphen zu verarbeiten. Im Berichtszeitraum waren wir an der Implementierung eines effizienten Breitensuchalgorithmus beteiligt, der die Basis von vielen anderen Graphalgorithmen ist. Färbung von sehr großen Graphen ist eine andere Anwendung, mit der wir uns beschäftigt haben. Graphfärbung ist eine sehr bedeutende Prozedur für mehrere Einsatzgebiete wie zum Beispiel das Lösen von linearen Gleichungssystemen, Ressourcenplanung, Scheduling und die Kosntruktion und das Testen von VLSI Schaltungen.