panthema (page 4 of 1 2 3 4 5 6 7 8 9)
Example of the Inducing Process

eSAIS - Inducing Suffix and LCP Arrays in External Memory

Posted on 2012-11-19 15:49 by Timo Bingmann at Permlink with 2 Comments. Tags: research stringology stxxl c++

This web page accompanies our conference paper "Inducing Suffix and LCP Arrays in External Memory", which we presented at the Workshop on Algorithm Engineering and Experiments (ALENEX 2013). A PDF of the publication is available from this site as alenex13esais.pdf alenex13esais.pdf or from the online proceedings. The paper was joint work with my colleagues Johannes Fischer and Vitaly Osipov.

Download alenex13esais.pdf

The slides to my presentation of the paper on January 7th, 2013 in New Orleans, LA, USA is available: alenex13esais-slides.pdf alenex13esais-slides.pdf. They contain little text and an example of the eSAIS algorithm with a simplified PQ.

Download alenex13esais-slides.pdf

We have also submitted a full version of the eSAIS paper to a journal. Due to long publication cycles, we make a pre-print of the journal article is available here: esais-preprint.pdf esais-preprint.pdf. The full paper contains more details on the inducing algorithm for the LCP array and additional experimental details.

Download esais-preprint.pdf

Our implementations of eSAIS, the eSAIS-LCP variants, DC3 and DC3-LCP algorithms as described in the paper are available below under the GNU General Public License v3 (GPL).

eSAIS and DC3 with LCP version 0.5.4 (current) updated 2013-12-13
Source code archive:
(includes STXXL 1.4.0)
eSAIS-DC3-LCP-0.5.4.tar.bz2 eSAIS-DC3-LCP-0.5.4.tar.bz2 (1.37 MiB) Browse online
Git repositories Suffix and LCP construction algorithms
git clone https://github.com/bingmann/eSAIS
cd eSAIS; git submodule init; git submodule update
STXXL 1.4.0
git clone https://github.com/stxxl/stxxl

For more information about compiling and testing the implementation, please refer to the README included in the source.

This blog entry continues on the next page ...

The QuadClip Algorithm

Finding Roots of Polynomials by Clipping - Report and Implementation from my Lab Course in Numerical Mathematics

Posted on 2012-03-20 22:29 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university c++

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:

For the lab course I wrote two documents, both in German: one is an abstract Kurzfassung.pdf Kurzfassung.pdf (1 page), which is translated into English below, and the other a short report Ausarbeitung.pdf 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 Slides.pdf, which however are not self-explanatory due to my minimum-text presentation style.

This blog entry continues on the next page ...

Drawing of PG(2,3)

Vervollständigung meiner Seminararbeit in Diskreter Mathematik

Posted on 2011-08-31 20:12 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university

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 Seminararbeit-Singer-Differenzenmengen.pdf (2.79 MiB).

Download Seminararbeit-Singer-Differenzenmengen.pdf

Zusammenfassung

Die Entwicklung von Differenzenmengen in der Design Theorie begann 1938 mit einer algebraischen Untersuchung endlicher projektiver Geometrien von James Singer. Nach Einführung der wichtigsten Grundbegriffe der Design Theorie und projektiver Geometrien werden in dieser Ausarbeitung die beiden Resultate von Singer entwickelt. Die Existenz einer Kollineation mit Periode \frac{n^{d+1}-1}{n-1} führt zur Definition von Differenzenmengen und beide Ergebnisse liefern elegante Konstruktionsverfahren für PG(d,p^k).


Small drawing of a B+ tree

Update Release of STX B+ Tree 0.8.6

Posted on 2011-05-18 12:44 by Timo Bingmann at Permlink with 1 Comments. Tags: c++ stx-btree

After four years I have decided to release an updated version 0.8.6 of the STX B+ Tree C++ Template Classes package. The updated release contains all patches that have accumulated in my inbox over the years. So yes, please send me patches for this project, it is not in vain! Below the highlights on the changes in this release:

I also reran the speed test done back in 2007 on my new hardware and compared the results with the old data. Due to the larger L2 cache sizes in my new Intel Core i7, the B-tree speed-up first starts to show at about 100,000 integer items, rather than 16,000 items with my older Pentium 4. This might also have something to do with the new CPU using 64-bit pointers and thus requiring larger nodes for child references. Read the complete speed test here.

result plot from new speedtest

The updated source code package is available for download from this webpage.


Yet Another Release of digup 0.6.40 - A Digest Updating Tool

Posted on 2011-01-31 20:25 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ utilities

This is yet another release entry of digup. This time, however, it is a major release with lots of new improvements and some old fixes:

For more information and the new version see the digup web page.


Bugfix Release: digup 0.6.30 - A Digest Updating Tool

Posted on 2010-10-03 16:12 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ utilities

Fixed another severe bug in the digup tool: on the amd64 architecture the tool crashed when writing the digest file, thanks goes to Daniel D. for reporting and fixing this bug.

The bug was caused by the variable arguments lists va_list used twice in the fprintfcrc() function. Apparently, on the amd64 platform va_start() and va_end() must be called twice even when passed the list to vsprintf().

For more information and the new version see the digup web page.


Bugfix Release: digup 0.6.27 - A Digest Updating Tool

Posted on 2010-08-20 23:05 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ utilities

Fixed a two bugs in the digup tool: added large file support when compiling the program and fixed a string allocation bug.

This new version enables large file support by using long long variables for size. Furthermore, a string allocation bug was fixed which occured when using -t and -f command line parameters.

For more information and the new version see the digup web page.


Bugfix Release: stx-execpipe 0.7.1 - STX Execution Pipe C++ Library

Posted on 2010-07-30 17:13 by Timo Bingmann at Permlink with 0 Comments. Tags: c++

Fixed a small bug in the stx-execpipe library: add large file support when compiling the library.

This bug switches on the large file support functions. Without this fix a pipeline reading or writing files >2GB will not function properly. The fix is to #define _FILE_OFFSET_BITS 64 when compiling the library's code.

For more information and the source code see the stx-execpipe web page.


Execution pipe with exec() bubbles

Published stx-execpipe 0.7.0 - STX Execution Pipe C++ Library

Posted on 2010-07-18 23:31 by Timo Bingmann at Permlink with 0 Comments. Tags: c++

The STX C++ library series has been extended today with a new installation: the STX Execution Pipe library, in short STX ExecPipe. It is the solution to an issue that I encountered in writing a small backup application. This backup tool collects some file to backup and then calls tar and xz followed by ncftpput.

However, I could not find any useful C++ library that allows convenient chaining of external programs like used in everyday shell piping. This pipe line functionality is based on the system calls fork(), exec() and pipe(), which are not easy to use correctly. After writing some ad-hoc functions to call one or two external programs, I decided to tackle this basic problem once and for all. The result is the stx-execpipe library.

Using the library a C++ program can build a sequence of external programs with command line parameters. These programs are connected by the library just like a shell pipe: stdout of the preceding stage goes into stdin of the next one. The input and output of the whole pipeline can be redirected to a plain fd, a file or saved in a std::string.

One very interesting feature of the library is to insert intermediate processing functions into a pipe line. The data can be intercepted and passed back to the parent process for manipulation or just inspection. This was necessary to calculate the SHA1 digest of a backup tarball simultaneously to uploading it.

For more information and the source code see the stx-execpipe web page.

The following small code snippet exemplifies the flexibility of the stx-execpipe solution:

stx::ExecPipe ep;

// first stage calls tar
std::vector<std::string> tarargs;
tarargs.push_back("tar");
tarargs.push_back("--create");
tarargs.push_back("--verbose");
tarargs.push_back("--no-recursion");
tarargs.push_back("/path/to/some/files");
tarargs.push_back("/path/to/more/files");
ep.add_execp(&tarargs);

// second stage compresses the tarball
ep.add_execp("xz", "-9");

// third stage intercepts data for a SHA1 digest
Sha1Function sha1tar;
ep.add_function(&sha1tar);

// fourth stage sends the tarball via FTP
std::vector<std::string> ftpargs;
ftpargs.push_back("ncftpput");
ftpargs.push_back("-c");
ftpargs.push_back("ftp.upload-to-host.net");
ftpargs.push_back("/path/to/ftpfile.tar.gz");
ep.add_execp(&ftpargs);

if (ep.run().all_return_codes_zero()) {
    std::cout << "Backup upload complete." << std::endl
}
else {
    // error processing...
}

Drawing of cbtreedb tree index structure

Published stx-cbtreedb 0.7.0 - STX Constant B-Tree Database Template Classes

Posted on 2010-04-14 13:34 by Timo Bingmann at Permlink with 0 Comments. Tags: c++

Published yet another C++ template library using a B-tree. This time the solution is a disk-based read-only key-value mapping using a "packed, sequential" B-tree as index structure.

All applications mapping a large number of constant, integral keys to string or data blobs can benefit from this library. The database structure is highly compact and contains self-verification checksums over both key and value areas.

stx-cbtreedb is a direct contender with cdb and tinycdb, which however are based on hash tables and do not retain key proximity. Compared to other full-fledged B-tree implementations like BerkeleyDB or TokyoCabinet, the stx-cbtreedb is very small, faster and the database files have much less overhead due to read-only optimizations.

For more information and the source code see the stx-cbtreedb web page.


Show Page: 1 2 3 4 5 6 7 8 9 Next >
RSS 2.0 Weblog Feed Atom 1.0 Weblog Feed Valid XHTML 1.1 Valid CSS (2.1)
Copyright 2005-2017 Timo Bingmann - Impressum