Get-Together for String Algorithms Researchers in Helsinki
The program consists of a talk by Travis Gagie (Aalto University):
Title: A Faster Grammar-Based Self-Index
Authors: Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Yakov Nekrich and Simon J. Puglisi
Abstract:
To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on straight-line programs and LZ77. In this paper we show how, given a balanced straight-line program for a string S[1..n] whose LZ77 parse consists of z phrases, we can add O(z log log z) words and obtain a compressed self-index for S such that, given a pattern P[1..m], we can list the occ occurrences of P in S in O(m^2 + (m + occ) log log n) time. All previous self-indexes are either larger or slower in the worst case.
Welcome!