223 Search Results for "Sanders, Peter"

Volume

LIPIcs, Volume 173

28th Annual European Symposium on Algorithms (ESA 2020)

ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference)

Editors: Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders

Artifact
Software
DOI: 10.4230/artifacts.26961
Mallob

Authors: Dominik Schreiber, Peter Sanders, Niccolò Rigi-Luperti, and Ruben Götz

Abstract
Cite as

Dominik Schreiber, Peter Sanders, Niccolò Rigi-Luperti, Ruben Götz. Mallob (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26961,
   title = {{Mallob}}, 
   author = {Schreiber, Dominik and Sanders, Peter and Rigi-Luperti, Niccol\`{o} and G\"{o}tz, Ruben},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:63e95b4ba914b33387dbf6e31babbc7b9c3904dc;origin=https://github.com/domschrei/mallob;visit=swh:1:snp:d171a3816db9a89fb89fd452be5b629b191c908c;anchor=swh:1:rev:745c357849212f4dfc33debecac44103a83e5a52}{\texttt{swh:1:dir:63e95b4ba914b33387dbf6e31babbc7b9c3904dc}} (visited on 2026-07-16)},
   url = {https://github.com/domschrei/mallob},
   doi = {10.4230/artifacts.26961},
}
Document
DOI: 10.4230/LIPIcs.SAT.2026.17
A Natively Parallel Proof Framework for Clause-Sharing SAT Solving

Authors: Ruben Götz, Michael Dörr, and Dominik Schreiber

Published in: LIPIcs, Volume 377, 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)

Abstract
Unsatisfiability proofs are valuable artifacts in propositional satisfiability (SAT) since they can provide correctness guarantees and thus complete trust in reported results. In powerful parallel and distributed clause-sharing SAT solvers, existing proof technology either funnels all solver threads' relevant reasoning steps into a single proof file, which leads to scalability problems for large setups and long running times, or checks proof information in parallel in real-time, which is fully scalable but leaves no persistent artifact. We suggest an alternative approach to achieve the best of both worlds. Specifically, we consider parallel proof files that are logged and also checked in parallel. To this end, we introduce PalRUP - an LRUP-based proof format and a bottleneck-free, decentralized parallel checking procedure that only uses the (parallel) file system and is composed of a set of small, sequential trusted components. In evaluations on up to 3072 cores, we observe that our approach allows for low-overhead proof logging during solving and substantially outscales prior proof producing approaches in terms of checking performance.
Cite as

Ruben Götz, Michael Dörr, and Dominik Schreiber. A Natively Parallel Proof Framework for Clause-Sharing SAT Solving. In 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 377, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gotz_et_al:LIPIcs.SAT.2026.17,
  author =	{G\"{o}tz, Ruben and D\"{o}rr, Michael and Schreiber, Dominik},
  title =	{{A Natively Parallel Proof Framework for Clause-Sharing SAT Solving}},
  booktitle =	{29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-431-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{377},
  editor =	{Ignatiev, Alexey and Szeider, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2026.17},
  URN =		{urn:nbn:de:0030-drops-263239},
  doi =		{10.4230/LIPIcs.SAT.2026.17},
  annote =	{Keywords: Satisfiability, Proofs, Distributed computing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.5
BuffCut: Prioritized Buffered Streaming Graph Partitioning

Authors: Linus Baumgärtner, Adil Chhabra, Marcelo Fonseca Faraj, and Christian Schulz

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Streaming graph partitioners enable resource-efficient and massively scalable partitioning, but one-pass assignment heuristics are highly sensitive to stream order and often yield substantially higher edge cuts than in-memory methods. We present BuffCut, a buffered streaming partitioner that narrows this quality gap, particularly when stream ordering is adversarial, by combining prioritized buffering with batch-wise multilevel assignment. BuffCut maintains a bounded priority buffer to delay poorly informed decisions and regulate the order in which nodes are considered for assignment. It incrementally constructs high-locality batches of configurable size by iteratively inserting the highest-priority nodes from the buffer into the batch, effectively recovering locality structure from the stream. Each batch is then assigned via a multilevel partitioning algorithm. Experiments on diverse real-world and synthetic graphs show that BuffCut consistently outperforms state-of-the-art buffered streaming methods. Compared to the strongest prioritized buffering baseline, BuffCut achieves 20.8% fewer edge cuts while running 2.9× faster and using 11.3× less memory. Against the next-best batched method, it reduces edge cut by 15.8% with only modest overheads of 1.8× runtime and 1.09× memory.
Cite as

Linus Baumgärtner, Adil Chhabra, Marcelo Fonseca Faraj, and Christian Schulz. BuffCut: Prioritized Buffered Streaming Graph Partitioning. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baumgartner_et_al:LIPIcs.SEA.2026.5,
  author =	{Baumg\"{a}rtner, Linus and Chhabra, Adil and Faraj, Marcelo Fonseca and Schulz, Christian},
  title =	{{BuffCut: Prioritized Buffered Streaming Graph Partitioning}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.5},
  URN =		{urn:nbn:de:0030-drops-260097},
  doi =		{10.4230/LIPIcs.SEA.2026.5},
  annote =	{Keywords: graph partitioning, streaming, online, buffered, prioritized partitioning}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.13
Practical Parallel Block Tree Construction

Authors: Robert Clausecker, Florian Kurpicz, and Etienne Palanga

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The block tree [Belazzougui et al., J. Comput. Syst. Sci. '21] is a compressed representation of a length-n text that supports access, rank, and select queries while requiring only O(z log n/z) words of space, where z is the number of Lempel-Ziv factors of the text. In other words, its space requirements are asymptotically comparable to those of the compressed text itself. In practice, block trees offer query performance comparable to that of state-of-the-art compressed rank and select indices. However, their construction is significantly slower, and the fastest known construction algorithms additionally require a significant amount of working memory. To address these limitations, we propose fast and lightweight parallel algorithms for the efficient construction of block trees. Our algorithm achieves similar construction speed than the currently fastest block tree construction algorithm on a single core and is up to eight times faster using 64 cores, while requiring an order of magnitude less memory. Overall, we achieve a speedup of up to 15.5 on 64 cores, which is in line with the parallel construction of the Lempel-Ziv compression.
Cite as

Robert Clausecker, Florian Kurpicz, and Etienne Palanga. Practical Parallel Block Tree Construction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{clausecker_et_al:LIPIcs.SEA.2026.13,
  author =	{Clausecker, Robert and Kurpicz, Florian and Palanga, Etienne},
  title =	{{Practical Parallel Block Tree Construction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.13},
  URN =		{urn:nbn:de:0030-drops-260175},
  doi =		{10.4230/LIPIcs.SEA.2026.13},
  annote =	{Keywords: block tree, shared memory, compression, SIMD, Karp-Rabin fingerprints}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.10
Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries

Authors: Gabriel Carmona and Filippo Lari

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Tree compression is a well-studied area that aims at reducing the size of tree representations by exploiting different forms of repetition. While the underlying theory is well understood, there is still significant room for experimental investigation, particularly in the design of compressed representations that efficiently support navigational queries. In this work, we address the problem of designing, engineering, and experimentally evaluating a compression technique for unlabeled binary trees based on repeated subtrees, yielding the minimal Directed Acyclic Graph (DAG) of the input tree. We show how this representation can be computed in linear time and space directly from a succinct encoding of the tree, and how it can be augmented with compact auxiliary data structures to support Lowest Common Ancestor (LCA) queries. When the input tree is the Cartesian tree of an array, LCA queries can be used to answer Range Minimum Queries (RMQs) on the underlying array. This is particularly relevant in the encoding model, where the array is not accessible at query time, and a space lower bound of 2n-O(log n) bits is known. Given the numerous applications of RMQs, we use this problem as a case study for our experimental evaluation, testing our implementation on 11 real-world datasets. Our experiments show that, on almost every dataset, our implementation is the most space-efficient, using as few as 0.11n bits, while still delivering practical query times.
Cite as

Gabriel Carmona and Filippo Lari. Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{carmona_et_al:LIPIcs.SEA.2026.10,
  author =	{Carmona, Gabriel and Lari, Filippo},
  title =	{{Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.10},
  URN =		{urn:nbn:de:0030-drops-260140},
  doi =		{10.4230/LIPIcs.SEA.2026.10},
  annote =	{Keywords: tree compression, range minimum query, compact data structures, algorithm engineering, experimental evaluation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.24
ZOR Filters: Fast and Smaller Than Fuse Filters

Authors: Antoine Limasset

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Probabilistic membership filters support fast approximate membership queries with controlled false-positive probability ε and are widely used across storage, analytics, networking, and bioinformatics [Chang et al., 2008; Niv Dayan et al., 2018; Broder and Mitzenmacher, 2004; Harris and Medvedev, 2020; Marchet and Limasset, 2023; Chikhi et al., 2025; Hernandez-Courbevoie et al., 2025]. In the static setting, low-overhead methods such as XOR, Fuse, and BuRR have been proposed [Graf and Lemire, 2020; Graf and Lemire, 2022; Dillinger et al., 2022; Ulrich and Renard, 2023]. Among these, Fuse filters are known for near-optimal query throughput. For XOR/Fuse-style peeling constructions, however, build success is only high probability, which complicates deterministic builds. We introduce ZOR filters, a deterministic continuation of XOR/Fuse-style constructions that guarantees termination while preserving the same XOR-based query mechanism. ZOR replaces restart-on-failure with deterministic peeling that abandons a small fraction of keys, and restores false-positive-only semantics by storing the remainder in a compact auxiliary structure. In our experiments, the abandoned fraction drops below 1% for moderate arity (e.g., N ≥ 5), so the auxiliary handles a negligible fraction of keys. As a result, ZOR filters can be substantially more memory-efficient than Fuse filters, with overhead below 1%, while not yet matching the near-optimal overhead of BuRR (below 0.1%). In query performance, ZOR-pure is close to Fuse and faster than BuRR on positive queries, while the complete interleaved variant trades additional negative-query latency for deterministic continuation. Relative to optimised Fuse/BuRR implementations [Graf and Lemire, 2022; Dillinger et al., 2022], the current ZOR prototype remains slower in construction because deterministic peeling requires explicit incidence handling; reducing this construction gap is an important direction for future work.
Cite as

Antoine Limasset. ZOR Filters: Fast and Smaller Than Fuse Filters. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{limasset:LIPIcs.SEA.2026.24,
  author =	{Limasset, Antoine},
  title =	{{ZOR Filters: Fast and Smaller Than Fuse Filters}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.24},
  URN =		{urn:nbn:de:0030-drops-260281},
  doi =		{10.4230/LIPIcs.SEA.2026.24},
  annote =	{Keywords: Data structure, Approximate Set Membership, Static filter}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.25
Engineering Learned Heuristics to Improve Clustering for Multilevel Graph Partitioning

Authors: Simeon Schrape, Nikolai Maas, Kenneth Langedal, and Daniel Seemaier

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Balanced Graph Partitioning is a classical optimization problem where quality guarantees are computationally infeasible, and practical solvers therefore rely on manually engineered heuristics. Yet, the problem has also proven difficult for approaches that rely heavily on machine learning - especially since applications often need to partition graphs of huge scale in a short amount of time. Instead, we demonstrate how to achieve practical improvements with a more careful approach that uses machine learning to improve heuristic decisions within the state-of-the-art solver Mt-KaHyPar. We use a pre-trained neural network to predict a score for each edge, which then guides clustering decisions in the first phase of the partitioning (the coarsening). Combined with corresponding adjustments to the clustering algorithm and an efficient implementation of the neural network logic, we improve the overall solution quality while preserving the efficiency and scalability of the original algorithm. Our detailed evaluation on more than 180 graphs shows an average quality improvement of 2% on a class of graphs with beneficial properties, and unchanged quality on all remaining graphs. Moreover, our improvements generalize to a set of instances from the literature that are much larger than the graphs used during training.
Cite as

Simeon Schrape, Nikolai Maas, Kenneth Langedal, and Daniel Seemaier. Engineering Learned Heuristics to Improve Clustering for Multilevel Graph Partitioning. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 25:1-25:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schrape_et_al:LIPIcs.SEA.2026.25,
  author =	{Schrape, Simeon and Maas, Nikolai and Langedal, Kenneth and Seemaier, Daniel},
  title =	{{Engineering Learned Heuristics to Improve Clustering for Multilevel Graph Partitioning}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{25:1--25:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.25},
  URN =		{urn:nbn:de:0030-drops-260295},
  doi =		{10.4230/LIPIcs.SEA.2026.25},
  annote =	{Keywords: Graph Partitioning, Graph Algorithms, Machine Learning, Neural Networks}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.26
Engineering Algorithms for Dynamic Greedy Set Cover

Authors: Amitai Uzrad

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
In the dynamic set cover problem, the input is a dynamic universe of elements and a fixed collection of sets. As elements are inserted or deleted, the goal is to efficiently maintain an approximate minimum set cover. While the past decade has seen significant theoretical breakthroughs for this problem, a notable gap remains between theoretical design and practical performance, as no comprehensive experimental study currently exists to validate these results. In this paper, we bridge this gap by implementing and evaluating four greedy-based dynamic algorithms across a diverse range of real-world instances. We derive our implementations from state-of-the-art frameworks - such as [GKKP(STOC'17); SU(STOC'23); SUZ(FOCS'24)] - which we simplify by identifying and modifying intricate subroutines that optimize asymptotic bounds but hinder practical performance. We evaluate these algorithms based on solution quality (set cover size) and efficiency, which comprises update time - the time required to update the solution following each insertion/deletion - and recourse - the number of changes made to the solution per update. Each algorithm uses a parameter β to balance quality against efficiency; we investigate the influence of this tradeoff parameter on each algorithm and then perform a comparative analysis to evaluate the algorithms against each other. Our results provide the first practical insights into which algorithmic strategies provide the most value in realistic scenarios.
Cite as

Amitai Uzrad. Engineering Algorithms for Dynamic Greedy Set Cover. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{uzrad:LIPIcs.SEA.2026.26,
  author =	{Uzrad, Amitai},
  title =	{{Engineering Algorithms for Dynamic Greedy Set Cover}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.26},
  URN =		{urn:nbn:de:0030-drops-260308},
  doi =		{10.4230/LIPIcs.SEA.2026.26},
  annote =	{Keywords: Dynamic graphs, set cover, recourse}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.20
QuadRank: Engineering a High Throughput Rank

Authors: Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Motivation. Given a text, a query rank(q, c) counts the number of occurrences of character c among the first q characters of the text. Space-efficient methods to answer these rank queries form an important building block in many succinct data structures. For example, the FM-index [Ferragina and Manzini, 2000] is a widely used data structure that uses rank queries to locate all occurrences of a pattern in a text. In bioinformatics applications, the goal is usually to process large inputs as fast as possible. Thus, data structures should have high throughput when used with many threads. Contributions. We first survey existing results on rank data structures. For the σ = 2 binary alphabet, we then develop BiRank, which has 3.28% space overhead. BiRank merges the central ideas of two recent papers: (1) we interleave (inline) offsets in each cache line of the underlying bit vector [Laws et al., 2024], reducing cache misses, and (2) these offsets are to the middle of each block so that only half of each needs popcounting [Gottlieb and Reinert, 2025]. In QuadRank (14.4% overhead), we extend these techniques to the σ = 4 (DNA) alphabet. Both data structures typically require only a single cache miss per query, making them highly suitable for high-throughput and memory-bound settings. To enable efficient batch-processing, we support prefetching the cache lines required to answer upcoming queries. Results. BiRank and QuadRank are around 1.5× and 2× faster than similar-overhead methods that do not use interleaving. Prefetching gives an additional 2× speedup, at which point the dual-channel DDR4 RAM bandwidth becomes a hard limit on the total throughput. With prefetching, both methods outperform all other methods apart from SPIDER [Laws et al., 2024] by 2×. When using QuadRank with prefetching in a toy count-only FM-index, QuadFm, this results in a smaller size and up to 4× speedup over Genedex, a state-of-the-art batching FM-index implementation. Conclusion. Optimizing data structures for high throughput, by minimizing cache misses and branch-misses and adding support for prefetching, can result in significant speedups when benchmarks are adjusted accordingly.
Cite as

Ragnar Groot Koerkamp. QuadRank: Engineering a High Throughput Rank. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp:LIPIcs.SEA.2026.20,
  author =	{Groot Koerkamp, Ragnar},
  title =	{{QuadRank: Engineering a High Throughput Rank}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.20},
  URN =		{urn:nbn:de:0030-drops-260248},
  doi =		{10.4230/LIPIcs.SEA.2026.20},
  annote =	{Keywords: Rank, Succinct Data Structures, Cache Performance, Prefetching}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.19
Breaking 2-Cores for Invertible Bloom Lookup Tables by Structure Prediction

Authors: Vojtěch Gaďurek and Pavel Veselý

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Invertible Bloom Lookup Tables (IBLTs) provide a highly space-efficient way to reconstruct small sets resulting from a large number of insertions and deletions of elements, such as in streaming or distributed computation of the symmetric difference of similar sets. The set recovery process succeeds if the IBLT size is at least 1.22 times the size of the encoded set; otherwise, a 2-core occurs with high probability in the corresponding random hypergraph. However, the sets in practice often exhibit structure that allows for performance beyond worst-case bounds. Here, we demonstrate that structured sets - such as the k-mers in the symmetric difference of two closely related genomes - can be recovered with an IBLT of significantly smaller size. We achieve this by employing structure-aware predictors to break the 2-core whenever the recovery process gets stuck. Importantly, this approach modifies only the decoding procedure, leaving the IBLT data structure unchanged. We prove that even a weak matching-based predictor enables the recovery of 27% more elements than the nominal IBLT size. Equipped with simple predictors for k-mers of genomic datasets, we demonstrate that recovering a symmetric difference with high probability can be done with an IBLT of size only 66% of the encoded set size for k = 31, improving the space efficiency by almost a factor of two. Moreover, we design an improved method for k-mers with large k that combines subsampling with nearly perfect prediction via fingerprinting and achieves a scaling property, requiring only O(M log M) bits for recovering M k-mers, instead of Θ(k⋅M) bits of the standard IBLT. Overall, our results highlight the possibility of significant space-efficiency improvements for IBLTs on datasets with predictable structure.
Cite as

Vojtěch Gaďurek and Pavel Veselý. Breaking 2-Cores for Invertible Bloom Lookup Tables by Structure Prediction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gadurek_et_al:LIPIcs.SEA.2026.19,
  author =	{Ga\v{d}urek, Vojt\v{e}ch and Vesel\'{y}, Pavel},
  title =	{{Breaking 2-Cores for Invertible Bloom Lookup Tables by Structure Prediction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.19},
  URN =		{urn:nbn:de:0030-drops-260237},
  doi =		{10.4230/LIPIcs.SEA.2026.19},
  annote =	{Keywords: Invertible Bloom Lookup Table, symmetric difference, k-mer sets}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.16
Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings

Authors: Patrick Dinklage

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The LZ77 [Lempel and Ziv, 1977] compression scheme is ubiquitous: it lies at the core of everyday general-purpose standard compressors such as gzip or zstd, but also behind the scenes of many applications such as the compression of payloads transmitted in networks. Computing the exact LZ77 parsing is largely solved in theory: it can be done in sublinear time and space, in compressed space and in external memory, to name but some scenarios. However, these approaches are often impractical for everyday use due to their intensive time or space requirements. Standard compressors tackle this issue by introducing heuristics that go hand in hand with sophisticated encoding schemes to achieve very good compression fast and in small space, however, they only have a local view (e.g., a sliding window) on the input, potentially missing out on long-range repetitions that may be located far apart from one another. In this work, we design and implement - in C++ and leveraging shared-memory parallelism - compression pipelines that first precompress the input using an approximate LZ77 parsing taking care of long-range repetitions. This then serves as an assist to standard compressors for producing a succinct encoding of the remaining short and local repetitions. Similar approaches have been considered by [Kosolobov et al., 2020] and [Nalbach, 2024], respectively using Relative Lempel Ziv [Kuruppu et al. 2010] or the string synchronizing set [Kempa & Kociumaka, 2019]. We fill a gap taking the route via the prefix-free parsing [Boucher et al., 2019], using an intermediate result of [Hong et al., 2023]. On large repetitive inputs of tens of gigabytes, our pipelines are orders of magnitudes faster than the state of the art for computing the exact LZ77 parsing, use space less than the input size and still - despite producing more phrases - achieve the best overall compression in comparison to related work.
Cite as

Patrick Dinklage. Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dinklage:LIPIcs.SEA.2026.16,
  author =	{Dinklage, Patrick},
  title =	{{Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.16},
  URN =		{urn:nbn:de:0030-drops-260204},
  doi =		{10.4230/LIPIcs.SEA.2026.16},
  annote =	{Keywords: compression, algorithm engineering, parallel computation}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.2
Near-Real-Time Solutions for Online String Problems

Authors: Dominik Köppl and Gregory Kucherov

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
Based on the Breslauer-Italiano online suffix tree construction algorithm (2013) with double logarithmic worst-case guarantees on the update time per letter, we develop near-real-time algorithms for several classical problems on strings, including the computation of the longest repeating suffix array, the (reversed) Lempel-Ziv 77 factorization, and the maintenance of minimal unique substrings, all in an online manner. Our solutions improve over the best known running times for these problems in terms of the worst-case time per letter, for which we achieve a poly-log-logarithmic time complexity, within a linear space. Best known results for these problems require a poly-logarithmic time complexity per letter or only provide amortized complexity bounds. As a result of independent interest, we give conversions between the longest previous factor array and the longest repeating suffix array in space and time bounds based on their irreducible representations, which can have sizes sublinear in the length of the input string.
Cite as

Dominik Köppl and Gregory Kucherov. Near-Real-Time Solutions for Online String Problems. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koppl_et_al:LIPIcs.CPM.2026.2,
  author =	{K\"{o}ppl, Dominik and Kucherov, Gregory},
  title =	{{Near-Real-Time Solutions for Online String Problems}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.2},
  URN =		{urn:nbn:de:0030-drops-259287},
  doi =		{10.4230/LIPIcs.CPM.2026.2},
  annote =	{Keywords: online algorithms, string algorithms, suffix tree, real-time computation, Lempel-Ziv factorization, minimal unique substrings}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.3
Computing k-mers in Graphs

Authors: Jarno N. Alanko and Máximo Pérez-López

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
We initiate the study of computational problems on k-mers (strings of length k) in labeled graphs. As a starting point, we consider the problem of counting the number of distinct k-mers found on the walks of a graph. We establish that this is #P-hard, even on connected deterministic DAGs. However, in the class of deterministic Wheeler graphs (Gagie, Manzini, and Sirén, TCS 2017), we show that distinct k-mers of such a graph W = (V, E) can be counted using O(|W|k) or O(n⁴ log k) arithmetic operations, where n = |V|, m = |E| and |W| = n+m. The latter result uses a new generalization of the technique of prefix doubling to Wheeler graphs. To generalize our results beyond Wheeler graphs, we discuss ways to transform a graph into a Wheeler graph in a manner that preserves the k-mers. As an application of our k-mer counting algorithms, we construct a representation of the de Bruijn graph of the k-mers that occupies O(n_k + |W|k log(max_{1 ≤ 𝓁 ≤ k} n_𝓁) + σlog m) bits of space, where n_𝓁 is the number of distinct 𝓁-mers in the Wheeler graph, and σ is the size of the alphabet. We show how to construct it in the same time complexity. Given that the Wheeler graph can be exponentially smaller than the de Bruijn graph, for large k this provides a theoretical improvement over previous de Bruijn graph construction methods from graphs, which must spend Ω(k) time per k-mer in the graph.
Cite as

Jarno N. Alanko and Máximo Pérez-López. Computing k-mers in Graphs. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alanko_et_al:LIPIcs.CPM.2026.3,
  author =	{Alanko, Jarno N. and P\'{e}rez-L\'{o}pez, M\'{a}ximo},
  title =	{{Computing k-mers in Graphs}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.3},
  URN =		{urn:nbn:de:0030-drops-259294},
  doi =		{10.4230/LIPIcs.CPM.2026.3},
  annote =	{Keywords: Wheeler graph, Wheeler language, de Bruijn graph, graph, k-mer, q-gram, DFA, #P-hard}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.14
Hardness Results on Characteristics for Elastic-Degenerate Strings

Authors: Dominik Köppl and Jannik Olbrich

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
Generalizations of plain strings have been proposed as a compact way to represent a collection of nearly identical sequences or to express uncertainty at specific text positions by enumerating all possibilities. While a plain string stores a character at each of its positions, generalizations consider a set of characters (indeterminate strings), a set of strings of equal length (generalized degenerate strings, or shortly GD strings), or a set of strings of arbitrary lengths (elastic-degenerate strings, or shortly ED strings). These generalizations are of importance to compactly represent such type of data, and find applications in bioinformatics for representing and maintaining a set of genetic sequences of the same taxonomy or a multiple sequence alignment. To be of use, attention has been drawn to answering various query types such as pattern matching or measuring similarity of ED strings by generalizing techniques known to plain strings. However, for some types of queries, it has been shown that a generalization of a polynomial-time solvable query on classic strings becomes NP-hard on ED strings, e.g. [Russo et al., 2022]. In that light, we wonder about other types of queries that are of particular interest to bioinformatics: unique substrings, absent words, anti-powers, longest previous factors, and Lempel-Ziv-like compression schemes. While we obtain a polynomial time algorithm for a variation of longest previous factors, we show that all other problems are NP-hard to compute, some of them even under the restriction that the input can be modeled as an indeterminate or GD string.
Cite as

Dominik Köppl and Jannik Olbrich. Hardness Results on Characteristics for Elastic-Degenerate Strings. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koppl_et_al:LIPIcs.CPM.2026.14,
  author =	{K\"{o}ppl, Dominik and Olbrich, Jannik},
  title =	{{Hardness Results on Characteristics for Elastic-Degenerate Strings}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.14},
  URN =		{urn:nbn:de:0030-drops-259409},
  doi =		{10.4230/LIPIcs.CPM.2026.14},
  annote =	{Keywords: Elastic-degenerate strings, NP-hardness, longest common factor, minimal unique substring, minimal absent word, anti-power, longest previous factor}
}
  • Refine by Type
  • 217 Document/PDF
  • 96 Document/HTML
  • 5 Artifact
  • 1 Volume

  • Refine by Publication Year
  • 26 2026
  • 75 2025
  • 6 2024
  • 5 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 35 Sanders, Peter
  • 8 Lehmann, Hans-Peter
  • 7 Walzer, Stefan
  • 6 Schulz, Christian
  • 5 Kurpicz, Florian
  • Show More...

  • Refine by Series/Journal
  • 189 LIPIcs
  • 16 OASIcs
  • 2 LITES
  • 2 TGDK
  • 8 DagSemProc

  • Refine by Classification
  • 30 Mathematics of computing → Graph algorithms
  • 26 Theory of computation → Data structures design and analysis
  • 23 Theory of computation → Parameterized complexity and exact algorithms
  • 22 Theory of computation → Design and analysis of algorithms
  • 22 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 6 Treewidth
  • 6 algorithm engineering
  • 5 approximation algorithms
  • 5 kernelization
  • 4 Approximation Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact