Papers for

streaming data system developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Efficient online string prediction improves update and prediction speeds

Efficient Lempel-Ziv Prediction with the Run-Length BWT

Abstract: Lempel-Ziv Plurality (LZP) is an algorithm of Kosoy that predicts the next symbol of a string by using its Lempel-Ziv factorization, and makes at most $O(z\log n)$ mistakes on every string of length $n$ with $z$ LZ77 phrases. We give efficient online implementations of LZP and of a new variant of it. Our first implementation maintains a run-length encoded Burrows-Wheeler transform (RLBWT) of the reversed history. It implements LZP, uses $O(z\log z\log^2 n)$ bits, and has worst-case update and prediction times $O(\log z+\log\log n)$ and $O(σ(\log z+\log\log n))$, respectively, where $σ$ is the size of the alphabet. This is an exponential improvement over Kosoy's implementation, whose update time is $O(z\log^7 n)$. We then introduce the Lempel-Ziv Majority (LZM) predictor, which has the same mistake bound and update time, and predicts in $O(1)$ time independently of $σ$. These two predictors accept new symbols at any time, without knowing the alphabet in advance. For an alphabet known in advance, a different data structure gives $O(σ(1+\log z/\log\log n))$ time per symbol, which is constant when $σ=O(1)$ and $z=\mathrm{polylog}(n)$.

Sun 1 NovData Structures and AlgorithmsMachine Learning
The gist
Predicting the next letter in a sequence can help computers compress or understand text better. Kosoy created a method called LZP that predicts these letters but was slow to update and predict. The authors designed faster ways to implement LZP by using a special data structure called the run-length encoded Burrows-Wheeler transform. They also introduced a new predictor called LZM that predicts much quicker, especially when the alphabet is large or unknown.
Open → 2611.01874v1