Binary Jumbled Indexing: Suffix tree histogram

Luís Cunha, Mário Medina* · 2025

Read Binary Jumbled Indexing: Suffix tree histogram by Luís Cunha, Mário Medina* (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00111.txt.

Description

Luís Cunha and Mário Medina speed up a classic string puzzle in a paper whose text dates to 2024. Given a string of zeros and ones, the puzzle asks which mixes of zeros and ones appear inside it. A data structure answering such questions for every mix is called a jumbled index.

Earlier builders of the index slowed badly on strings with many runs of the same digit, and the authors prove that slowdown is typical, not rare. Their new algorithm grows a suffix tree to strip out repeated substrings before counting. The worst-case cost stays high, but leaner memory access makes it faster in practice. The work matters for pattern matching in texts and biological sequences.

Catalog record

CREATORLuís Cunha, Mário Medina*
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00111

Browse the full library · About the Tower of Babel