5 papers · 1 filter
Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
Philip Bille, Inge Li Gørtz, Tord Stordalen +1
We consider the dynamic range minimum problem on the ultra-wide word RAM model of computation. This model extends the classic -bit word RAM model with special ultrawords of leng…
Rank and Select on Degenerate Strings
Philip Bille, Inge Li Gørtz, Tord Stordalen
A 'degenerate string' is a sequence of subsets of some alphabet; it represents any string obtainable by selecting one character from each set from left to right. Recently, Alanko e…
Sliding Window String Indexing in Streams
Philip Bille, Johannes Fischer, Inge Li Gørtz +2
Given a string over an alphabet , the 'string indexing problem' is to preprocess to subsequently support efficient pattern matching queries, i.e., given a pattern string…
The Complexity of the Co-Occurrence Problem
Philip Bille, Inge Li Gørtz, Tord Stordalen
Let be a string of length over an alphabet and let be a subset of of size . The 'co-occurrence problem' is to construct a compact data structure that…
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 bits [TAMC, 2015]. The m…