Online Program Home
My Program

Abstract Details

Activity Number: 245 - Methods for Analysis of High-Dimensional Data
Type: Contributed
Date/Time: Monday, July 30, 2018 : 2:00 PM to 3:50 PM
Sponsor: SSC
Abstract #330877
Title: Efficient Forward Algorithms for Inverse Burrows-Wheeler Transformation
Author(s): Gun Ho Jang*
Companies: Ontario Institute for Cancer Research
Keywords: Burrows-Wheeler transformation; Inverse Burrows-Wheeler transformation; cache miss; IBWT; BWT

Burrows-Wheeler transformation has been used in many fields such as lossless data compression, search in text and read alignments in genome sequencing. Particularly both Burrows-Wheeler transformation and its inversion are important in lossless data compression. There are many efficient inversion algorithms available, however, all of them recovers the original text one by one from the end to obtain better efficiency in both time and working memory. We present new algorithms which recovers the original text from the beginning with high efficiency either in time or in working memory space. Performances of proposed algorithms are compared to other known efficient algorithms with public corpus.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2018 program