23.02.2012: Get-Together for String Algorithms Researchers in Helsinki

23.02.2012 16:15–18:00

Seminar

Exactum B119

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!