DIMACS Theoretical Computer Science Seminar

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


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.