Charla: Space-efficient encodings for various range queries

Srinivasa Rao Satti
9 Marzo, 2016 - 14:30
Auditorio Ramón Picarte, Piso 3, Edificio Norte
Prof. Jérémy Barbay


An encoding of a given data with respect to a set of queries is any data structure that stores enough information about the data in order to support the queries, without having access to the input data at query time. A classic example is a 2n-bit encoding of an integer array of size n that supports range minimum queries -- a range minimum query (RMQ) asks for a position of the smallest element in the given query range.


This result on RMQ encoding has been extended in two ways - (i) by supporting leftmost, rightmost and median positions among the minimum values in the query range, using ~2.54n bits, and (ii) by supporting both range minimum and range maximum queries, using 3n bits.


In this talk, first I will present further extensions of these results by describing encodings that support a wide range of queries (range queries mentioned above, and some related queries). Then I will describe some encodings of two-dimensional integer arrays that support range top-k queries - given a 4-sided range, a range top-k query returns the positions of the k largest elements in the query range.