Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Local Decodability of the Burrows-Wheeler Transform
Speaker:Sandip Sinha
coming from:Columbia University
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 18 June 2019
Duration:45 Minutes
Building:E1 4
The Burrows-Wheeler Transform (BWT) is a reversible preprocessing step that facilitates significant compression of strings with context, and is the basis of the bzip compression program. Alas, the decoding process of BWT is inherently sequential and requires \Omega(n) time even to retrieve a single character.

We study the succinct data structure problem of locally decoding short substrings of a given text under its compressed BWT, i.e., with small additive redundancy r over the Move-To-Front compression. The celebrated BWT-based FM-index yield a trade-off of r = O~(n/\sqrt{t}) bits, to decode a single character in O(t) time. We give a near-quadratic improvement r = O~(n\lg(t)/t). As a by-product, we obtain an exponential (in t) improvement on the redundancy of the FM-index for counting pattern-matches on compressed text. In the interesting regime where the text compresses to n^{1-o(1)} bits, these results provide an exp(t) overall space reduction. For the local decoding problem of BWT, we also prove an \Omega(n/t^2) cell-probe lower bound for "symmetric" data structures.

We achieve our main result by designing a compressed partial-sums (Rank) data structure over BWT. The key component is a locally-decodable Move-to-Front (MTF) code: with only O(1) extra bits per block of length n^{\Omega(1)}, the decoding time of a single character can be decreased from \Omega(n) to O(\lg n). This result is of independent interest in algorithmic information theory.

This is joint work with Omri Weinstein.

Note: This talk will take 45min.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Karl Bringmann, 05/12/2019 11:03 AM
  • Karl Bringmann, 04/18/2019 10:29 AM -- Created document.