Florian Kurpicz

Florian Kurpicz

Auto-generated profile, based on publicly available information

Florian Kurpicz

Institute of Theoretical Informatics Karlsruhe Institute of Technology Karlsruhe Germany

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 November 2022
Verified
Book Chapter
Open access
PDF file
FKFlorian Kurpicz
Florian Kurpicz
Bit vectors are fundamental building blocks of succinct data structures used in compressed text indices, e.g., in the form of the wavelet trees. Here, two types of queries are of interest: rank and select queries. In practice, the smallest (uncompressed) rank and select data structure cs-poppy has a space overhead of $$\approx $$ ≈ 3.51 % [Zhou et al. SEA 2013] [26]. Using the same overhead, we present a data structure that can answer queries up to 8 % (rank) and 16.5 % (select) faster compared with cs-poppy.

9 July 2021 in ACM Journal of Experimental Algorithmics
Verified
Journal Article
Open access
PDPatrick Dinklage
Patrick Dinklage
JEJonas Ellert
Jonas Ellert
JFJohannes Fischer
Johannes Fischer
FKFlorian Kurpicz
Florian Kurpicz
MLMarvin Löbel
Marvin Löbel
We present new sequential and parallel algorithms for wavelet tree construction based on a new bottom-up technique. This technique makes use of the structure of the wavelet trees—refining the characters represented in a node of the tree with increasing depth—in an opposite way, by first computing the leaves (most refined), and then propagating this information upwards to the root of the tree. We first describe new sequential algorithms, both in RAM and external memory. Based on these results, we adapt these algorithms to parallel computers, where we address both shared memory and distributed memory settings. In practice, all our algorithms outperform previous ones in both time and memory efficiency, because we can compute all auxiliary information solely based on the information we obtained from computing the leaves. Most of our algorithms are also adapted to the wavelet matrix , a variant that is particularly suited for large alphabets.

1 February 2018 in European Journal of Combinatorics
Verified
Journal Article
Closed access
NKNils Kriege
Nils Kriege
FKFlorian Kurpicz
Florian Kurpicz
PMPetra Mutzel
Petra Mutzel

2 January 2019
Verified
Book Chapter
Closed access
JFJohannes Fischer
Johannes Fischer
FKFlorian Kurpicz
Florian Kurpicz
We present two new distributed suffix array construction algorithms. One of our algorithms requires only half as much memory as its competitor (PSAC) [Flick & Aluru, SC 2015], while achieving similar speed. In practice, we can compute on the same hardware suffix arrays for text twice as large as PSAC. The other algorithm still requires less memory than PSAC but is faster on some instances. As a by-product, we also engineered the first distributed string sorting algorithm. All of our algorithms are tested on text collections of up to 115 GB and running on 1280 cores.

1 January 2020
Verified
Book Chapter
Closed access
PDPatrick Dinklage
Patrick Dinklage
JFJohannes Fischer
Johannes Fischer
FKFlorian Kurpicz
Florian Kurpicz
The wavelet tree (Grossi et al. [SODA, 2003]) is a compact index for texts that provides rank, select, and access operations. This leads to many applications in text indexing, computational geometry, and compression. We present the first distributed memory wavelet tree construction algorithms, which allow us to process inputs that are orders of magnitude larger than what current shared memory construction algorithms can work with. In addition, our algorithms can easily be adapted to compute the wavelet matrix (Claude et al. [Inf. Syst., 47:15–32,2015]), an alternative representation of the wavelet tree. In practice, one of our distributed memory wavelet matrix construction algorithms is the first parallel algorithm that can compute the wavelet matrix for alphabets of arbitrary size.

1 December 2018
Verified
Conference Paper
Closed access
TBTimo Bingmann
Timo Bingmann
SGSimon Gog
Simon Gog
FKFlorian Kurpicz
Florian Kurpicz
The suffix array is the key to efficient solutions for myriads of string processing problems in different application domains, like data compression, data mining, or bioinformatics. With the rapid growth of available data, suffix array construction algorithms have to be adapted to advanced computational models such as external memory and distributed computing. In this article, we present five suffix array construction algorithms utilizing the new algorithmic big data batch processing framework Thrill, which allows scalable processing of input sizes on distributed systems in orders of magnitude that have not been considered before.