Get-Together for String Algorithms Researchers in Helsinki

Event type: 
Seminar
Event time: 
23.02.2012 - 16:15 - 18:00
Lecturer : 
Travis Gagie
Place: 
Exactum B119
Description: 

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!

16.02.2012 - 09:22 Leena Salmela
16.02.2012 - 09:22 Leena Salmela