Search Results

Documents authored by Schmitz, Johanna Elena

Artifact
Software
DOI: 10.4230/artifacts.27620
DivQuant

Authors: Johanna Elena Schmitz and Sven Rahmann

Abstract
Cite as

Johanna Elena Schmitz, Sven Rahmann. DivQuant (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27620,
   title = {{DivQuant}}, 
   author = {Schmitz, Johanna Elena and Rahmann, Sven},
   note = {Software, version 0.1., swhId: \href{https://archive.softwareheritage.org/swh:1:dir:1ca96b0e0bbf05c5e7afa9dee8101fd46e1246b5;origin=https://gitlab.com/rahmannlab/divquant;visit=swh:1:snp:02bbab1fb6f82d9f58a60d98ca97d13a79773826;anchor=swh:1:rev:2baab79d828dca7d5dcffcbe2c333baf05a92d82}{\texttt{swh:1:dir:1ca96b0e0bbf05c5e7afa9dee8101fd46e1246b5}} (visited on 2026-08-27)},
   url = {https://gitlab.com/rahmannlab/divquant},
   doi = {10.4230/artifacts.27620},
}
Document
DOI: 10.4230/LIPIcs.WABI.2026.16
DivQuant: Estimation of Species Richness and Entropy from Small Samples

Authors: Johanna Elena Schmitz and Sven Rahmann

Published in: LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026)

Abstract
Estimating diversity properties of discrete distributions from a small observed sample is a fundamental problem in algorithmic statistics that has applications in many fields, in particular bioinformatics, but also in ecology or linguistics. The two most common diversity measures are the number of distinct elements in a multiset, also referred to as "species richness" in ecology or "alpha diversity" in microbial analysis, and the Shannon entropy, also referred to as "evenness". Estimating these properties from a small sample is particularly challenging for distributions with many rare elements. Thus, many estimators have been proposed in the past that, in practice, work well for different types of distributions. We present DivQuant, an optimization-based, extrapolating richness and entropy estimator with three contributions. First, we formulate the upsampling problem as a convex quadratic program with a Neyman χ² objective. Unlike the linear program of its predecessor RichnEst, DivQuant admits confidence intervals via χ² test inversion that are empirically well-calibrated. Second, we replace RichnEst’s fixed-threshold fingerprint truncation with the rare/abundant fingerprint split of Valiant and Valiant, which strongly reduces problem size and preserves enough degrees of freedom for the confidence-interval program to remain valid and feasible. Third, we plug the optimal population fingerprint returned by the program into Shannon’s entropy formula to obtain an entropy estimate. DivQuant attains close-to-nominal 95% confidence intervals in essentially all tested regimes, including six simulated distribution families, Tara Oceans microbiome data, and 10X Genomics scRNA-seq data, while competing state-of-the-art methods (RichnEst, iNext, PreSeq) miss the true richness in up to 80% of instances, well above the nominal 5%. In addition, DivQuant outperforms classical asymptotic entropy estimators (Miller-Madow, CAE) and the extrapolating iNext estimator. Running times remain competitive, with DivQuant typically completing in seconds.
Cite as

Johanna Elena Schmitz and Sven Rahmann. DivQuant: Estimation of Species Richness and Entropy from Small Samples. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schmitz_et_al:LIPIcs.WABI.2026.16,
  author =	{Schmitz, Johanna Elena and Rahmann, Sven},
  title =	{{DivQuant: Estimation of Species Richness and Entropy from Small Samples}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{16:1--16:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-446-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{390},
  editor =	{El-Mabrouk, Nadia and Vandin, Fabio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.16},
  URN =		{urn:nbn:de:0030-drops-275201},
  doi =		{10.4230/LIPIcs.WABI.2026.16},
  annote =	{Keywords: diversity estimation, alpha diversity, species richness, entropy estimation, upsampling, linear program, quadratic program}
}
Artifact
Software
DOI: 10.4230/artifacts.23082
BlowChoc filters

Authors: Johanna Elena Schmitz, Jens Zentgraf, and Sven Rahmann

Abstract
Cite as

Johanna Elena Schmitz, Jens Zentgraf, Sven Rahmann. BlowChoc filters (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23082,
   title = {{BlowChoc filters}}, 
   author = {Schmitz, Johanna Elena and Zentgraf, Jens and Rahmann, Sven},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:109cfb17836edb54632d60844a0cd2771d125e94;origin=https://gitlab.com/rahmannlab/blowchoc-filters;visit=swh:1:snp:eab240e3259e1aa944fa4af56768ac4dad71b559;anchor=swh:1:rev:9737e51453655741704432fea2f4337919d55802}{\texttt{swh:1:dir:109cfb17836edb54632d60844a0cd2771d125e94}} (visited on 2025-07-15)},
   url = {https://gitlab.com/rahmannlab/blowchoc-filters},
   doi = {10.4230/artifacts.23082},
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.25
Blocked Bloom Filters with Choices

Authors: Johanna Elena Schmitz, Jens Zentgraf, and Sven Rahmann

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Probabilistic filters are approximate set membership data structures that represent a set of keys in small space, and answer set membership queries without false negative answers, but with a certain allowed false positive probability. Such filters are widely used in database systems, networks, storage systems and in biological sequence analysis because of their fast query times and low space requirements. Starting with Bloom filters in the 1970s, many filter data structures have been developed, each with its own advantages and disadvantages, e.g., Blocked Bloom filters, Cuckoo filters, XOR filters, Ribbon filters, and more. We introduce Blocked Bloom filters with choices that work similarly to Blocked Bloom filters, except that for each key there are two (or more) alternative choices of blocks where the key’s information may be stored. When inserting a key, we select the block using a cost function which takes into account the current load and the additional number of bits to be set in the candidate blocks. The result is a filter that partially inherits the advantages of a Blocked Bloom filter, such as the ability to insert keys rapidly online or the ability to slightly overload the filter with only a small penalty to the false positive rate. At the same time, it avoids the major disadvantage of a Blocked Bloom filter, namely the larger space consumption. Our new data structure uses less space at the same false positive rate, or has a lower false positive rate at the same space consumption as a Blocked Bloom filter. We discuss the methodology, cost functions for block selection, engineered implementation, a detailed performance evaluation and use cases in bioinformatics of Blocked Bloom filters with choices, showing that they can be of practical value. The implementation of the evaluated filters and the workflows used are provided via Gitlab at https://gitlab.com/rahmannlab/blowchoc-filters.
Cite as

Johanna Elena Schmitz, Jens Zentgraf, and Sven Rahmann. Blocked Bloom Filters with Choices. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schmitz_et_al:LIPIcs.SEA.2025.25,
  author =	{Schmitz, Johanna Elena and Zentgraf, Jens and Rahmann, Sven},
  title =	{{Blocked Bloom Filters with Choices}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra 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.SEA.2025.25},
  URN =		{urn:nbn:de:0030-drops-232631},
  doi =		{10.4230/LIPIcs.SEA.2025.25},
  annote =	{Keywords: Probabilistic filter, Bloom filter, power of two choices}
}

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