STXXL home page

STXXL : Standard Template Library for Extra Large Data Sets.

The core of STXXL is an implementation of the C++ standard template library STL for external memory (out-of-core) computations, i.e., STXXL implements containers and algorithms that can process huge volumes of data that only fit on disks. While the compatibility to the STL supports ease of use and compatibility with existing applications, another design priority is high performance. [more info]
stxxl layers
The following are some key features of STXXL:
  · Transparent support of parallel disks. The library provides implementations of basic parallel disk algorithms. STXXL is the only external memory algorithm library supporting parallel disks.
  · The library is able to handle problems of very large size (up to dozens of terabytes).
  · Improved utilization of computer resources. STXXL supports explicitly overlapping between I/O and computation. STXXL implementations of external memory algorithms and data structures benefit from overlapping of I/O and computation.
  · Small constant factors in I/O volume. A unique library feature ``pipelining'' can save more than half the number of I/Os performed by many applications.
  · Shorter development times due to well known STL-compatible interfaces for external memory algorithms and data structures. STL algorithms can be directly applied to STXXL containers; moreover the I/O complexity of the algorithms remains optimal in most of the cases.
[more info]

Questions concerning use and development of the STXXL library mail to Roman Dementiev .
STXXL is free, open source, and available under the Boost Software License 1.0
 Platforms supported
  · Linux (kernel >= 2.4.18)
  · SunOS
  · Windows 2000/XP
 Current version
Version 0.9 (9 August 2005) contains an implementation of the lower layers (memory management, disk virtualization, prefetching,...). From the higher layers, (pipelined) sorting, (pipelined) scanning and containers (vectors, stacks, priority queues, maps, queues) are supported. Currently that sums to about 15 thousand lines of code.
 What's new in the latest release
  · STXXL has been ported to Windows. It now can be run under Windows XP and Windows 2000.
  · STXXL can be compiled now by g++ (versions 3.0.x-3.4.x, 4.0.x) and Microsoft Visual C++ 7.1 (.NET)
  · New data structure: I/O efficient FIFO queue
  · Installation manual: [link]
  · Design paper - library overview [pdf] [html]
  · Tutorial (draft) [pdf]
  · Programmer documentation: [doxy]
  · Current stable version (last update:Wed May 30 18:14:06 CEST 2007 ): [tgz] [zip]
  · Older version (0.77 - Linux only): [tgz]
  Ongoing and completed projects using STXXL
  · External Memory Minimum Spanning Trees [project page] [paper (ps)] [paper (pdf)]
  · External Memory Spanning Forests and Connected Components [report] [src tarball]
  · External Memory Suffix Array Construction and Suffix Array Checker [project page] [paper(pdf)] [input instances]
  · Parallel Disk B-Trees
  · External Memory Breadth-First Search (BFS)
D. Ajwani, R. Dementiev, U. Meyer: A Computational Study of External-Memory BFS Algorithms. SODA2006: ACM-SIAM Symposium on Discrete Algorithms (January 2006, Miami, Florida, USA) to appear
R. Dementiev, L. Kettner, P. Sanders: Stxxl: Standard Template Library for XXL Data Sets. ESA2005: 13th Annual European Symposium on Algorithms (October 2005, Palma de Mallorca, Spain) [pdf] (see also the extended version)
R. Dementiev, L. Kettner, P. Sanders: Stxxl: Standard Template Library for XXL Data Sets. Technical Report 2005/18, Fakultät für Informatik, University of Karlsruhe [pdf] [html]
R. Dementiev, J. Kärkkäinen, J. Mehnert, P. Sanders: Better External Memory Suffix Array Construction ALENEX05: Algorithm Engineering and Experiments (January 2005, Vancouver , Canada): [pdf] [input instances]
R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn: Engineering an External Memory Minimum Spanning Tree Algorithm. TSC04: 3rd IFIP International Conference on Theoretical Computer Science (August 24-26, 2004, Toulouse): [ps] [pdf]
R. Dementiev, P. Sanders: Asynchronous Parallel Disk Sorting. In 15th ACM Symposium on Parallelism in Algorithms and Architectures (June 7-9, 2003, San Diego, California, USA): pages 138-148 [pdf]