3 citations · 4 across the 4 of their papers we have counts for
6 papers · 1 filter
Suffix arrays with a twist
Tomasz Kowalski, Szymon Grabowski, Kimmo Fredriksson +1
The suffix array is a classic full-text index, combining effectiveness with simplicity. We discuss three approaches aiming to improve its efficiency even more: changes to the navig…
Rank and select: Another lesson learned
Szymon Grabowski, Marcin Raniszewski
Rank and select queries on bitmaps are essential building bricks of many compressed data structures, including text indexes, membership and range supporting spatial data structures…
A Bloom filter based semi-index on -grams
Szymon Grabowski, Robert Susik, Marcin Raniszewski
We present a simple -gram based semi-index, which allows to look for a pattern typically only in a small fraction of text blocks. Several space-time tradeoffs are presented. Exp…
FM-index for dummies
Szymon Grabowski, Marcin Raniszewski, Sebastian Deorowicz
The FM-index is a celebrated compressed data structure for full-text pattern searching. After the first wave of interest in its theoretical developments, we can observe a surge of…
Sampling the suffix array with minimizers
Szymon Grabowski, Marcin Raniszewski
Sampling (evenly) the suffixes from the suffix array is an old idea trading the pattern search time for reduced index space. A few years ago Claude et al. showed an alphabet sampli…
Two simple full-text indexes based on the suffix array
Szymon Grabowski, Marcin Raniszewski
We propose two suffix array inspired full-text indexes. One, called SA-hash, augments the suffix array with a hash table to speed up pattern searches due to significantly narrowed…