Title: Compressing and indexing strings and labeled trees
Speaker: Paolo Ferragina, University of Pisa
Date: March 7, 2006 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk we will investigate theoretically and experimentally the design of compressed data structures for supporting substring search queries, as the ones that occur in genomic or text mining applications, and path-based queries, as the ones that occur in XML processing applications. We will introduce the notion of "compressed index" and will survey the most recent advancements on this algorithmic topic that stands at the crossing point of data compression and data structure design.