Today, I presented our paper "COBS: A Compact Bit-Sliced Signature Index" at the 26th International Symposium on String Processing and Information Retrieval (SPIRE) 2019 in Segovia, Spain. The full paper is available from this webpage:

paper-COBS-A-Compact-Bit-Sliced-Signature-Index.pdf ,

from the Springer proceedings in LNCS (same content, somewhat differently typeset), and also from arXiv:1905.09624.

I am honored that our paper won the best paper award at SPIRE'19: bestPaperAward.pdf

The slides of my presentation at the SPIRE conference are available here: slides-20191008-cobs-spire.pdf .

The source code and more documentation about COBS can be found by following this link.

Update 2019-11-06: COBS now has a Python interface and can be downloaded from PyPI.

Abstract

Today was the ceremonial graduation day on which new bachelors, masters, and also Dr.s (PhDs in the Anglo-Saxon world) were celebrated who received their degrees from the department of informatics at the Karlsruhe Institute of Technology (KIT) within the last year. This year's graduation day coincided with the 50th anniversary of the introduction of computer science as a field of study and as a diploma degree.

I was among those honoured for completing the Dr. last year, (see my dissertation page). In total 44 freshly minted Dr.s, 292 masters, and 261 bachelors where celebrated today.

Furthermore, I was awarded the Uniserv Research-Prize "Algorithms for Efficient Data-Processing" for the best dissertation in the field of fast algorithms in the academic year 2017/2018 at the KIT department of informatics by the talent committee of the department.

I would like to thank Uniserv for endowing the department and my dissertation with this prize and especially the talent committee for selecting my work. It was a great and pleasant surprise to receive such a notification in the morning email inbox, which as usual contained many "prize and distant inheritance" emails. But on that day one of them was real, and I nearly overlooked it.

My dissertation was the central purpose in my life for many years, and receiving the prize helps me feel the time was well spent and consider it as confirmation of having furthered the field of informatics a tiny bit. It is rare to receive such honours and I am truly grateful.

Uniserv wrote a much longer honorific press release in German.

The road to a Dr. title (PhD in the Anglo-Saxon world) is often long, rough, and twisted. First you have to do original research, produce novel results, publish articles, and then write and ultimately publish a dissertation. Defending your research in the dissertation in front of a panel of professors is one of the final milestones on that journey.

On July 3rd, I successfully defended my dissertation at the Karlsruhe Institute of Technology and the dissertation text has now been published as a book.

Published Dissertation

My final dissertation PDF is available here: dissertation-Bingmann-Scalable-String-and-Suffix-Sorting.pdf .

It has also been published at the KIT library, on arXiv:1808.00963, and finally as a print-on-demand paperback from Amazon.

The published book cover's background shows a list of most common words in the Wikipedia. The words are sorted and their distinguishing prefix is marked in blue. The cover is available as a double-page PDF: dissertation-cover.pdf , and as front and back separately: dissertation-cover-front.pdf and dissertation-cover-back.pdf .

The LaTeX source code for my dissertation is available for download: dissertation-source.zip (791 KiB). The complete text is in one .tex file, all figures (except the creative commons logo) are generated from the LaTeX code.

Dissertation Defense Presentation

The slides of my presentation during the defense are available for download here: dissertation-defense-slides.pdf .

The presentation was only part of the whole defense. My actual slide set also had almost 200 more backup slides, which however were collected from all the other talks already available on this homepage. These backup slides helped greatly in the examination question after the presentation.

After a long exhausting period with many interruptions my diploma thesis in mathematics "On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs" is finalized and submitted. The full abstract of the thesis is shown below, and an additional German abstract is available further down the page.

The final version of the thesis is available here: thesis pdf , and was also uploaded to arXiv.org as 1601.03526.

The underlying problem discussed in the thesis is best explained using a game on a bispanning graph. You can play the game with this Java Applet or using the Java WebStart Launcher (if the Applet does not work). You play Alice's role and want to flip the colors of all edges in the graph. Bob will try to prevent this from happening.

In addition to the thesis itself, the source code of the accompanying computer program is also available. It was used while preparing the thesis to calculate exchanges graphs and to test many hypothesis about bispanning graphs. The program can enumerate all bispanning graphs and their exchange graphs for small numbers of vertices. See the program page for downloadable lists and PDFs of all bispanning graphs for small numbers of vertices.

Abstract

Our paper "Engineering Parallel String Sorting" was accepted for publication in Springer's Algorithmica Journal, and is available online at http://dx.doi.org/10.1007/s00453-015-0071-1.

Compare to our older technical report, the journal edition contains many (minor and major) corrections, additional references and better explanations.

A pre-print version is available here: Engineering-Parallel-String-Sorting.pdf .

Please refer to the main parallel-string-sorting page for details and source code.

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 history about STXXL can be found in the blog post to 1.4.0. Today, the second release of the new 1.4 branch was published:

What's new in 1.4.1 ?

• Integrated support for kernel based asynchronous I/O on Linux (new file type "linuxaio"), which exploits Native Command Queuing (NCQ) if available.
• Merged stxxl::unordered_map branch, which provides a hash map backed by external memory.
• Replaced struct default_completion_handler with a NULL pointer, thus avoiding superfluous new/delete work for each I/O request.
• Added stxxl::external_shared_ptr which is a proxy class to allow use of shared_ptr classes inside stxxl containers.
• Fixing bugs and warnings on 32-bit systems (yes, they still exist).
• Use atomic_counted_object in class file for request reference counting.
• Adding support for MinGW-w64 (64-bit) systems with working SJLJ thread implementations.

See the CHANGELOG for further minor changes.

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.

The project was originally created by Roman Dementiev and Peter Sanders at MPI Informatik in Saarbrücken. It moved to Karlsruhe with them in 2004. After Roman's PhD defense, there was a cooperation with the Algorithm Engineering group at the University of Frankfurt to create better parallel asynchronous sorting. Afterwards, stewardship moved to Frankfurt, where work on flash/SSD drives and various external memory graph algorithms was done.

After a longer stretch without further work, I have decided to take part in future development as a maintainer. This is partly due to my previous experience with it while implement in eSAIS, the external memory suffix and LCP array construction algorithm. And thus, today, the first release of the new 1.4 branch was published:

What's new in 1.4.0 ?

• reorganized source hierarchy into include/ lib/ tests/ examples/ doc/ tools/
• CMake build system for cross-platform compilation
• greatly improved documentation with tutorials and examples
• efficient external matrix operations
• new containers stxxl::sequence and stxxl::sorter
• improved .stxxl disk configuration files and additional options
• combined stxxl_tool of disk benchmarks
• simple examples and skew3 as real-world stream application
• support for Visual Studio 2012 and 2013 without Boost
• important bug fixes in stxxl::queue and stxxl::priority_queue

This post announces the publication of my demo program for integer string sorting algorithms, called "The Sound of Sorting". It both visualizes the internals of sorting algorithms, and generates sound effects from the values being compared!

The demo is implemented using the cross-platform toolkits wxWidgets and SDL, can be executed on Windows, Linux and Mac, and runs in real time.

There are also many videos of the sorting algorithm on my new YouTube channel.

See the Sound of Sorting project page for the demo program and source code, and more information about version 0.6.

This semester I had the pleasure to take part in a lab exercise course supervised by Prof. Thomas Linß at the FernUniversity of Hagen. The objective was to comprehend, implement and evaluate a particular recent advancement in the field of numerical mathematics. My topic was finding the roots of a polynomial by clipping in Bézier representation using two new methods, one devised by Michael Bartoň and Bert Jüttler [1], the other extended from the first by Ligang Liu, Lei Zhang, Binbin Lin and Guojin Wang [2].

My implementation of this topic was done for the lab course in C++ and contains many in themselves interesting sub-algorithms, which are combined into the clipping algorithms for finding roots. These sub-algorithms may prove useful for other purposes, which is the main reason for publishing this website. Among these are:

• Polynomial classes for monomial and Bézier representations: PolynomialStandard and PolynomialBezier.
• Algorithms to convert from monomial to Bézier representation and vice versa: PolynomialStandard::toBezier() and PolynomialBezier::toStandard().
• Evaluation algorithms for both representations: Horner's Schema and the Algorithm of de Casteljau.
• Another version of de Casteljau's Algorithm to split a polynomial in Bézier representation into two parts.
• Jarvis' March aka gift wrapping (run time O(hn)) to calculate the convex hull of the Bézier polygon: PolynomialBezier::getConvexHull().
• Cardano's formulas to find all real roots of any cubic polynomial: PolynomialStandard::findRoots().

For the lab course I wrote two documents, both in German: one is an abstract Kurzfassung.pdf (1 page), which is translated into English below, and the other a short report Ausarbeitung.pdf (6 pages). The report contains a short description of the algorithms together with execution and convergence speed measurements, which verify the original authors experiments. For presenting the lab work I created these Slides.pdf , which however are not self-explanatory due to my minimum-text presentation style.

Heute habe ich meine Seminararbeit in Diskreter Mathematik an der FernUni Hagen vervollständigt. Ich möchte mich bei Prof. Hochstättler bedanken für die erfahrene Leitung und planvolle Einführung in die interessanten Gebiete der Design Theorie und endlicher Geometrien. Die Arbeit ist auf deutsch und unter folgendem Link downloadbar.

Download PDF: Seminararbeit-Singer-Differenzenmengen.pdf (2.79 MiB).

Today I gave the final completion presentation for my diploma thesis. The talk showcased a selection of results published in the thesis. Results and experiments are only sketched, as all further detailed information can be found in the thesis PDF itself.

The talk contains side-by-side comparison plots of feature enhancements made to ns-3 and verifications thereof using ns-2. Furthermore, the EDCA extensions implemented in ns-3 are tested against analytically calculated reference values. In the end, a speed test comparison is done between ns-2 and ns-3, which uses the implemented classes to run an experiment scenario identically on both simulators.

The slides are available as PDFs in following two variants:

Here the table of contents:

1. Thesis Objectives
2. Enhancements
   1. Propagation Loss Models
   2. Reception Criteria
   3. Frame Capture Effect
   4. EDCA Implementation
3. Speed Comparison
4. Conclusion
5. Appendix
   1. Enlarged Plots and Figures
      1. Propagation Loss Models
      2. Reception Criteria
      3. Frame Capture Effect
      4. EDCA Implementation

After a very exhausting last week with lots of writing and little sleep, my diploma thesis is finally complete. The thesis is on enhancements to the 802.11 model and EDCA (enhanced distributed coordination access) QoS (quality of service) extensions in the new network simulator ns-3.

The thesis is written in English and a copy of the abstract and table of contents is located below. There is also a Zusammenfassung in German.

It is available as PDF in different variants:

Beyond the thesis itself, an extra page contains additional material like the source code, plot results and a snapshot of ns-3 at that time.

Shortened Table of Contents

• 1. Introduction
     1. Motivation
     2. Contributions
• I   Related Work
  1. IEEE 802.11
     1. 802: The Big Picture
     2. Outline of 802 and 802.11 Layers
     3. PHY Layers
     4. MAC Layer
  2. The ns-2 Network Simulator
     1. Overview
     2. Problems with 802.11 and Overhaul by DSN
  3. The ns-3 Network Simulator
     1. Design Overview
     2. Architecture of 802.11 Implementation
• II   Enhancements
  1. Propagation Model Enhancements
     1. Propagation in ns-3
     2. Basic Propagation Loss Models
     3. Further Models in ns-3.4
     4. Nakagami-m Fast Fading
     5. Implementation and Verification
  2. PHY Layer Enhancements
     1. Modeling the Transceiver
     2. Implementation of Cumulative Noise
     3. SINR Reception Criterion
     4. Frame Capture Effect
     5. Implementation Issues
     6. BER/PER Reception Criterion
     7. Verification
     8. Discussion of Reception Criteria
  3. EDCA QoS Extensions
     1. Modeling DCF
     2. Extending Model with EDCA
     3. Implementation Issues
     4. Verification
  4. Speed Comparison – ns-2 vs. ns-3
     1. Highway Lanes Scenario
  5. Conclusion
     1. Summary
     2. Future Work
  6. Bibliography
  7. Background
     1. A Note on Decibel
  8. Extra Figures and Tables
     1. 802.11a Convolutional Encoder
     2. Default EDCA Parameters
  9. ns-3 Crash Course
     1. Callbacks
     2. Objects, Ptrs, Attributes and TraceSources
     3. Highway Lanes Scenario Code

For the last three months I have been working intensely on my diploma thesis. The thesis will be about 802.11 enhancements and EDCA QoS extensions in the new network simulator ns-3.

Today I gave my halftime presentation about the current status of my efforts. The talk is composed of a short introduction into ns-3, followed by a detailed discussion of WLAN packet reception criteria and finishes with a review of DCF and how EDCA extends it.

Be warned: many slides are not all self-explanatory and therefore less suitable as a casual introduction into the topics. They are slides meant for presentation.

The slides are available as PDFs in following three variants:

Here the table of contents:

1. ns-3 Basics
   1. Introduction
   2. Showcase: Design Patterns
   3. Current State
2. Wifi in ns-3
   1. State of 802.11
   2. PHY Layer
   3. Signals, Noise and Interference
   4. Short Recapitulation of DCF
   5. QoS with EDCA
3. Conclusion

Following up on the technical report, today Dimitar and myself gave a 70min presentation on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation. It finished my work for the NetFundamentals seminar, which was organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. The seminar was very profound and extensively dug into the mathematics of six fundamental networking papers. Besides that it was great fun and opened some new horizons.

Our presentation can be downloaded as PDF (553 KB), with two slides per page or even with four per page.

Furthermore our listeners were given an equation sheet (139 KB) to aid them in following the many formulas.

Today the technical report on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation was finished. It is part of my work for the NetFundamentals seminar organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. In the seminar six of the computer science papers most worth reading are reviewed and presented. The technical report was written by Dimitar Yordanov and myself and a presentation will follow.

The technical report can be downloaded as PDF (470 KB)

As promised the source code to SDIOS06 was released under the GPL.

SDIOS06 is a toy operating system developed during the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. It was designed and written by Timo Bingmann, Matthias Braun, Torsten Geiger and Andreas Mähler. Two games were ported to a custom SDL implementation using the VMware "hard"-ware: SDLjump and SuperTux. For more information and screenshots see my blog entry 20060727-SDI-Demo.

The source code archive was published on the L4Ka.org page: http://www.l4ka.org/86.php

A local copy of the source archive (7.4 MB) is available as well. The README file contains a great deal of information about SDIOS06's design and modules. The complete source code can be browsed on the web.

To make demonstration as easy as possible a ready-to-run binary vmware image (3.8 MB) can be downloaded. The image contains SDIOS06 installed on a virtual vmware disk image. The VMware image can be run using the free VMware Player.

At the University of Karlsruhe it is common to give a concluding talk after finishing a study thesis (Studienarbeit). I presented my study thesis "Visualisation of Very Large Graphs" today at the mid-day seminar of the Theoretical Computer Science Group. The slides of the talk are available as PDFs below:

studythesis-talk-visualisation.pdf (1.6 MB) - also available with two slides per page (1.6 MB)or four slides per page (1.6 MB).

During the talk I showed a movie, in which a r-tree of the autobahnen of Germany is constructed incrementally. I actually produced two movies for this purpose: in the first the edges are added in a given sequential order and in the second the order is randomized. Both movies are encoded using transcode and the XviD codec.

Sequential Movie (3.6 MB)
Randomized Movie (5.1 MB)

The talk was received very well, and I may continue in this field with my diploma thesis.

The visualisation library is used by a route planning algorithm developed at the Theoretical Computer Science Group. By integrating my study thesis it was possible to create a Java web applet which animates the route planning algorithm. The Java applet is currently available at http://algo2.iti.uni-karlsruhe.de/schultes/hwy/demo/.

Für meinen morgigen Vortrag zur Studienarbeit, habe ich (viel zu) lange nach einem vektor-gezeichneten Logo der Univerisität Karlsruhe (TH) gesucht. Es war nur sehr schwer eines zu finden. Aus einem nach langen Stöbern gefundenen PDF habe ich dann folgende SVG, PDF und EPS Grafiken mit Inkscape erzeugt, die bestimmt jemand anderem etwas Mühe ersparen:

	SVG	SVG (Inkscape)	EPS	PDF
	SVG	SVG (Inkscape)	EPS	PDF

Hinweis: Die Grafiken sind keineswegs offiziell oder sonst wie von der Univerität bereitgestellt.

Today was the final demo presentation day for the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. Goal of the course was to implement a simple operating system on top of the L4 microkernel, which is developed at the Group.

Our practical course group was one of the two groups to demonstrate a working system on the last day of the semester. The presented operating system contained following basic components:

• An initial root task,
• a pager (memory server and task server combined) creating virtual address spaces,
• a root name server for servers to register their facilities,
• a minix file system server which extends the name space to files,
• a (virtual) console server reading keyboard input and writing to the screen buffer,
• and a limited shell with two utility programs: ls and cat.

Furthermore we utilized the VMWare video "card" to enable graphics output. The "hardware" is well documented in the source code to the X11 video driver contributed by VMWare.

The frame buffer and keyboard input was linked up to a ported SDL implementation. After adding a lot of POSIX library function calls like fopen, opendir and getenv, it was possible to compile our favourite games: SDLjump and SuperTux. Both run very well on our operating system from scratch project.

Some screenshots of the shell, sdijump and supertux are available. In future the whole source code and compiled binary images may become available

A big thank you to my friends Matthias Braun, Torsten Geiger and Andreas Mähler, who made this practical work possible and especially fun!

Heute habe ich meine Studienarbeit "Visualisierung sehr großer Graphen" am Institut für Theoretische Informatik fertig gestellt und abgegeben. Die Studienarbeit ist eine 3-4 monatige wissenschaftliche Arbeit und dient als Vorbereitung auf die Diplomarbeit.

Die Studienarbeit kann zum Durchlesen als PDF (2,4 MB) herunter geladen werden. Auf diesen Abschnitt folgenden die deutsche und englische Zusammenfassung der Arbeit. Weiter gibt es eine Version zum Ausdrucken (PDF 15,3 MB) mit einer hochauflösenden Vektorgraphik im Anhang.

As part of my work for the SDI Lab work this summer, I held a short talk about how to design a name service in a multi-server operating system like L4.

The slides are available here:

Here the table of contents:

1. Goals
2. Name Catalogs
   1. Object Representation
   2. Catalogs
3. IDL Interfaces
   1. Resolve Interface
   2. Bind Interface
4. Extension / Ideas

Hier findet man noch die alte Homepage, welche ich im WS2005 für mein Tutorium in Info3 gemacht habe.

Dort konnten meine Tutoranden ihren Punktestand und eventuelle Neuigkeiten abfragen.

Zum Abschluss der Tutorien von Informatik 2 im Sommersemester 2005 haben die Tutoren zusammen eine Probeklausur erstellt. Diese wurde im letzten Tutorium geschrieben und anschließend einige Lösungshinweise zu den schwierigeren Aufgaben gegeben.

Kopie der ursprünglichen Veröffentlichung:

Im Sommersemester 2005 habe ich am Praktikum "Real-Life Programming" am IPD Lehrstuhl der UniKa teilgenommen. Hier platt die Beschreibung von der Homepage zitiert:

In diesem Zusammenhang haben zwei Komilitonen und ich einen Vortrag über "Objekt-orientiertes Programmieren in C" (ohne ++) ausgearbeitet und gehalten. Weiteres Schwerpunktthema war die Darstellung von C++ in Maschine, also wie der C++ Übersetzer dann die Klassen abbildet.

Hier noch ein Auszug des Inhaltsverzeichnisses:

1. Objekt-Orientierte Konzepte
2. OO in C
   • Kapselung und Geheimnisprinzip
   • Vererbung und Polymorphie
   • Generiztiät
3. Darstellung von C++ in Maschine
   • vtable
   • Name-Mangling
   • Run-Time-Type Information (RTTI)

Diese Folien geben einen kompetenten Überblick über den Themenbereich.