Login
Talks & Seminars
Title: Compressed Text Indexing and Succint Data Structures
Prof. Rahul Shah, Louisiana State University and National Science Foundation
Date & Time: December 22, 2015 11:00
Venue: Conference Room, C Block, 01st Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
In the era of big data, data sizes are ever increasing, however the information content in the data is often low. Many such data sets can be compressed to much under their original size. The field of succinct data structure attempts to achieve two goals at one shot: (1) keeping the space usage of the data structure as low as the information theoretic optimum space required for the underlying data storage and (2) achieving fast query time (polylog in data size) as if the data structure was space unaware. Classic example where succinct data structures have had a huge impact is the Suffix Trees which are used for full-text indexing. Suffix trees on text data would typically take 15 to 50 times the size of the text. Morever, many text datasets can be compressed even further. In terms of the complexity, suffix trees take O(n log n) bits of space while the raw text takes O(n log s) bits, where s is the size of the alphabet. Compressed indexes based on Burrows-Wheeler Transform(BWT) have made it possible to have text searching data structures in less than the original text's space. In this talk, I will cover some of our recent developments in this area, where the BWT based index can be made as powerful as suffix tree for pattern matching variants where suffix trees need augmenting information as well as those variants which need different notions of suffix trees.
Speaker Profile:
Dr. Rahul Shah is a Roy Paul Daniel Distinguished Associate Professor at Louisiana State University (LSU). He did is undergraduate degree from Indian Institute of Technology, Bombay and his Doctoral degree in computer science from Rutgers University. His main areas of interest are data structures and algorithms. He particularly specializes in string matching and external memory algorithms. Prior to joining LSU, he was an assistant research professor at Purdue University. He also spent a year working as a research staff member at IBM India Research Lab. He is currently serving as a program director in algorithms foundations at NSF.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback