Seminario de Datos: "Wavelet Trees for All"


Compartir
Charlista: 
Gonzalo Navarro, académico DCC U. de Chile.
Fecha: 
8 Noviembre, 2012 - 13:30
Sala: 
Auditorio 4to. piso
Organización: 
Pablo Barceló, académico DCC.

Abstract:

 

The wavelet tree is a versatile data structure that serves a number of purposes, from string processing to geometry and more. It can be regarded as a device that represents a sequence, or that represents a grid of points, or that encodes a reordering of a sequence of elements. In addition, its space adapts to various compressibility criteria of the the data it encodes, enabling compressed representations. New competitive solutions to fundamental problems, based on wavelet trees, are appearing every year. In this talk I will give an overview of the surprising number of applications in which I have found wavelet trees extremely useful: basic and weighted point grids, sets of rectangles, strings, permutations, binary relations, graphs, inverted indexes, document retrieval indexes, full-text indexes, XML indexes, and general numeric sequences.

--
Comunicaciones DCC