Inge Li Gørtz

activity

20052026

most citedTime-Space Trade-Offs for Lempel-Ziv Compressed Indexing

35 citations · 99 across the 47 of their papers we have counts for

collaborators

Showing 2022Show all

4 papers · 1 filter

cs.DS2022

Gapped String Indexing in Subquadratic Space and Sublinear Query Time

Philip Bille, Inge Li Gørtz, Moshe Lewenstein +3

In Gapped String Indexing, the goal is to compactly represent a string $S$ of length $n$ such that for any query consisting of two strings $P_{1}$ and $P_{2}$ , called patterns, and an…

cs.DS2022

Hierarchical Relative Lempel-Ziv Compression

Philip Bille, Inge Li Gørtz, Simon J. Puglisi +1

Relative Lempel-Ziv (RLZ) parsing is a dictionary compression method in which a string $S$ is compressed relative to a second string $R$ (called the reference) by parsing $S$ into…

cs.DS2022

The Complexity of the Co-Occurrence Problem

Philip Bille, Inge Li Gørtz, Tord Stordalen

Let $S$ be a string of length $n$ over an alphabet $Σ$ and let $Q$ be a subset of $Σ$ of size $q \geq 2$ . The 'co-occurrence problem' is to construct a compact data structure that…

cs.DS2022

Predecessor on the Ultra-Wide Word RAM

Philip Bille, Inge Li Gørtz, Tord Stordalen

We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with 'ultrawords' consisting of $w^{2}$ bits [TAMC, 2015]. The m…