Algorithm Engineering for the Basic Toolbox
Description
Prof. Dr. Peter Sanders; Karlsruhe Institute of Technology
Project website
This project addresses algorithm engineering for basic algorithms and data structures that are the most important building blocks for many computer applications — sorting, searching, graph traversal,. . . . Although this topic is as old as computers science itself, many interesting new results have appeared in recent years and many gaps between theory and practice remain. In particular, many interesting approaches have not been thoroughly tried experimentally. Ever more complex hardware with memory hierarchies and several types of parallel processing requires reﬁned models, new algorithms, and efﬁcient implementations. We plan to incorporate the most successful implementations into reusable software libraries such as the the C++ STL.
Publications
- V. Osipov. "Parallel Suffix Array Construction for Shared Memory Architectures". 19th International Symposium on String Processing and Information Retrieval (SPIRE). 2012. [More]
- V. Osipov and P. Sanders. "n-Level Graph Partitioning". 18th European Symposium on Algorithms (ESA). 2010. [More]
- R. Dementiev and J. Singler. "Libraries". Algorithm Engineering. 2010. [More]
- A. Beckmann, U. Meyer, P. Sanders and J. Singler. "Energy-Efficient Sorting using Solid State Disks". 1st International Green Computing Conference. 2010. [More]
- V. H. Batista, D. L. Millman, S. Pion and J. Singler. "Parallel Geometric Algorithms for Multi-Core Computers", Computational Geometry -- Theory and Applications, Vol. 43. 2010, pp. 663-677. [More]
Projects
- The Multi-Core Standard Template Library (MCSTL)
- Standard Template Library for Extra Large Data Sets (STXXL)