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]
- M. Rahn, P. Sanders and J. Singler. "Scalable Distributed-Memory External Sorting". 26th IEEE International Conference on Data Engineering (ICDE). 2010. pp. 685-688. [More]
- M. Birn, M. Holtgrewe, P. Sanders and J. Singler. "Simple and Fast Nearest Neighbor Search". Workshop on Algorithm Engineering {&} Experiments (ALENEX). 2010. pp. 43-54. [More]
- N. Leischner, V. Osipov and P. Sanders. "GPU Sample Sort". 24th IEEE International Symposium on Parallel and Distributed Processing (IPDPS). 2010. pp. 1 -10. [More]
- P. Sanders. "Algorithm Engineering -- An Attempt at a Definition". Efficient Algorithms. 2009. pp. 321-340. [More]
- V. H. Batista, D. L. Millman, S. Pion and J. Singler. "Parallel Geometric Algorithms for Multi-Core Computers". 25th Annual Symposium on Computational Geometry (SoCG). 2009. pp. 217-226. [More]
- A. Beckmann, R. Dementiev and J. Singler. "Building A Parallel Pipelined External Memory Algorithm Library". 23rd IEEE International Parallel {&} Distributed Processing Symposium (IPDPS). 2009. [More]
- F. Putze, P. Sanders and J. Singler. "Cache-, Hash- and Space-Efficient Bloom Filters", ACM Journal of Experimental Algorithmics, Vol. 14. 2009, pp. 4.4-4.18. [More]
- V. Osipov, P. Sanders and J. Singler. "The Filter-Kruskal Minimum Spanning Tree Algorithm". 10th Workshop on Algorithm Engineering and Experiments (ALENEX). 2009. pp. 52-61. [More]
- U. Meyer and V. Osipov. "Design and Implementation of a Practical I/O-efficient Shortest Paths Algorithm". 10th Workshop on Algorithm Engineering and Experiments (ALENEX). 2009. pp. 85-96. [More]
- J. Singler and B. Kosnik. "The libstdc++ parallel mode: Software Engineering Considerations". International Workshop on Multicore Software Engineering (IWMSE). 2008. [More]
- L. Frias, J. Singler and P. Sanders. "Single-Pass List Partitioning", Scalable Computing: Practice and Experience, Vol. 9. 2008, pp. 179-184. [More]
- L. Frias, J. Singler and P. Sanders. "Single-Pass List Partitioning". International Workshop on Multi-Core Computing Systems (MuCoCoS). 2008. [More]
- J. Singler, P. Sanders and F. Putze. "The Multi-Core Standard Template Library". Euro-Par 2007: Parallel Processing. 2007. pp. 682-694. [More]
- F. Putze, P. Sanders and J. Singler. "Cache-, Hash- and Space-Efficient Bloom Filters". 6th Workshop on Experimental Algorithms (WEA). 2007. pp. 108-121. [More]
- L. Frias and J. Singler. "Parallelization of Bulk Operations for STL Dictionaries". Workshop on Highly Parallel Processing on a Chip (HPPC). 2007. pp. 49-59. [More]
Projects
- The Multi-Core Standard Template Library (MCSTL)
- Standard Template Library for Extra Large Data Sets (STXXL)