Agenda

27 May 2024 14:00

Linear Suffix Array Construction by Almost Pure Induced-Sorting

Laboratorio ACADIA, edificio ZETA - Campus Scientifico via Torino

Speaker: Giacomo Zanatta, Università Ca' Foscari Venezia

Abstract:
A suffix array is a data structure that stores a string's suffixes in lexicographically sorted order. This data structure is useful for creating text indexes, performing text compression, and efficiently executing pattern matching over a string. There are several methods for building a suffix array, including (i) sorting all the suffixes of a string (impractical for very long strings), (ii) performing a lexicographic-depth first traversal of a suffix tree, or (iii) using a dedicated Suffix Array Construction Algorithm (SACA).
This seminar will explore the SA-IS (Suffix Array - Induced Sorting) algorithm, discussing the 2009 original paper "Linear Suffix Array Construction by Almost Pure Induced-Sorting" by Nong et al. This algorithm offers a linear time and efficient divide-and-conquer approach to sorting string suffixes.

Bio Sketch:
Giacomo Zanatta is a PhD student in Computer Science in our department and will present this topic for his exam of the PhD course "compressed data structures".

Language

The event will be held in Italian

Organized by

Nicola Prezza

Search in the agenda