FKFlorian Kurpicz

Florian Kurpicz

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Florian Kurpicz has a total of 43 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Faster Wavelet Tree Queries

    by Florian Kurpicz, Angelo Savino, Rossano Venturini

    Introduction: Given a text, rank and select queries return the number of occurrences of a character up to a position (rank) or the position of a character with a given rank (select). These queries have applications in compression, computational geometry, and most notably pattern matching in the form of the backward search, which is the backbone of many compressed full‐text indices. Currently, in practice, for text over non‐binary alphabets, the wavelet tree is probably the most used data structure for rank and select queries. Objective: The goal of this work is to design techniques that accelerate rank, select, and access queries while retaining the space efficiency of both uncompressed and compressed representations. Methods: To this end, we change the underlying tree structure from a binary tree to a quaternary tree and reduce cache misses by approximating rank queries using a predictive model to prefetch all data required for the actual rank query. Finally, we also extend our approach to Huffman‐shaped wavelet trees. Result: Our methods allowed us to achieve speedups of up to a factor of two for access and select queries and up to three for rank queries compared to the SDSL implementation. With Huffman‐shaped wavelet trees, we achieved up to three times faster access and select, and 3.8 times faster rank. In addition, our approach still achieves a reduction of space usage by up to 30% for compressible datasets. Conclusion: By changing the tree structure and using predictive prefetching, we obtain a data structure that substantially outperforms other standard wavelet tree implementations, delivering significantly faster query performance while also occupying compact space.


  • Open Access

    Random Access Segmentation Volume Compression for Interactive Volume Rendering

    by M. Piochowiak, F. Kurpicz, C. Dachsbacher

    Segmentation volumes are voxel data sets often used in machine learning, connectomics, and natural sciences. Their large sizes make compression indispensable for storage and processing, including GPU video memory constrained real‐time visualization. Fast Compressed Segmentation Volumes (CSGV) [PD24] provide strong brick‐wise compression and random access at the brick level. Voxels within a brick, however, have to be decoded serially and thus rendering requires caching of visible full bricks, consuming extra memory. Without caching, accessing voxels can have a worst‐case decoding overhead of up to a full brick (typically over 32.000 voxels). We present CSGV‐R which provide true multi‐resolution random access on a per‐voxel level. We leverage Huffman‐shaped Wavelet Trees for random accesses to variable bit‐length encoding and their rank operation to query label palette offsets in bricks. Our real‐time segmentation volume visualization removes decoding artifacts from CSGV and renders CSGV‐R volumes without caching bricks at faster render times. CSGV‐R has slightly lower compression rates than CSGV, but outperforms Neuroglancer, the state‐of‐the‐art compression technique with true random access, with 2× to 4× smaller data sets at rates between 0.648% and 4.411% of the original volume sizes.

  • Open Access

    Partitioning Trillion Edge Graphs on Edge Devices

    by Adil Chhabra, Florian Kurpicz, Christian Schulz, Dominik Schweisgut, Daniel Seemaier

    Processing large-scale graphs, containing billions of entities, is critical across fields like bioinformatics, high-performance computing, navigation and route planning, among others. Efficient graph partitioning, which divides a graph into sub-graphs while minimizing inter-block edges, is essential to graph processing, as it optimizes parallel computing and enhances data locality. Traditional in-memory partitioners, such as METIS and KaHIP, offer high-quality partitions but are often infeasible for enormous graphs due to their substantial memory overhead. Streaming partitioners reduce memory usage to O(n), where 'n' is the number of nodes of the graph, by loading nodes sequentially and assigning them to blocks on-the-fly. This paper introduces StreamCPI, a novel framework that further reduces the memory overhead of streaming partitioners through run-length compression of block assignments. Notably, StreamCPI enables the partitioning of trillion-edge graphs on edge devices. Additionally, within this framework, we propose a modification to the LA-vector bit vector for append support, which can be used for online run-length compression in other streaming applications. Empirical results show that StreamCPI reduces memory usage while maintaining or improving partition quality. For instance, using StreamCPI, the Fennel partitioner effectively partitions a graph with 17 billion nodes and 1.03 trillion edges on a Raspberry Pi, achieving significantly better solution quality than Hashing, the only other feasible algorithm on edge devices. StreamCPI thus advances graph processing by enabling high-quality partitioning on low-cost machines.

  • Open Access

    Bit-Parallel Wavelet Tree Construction (Abstract) | Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing

    by Patrick Dinklage, Johannes Fischer, Florian Kurpicz, Jan-Philipp Tarnowski

    We present the fastest practical construction algorithms for Huffman-shaped wavelet trees, closing the gap between theory and practice by utilizing SIMD instructions.

  • Open Access

    Brief Announcement: Scalable Distributed String Sorting

    by Florian Kurpicz, Pascal Mehnert, Peter Sanders, Matthias Schimek

    String sorting is an important part of tasks such as building index data structures. Unfortunately, current string sorting algorithms do not scale to massively parallel distributed-memory machines since they either have latency (at least) proportional to the number of processors p or communicate the data a large number of times (at least logarithmic). We present practical and efficient algorithms for distributed-memory string sorting that scale to large p. Similar to state-of-the-art sorters for atomic objects, the algorithms have latency of about p1/k when allowing the data to be communicated k times. Experiments show good scaling behavior on a wide range of inputs on up to 49 152 cores.We achieve speedups of up to 5 over the current state-of-the-art distributed string sorting algorithms.


  • Open Access

    Brief Announcement: (Near) Zero-Overhead C++ Bindings for MPI

    by Demian Hespe, Lukas Hübner, Florian Kurpicz, Peter Sanders, Matthias Schimek, Daniel Seemaier, Tim Niklas Uhl

    The Message-Passing Interface (MPI) and C++ form the backbone of high-performance computing and algorithmic research in the field of distributed-memory computing, but MPI only provides C and Fortran bindings. This provides good language interoperability, but higher-level programming languages make development quicker and less error-prone. We propose novel C++ language bindings designed to cover the whole range of abstraction levels from low-level MPI calls to convenient STL-style bindings, where most parameters are inferred from a small subset of the full parameter set. This allows for both rapid prototyping and fine-tuning of distributed code with predictable runtime behavior and memory management. Using template-metaprogramming, only code paths required for computing missing parameters are generated at compile time, which results in (near) zero-overhead bindings.


  • Open Access

    Faster Wavelet Tree Queries

    by Matteo Ceregini, Florian Kurpicz, Rossano Venturini

    Given a text, rank and select queries return the number of occurrences of a character up to a position (rank) or the position of a character with a given rank (select). These queries have applications in, e.g., compression, computational geometry, and most notably pattern matching in the form of the backward search -- the backbone of many compressed full-text indices. Currently, in practice, for text over non-binary alphabets, the wavelet tree is probably the most used data structure for rank and select queries. In this paper, we present techniques to speed up queries by a factor of two (access and select) up to three (rank), compared to the wavelet tree implementation contained in the widely used Succinct Data Structure Library (SDSL). To this end, we change the underlying tree structure from a binary tree to a 4-ary tree and reduce cache misses by approximating rank queries using a predictive model to prefetch all data required for the actual rank query.


  • Open Access

    Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors

    by 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.


  • Open Access

    Scalable Text Index Construction

    by Timo Bingmann, Patrick Dinklage, Johannes Fischer, Florian Kurpicz, Enno Ohlebusch, Peter Sanders

    We survey recent advances in scalable text index construction with a focus on practical algorithms in distributed, shared, and external memory.


  • Open Access

    Practical Wavelet Tree Construction

    by Patrick Dinklage, Jonas Ellert, Johannes Fischer, Florian Kurpicz, 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.